Degree of Vertex
The degree of vertex is the total number of vertices in the graph minus 1 or we can say that the number of vertices adjacent to a vertex V is the degree of vertex.
|
1 2 3 |
Notation - deg(V). |
Degree of vertex can be considered under two cases of graphs:
- Directed Graph
- Undirected Graph
Directed Graph
A directed graph or digraph is a pair (V, E), where V is the vertex set and E is the set of vertex pairs as in “usual” graphs. The graph in which each vertex has its indegree and outdegree is known as directed graph.
Indegree of vertex V is the number of edges which are coming towards the vertex V.
|
1 2 3 4 |
Notation - deg<sup>-</sup>(V). |
Outdegree of vertex V is the number of edges which are going away from the vertex V.
|
1 2 3 4 |
Notation − deg<sup>+</sup>(V). |
For example :
Indegree of (a) -1
Outdegree of (a) – 2
Undirected Graph
The graph in which there is no directed edges is known as undirected graph.
For example:
deg(a) = 2 there are 2 edges meeting at ‘a’
deg(b) = 3 there are 3 edges meeting at ‘b’
deg(d) = 2 there are 2 edges meeting at ‘d’
Types of directed graph
- Symmetric directed graphs: The graph in which all the edges are bidirected is called as symmetric directed graph.
- Simple directed graph: The directed graph that is without loops is called as simple directed graph.
- Loop directed graph: The directed graph that has loops is called as loop directed graph or loop digraph.
- Complete directed graph: When each pair of vertices of the simple directed graph is joined by a symmetric pair of directed arrows, this graph is called as complete directed graph.
- Oriented graphs: The directed graph that has no bidirected edges is called as oriented graph.
- Weighted directed graph: The directed graph in which weight is assigned to the directed arrows is called as weighted graph.
For example:
Flow networks: These are the weighted graphs in which the two nodes are differentiated as source and sink.
Rooted directed graph: These are the directed graphs in which vertex is distinguished as root.
Signal flow graphs: The directed graph in which system variable is represented by nodes and connection between pairs and nodes is represented by branches are called as signal flow graphs.