Nonlinear Data Structure
- A graph G consist of a non-empty set V called the set of nodes (points, vertices) of the graph, a set E which is the set of edges and a mapping from the set of edges E to a set of pairs of elements of V.
- It is also convenient to write a graph as G=(V, E).
- Notice that definition of graph implies that to every edge of a graph G, we can associate a pair of nodes of the graph. If an edge X Є E is thus associated with a pair of nodes (u,v) where u, v Є V then we say that edge x connect u and v.
- Any two nodes which are connected by an edge in a graph are called adjacent node in Nonlinear Data Structure.
Directed & Undirected Edge
- In a graph G=(V, E) an edge which is directed from one end to another end is called a directed edge, while the edge which has no specific direction is called undirected edge.
Directed Graph (Digraph)
- A graph in which every edge is directed is called directed graph or digraph.
- A graph in which every edge is undirected is called undirected graph.
- If some of the edges are directed and some are undirected in the graph then the graph is called mixed graph.
- An edge of a graph which joins a node to itself is called a loop (sling).
- In some directed as well as undirected graphs, we may have certain pairs of nodes joined by more than one edges, such edges are called Parallel edges.
- Any graph which contains some parallel edges is called multigraph.
- A graph in which weights are assigned to every edge is called weighted graph.
- In a graph, a node which is not adjacent to any other node is called isolated node.
- A graph containing only isolated nodes are called null graph. In other words, set of edges in a null graph is empty.
Path of Graph
- Let G=(V, E) be a simple digraph such that the terminal node of an edge in the sequence is the initial node of the edge if any appearing next in the sequence defined as the path of the graph.
Length of Path
- The number of edges appearing in the sequence of the path is called length of a path.
Degree of vertex
- The no of edges which have V as their terminal node is call as in degree of node V
- The no of edges which have V as their initial node is call as outdegree of node V
- Sum of indegree and outdegree of node V is called its Total Degree or Degree of a vertex.