Graph Terminologies

Advertisements
Advertisements

 16 total views

In the previous lesson, you learned about graph models. In this article, you will learn about basic graph terminologies. There are some important terminologies that you will come across frequently, it is important to learn them first.

Definition 1:

Two vertices u and v are adjacent or neighbor in graph G if u and v are endpoints of edge e of G. Then we can say that edge e is incident with vertices u and v and also, connects u and v.

Definition 2:

The set of all neighbors of graph G = (V, E) is denoted by N(v) and it is called Neighborhood of v. The smaller v denotes a single vertex and larger V is a set of all vertices for the graph. If A is a subset of V, then N(A) is set of all vertices that are adjacent to at least one vertex in A.

 

N(A) = \cup_{v \epsilon A}N(v)

 

Definition 3:

The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop contributes twice to the degree of the vertex. The degree of a vertex is denoted by deg(v).

Advertisements

 

Degree of Graph
Degree of Graph

 

In the above figure, deg(A) = deg(B) =2, deg(C) = 3. When the degree is 0 then the node is said to be isolated and when the degree is 1, the node is said to be a pendant.

For example, deg(D) = 1 and deg(E) = 0.

The Handshake Theorem

The handshake theorem is a special theorem that takes the total amount of degrees of a graph. It goes like this, let G = (V, E) be an undirected graph with m edges, then

 

2m = \Sigma_{v \epsilon V} deg(v)

 

Note: This applies even when multiple edges and loops are present.

Example:-

Consider the above example  graph G = (V, E) where V = {A, B, C, D, E } and E = { (A, B), (A, C), (B, C), (C, D) } = |E| = 4

 

2 x 4= deg(A) + deg(B) + deg(C) + deg(D) + deg(E)

 

8 = 2 + 2 + 3 + 1 + 0

 

8 = 8

 

Right Hand Side = Left Hand Side

Theorem 2: Even Number of Vertices with Odd degree

An undirected graph has an even number of vertices of odd degree.

To prove the above statement, we will consider a graph G = (V, E) where V is the non-empty set of vertices and E is a set of edges for the graph. Now, we will divide the V into two sets – V1 and V2.

The set V1 has all nodes with odd degrees. The set V2 has all the nodes with even degrees.

Advertisements

Therefore,

 

V = V1 + V2

 

Example:-

To prove this theorem let’s take a graph with G = (V, E).

Graph with vertices that has even and odd degrees
A graph with vertices that has even and odd degrees

The above graph we can split the vertices into V1 (odd degrees) and V2 (even degrees).

 

V1 = { A, B, C , E}

 

V2 = { D }

 

deg(A) = 3

 

deg(B) = 3

 

deg(C) = 3

 

deg(E) = 1

 

\Sigma_{v \epsilon V1}deg(v) = 10

 

deg(D) = 2

 

\Sigma_{v \epsilon V2}deg(v) = 2

 

Now, we need the total number of edges in G which is |E| = 6.

therefore,

 

2 \times 6 = 10 + 2

 

12 = 12

 

R.H.S = L.H.S

That means, the theorem is correct and also, V1 = { A, B, C, E } is a set with even number of vertices with odd degrees.

The Degree of Directed Edges

We already know that a directed graph has directed edges from the lesson – graph models.

In a graph with directed edges the in-degree of vertex v, denoted by deg-{v}, is the number of edges with v as a terminal vertex.

The out-degree of vertex v, denoted by deg+{v}, is the number of edges with v as an initial vertex for the edges.

Note:- A loop on the vertex contribute 1 to both in-degree and out-degree at the same time.

Example:-

Find the in-degree and out-degree for the following directed graph G = (V, E).

 

The Directed Graph with In-Degree and Out-Degrees for Each Node.
The Directed Graph with In-Degree and Out-Degrees for Each Node.

 

The solution to the problem of counting in-degree and out-degree of each node in the above-directed graph is given in tabular format. You can see that some nodes have 0 degrees or 0 out-degree.

In-Degree and Out-Degree for the Directed graph
In-Degree and Out-Degree for the Directed graph

Note that a graph with a directed edge and its underlying undirected graph has the same number of edges.

Advertisements
Advertisements
Advertisements