DAA Note 2
Uploaded by
AMAN KUMAR SHAWDAA Note 2
Uploaded by
AMAN KUMAR SHAWGraph Theory
Walk: A walk is defined as a finite alternating sequence of vertices and edges,
starting and ending with vertices such that each edge is incident with the vertices
preceding and following it. No edge can be repeated in a walk.
e1
V1 V2
e5 e2
e4
V4 V3
e3
Fig-1
In the above graph V1e1V2e2V3e3V4e4V2 is a walk. Note that here no edge is
repeated but the vertex V2 is repeated twice.
Note the walk carefully.
It is started with V1 and ended with V2.
V2,V3 ,V4 all are intermediate vertices. V2 also came as end vertex of the
walk.
The edge e1 is incident with the vertices V1 and V2, e2 incident with V2 and
V3. Similarly other edges also.
But V1e1V2e4V4e5V1e1V2 is not a walk as the edge e1 is repeated twice.
Terminal Vertices: The vertices with which a walk begins and ends are called
terminal vertices. For example in the walk V1e1V2e2V3e3V4e4V2, V1 and V2 are
terminal vertices.
Open Walk: If the terminal vertices are different for a walk then it is called open
walk. For example V1e1V2e2V3e3V4e4V2 is an open walk as terminal vertices are
different v iz V1 and V2.
Closed Walk: If for a walk terminal vertices are same then it is called a closed
walk. For example in the above graph (Fig-1) V1e1V2e2V3e3V4e5V1 is a closed
walk. Here both the terminal vertices =V1.
Path: A path is an open walk where no vertices come more than once. For
example in Fig-1 V1e1V2e2V3e3V4 is Path, but V1e1V2e2V3e3V4e4V2 is not a
path as the vertex V2 is repeated.
All the intermediate vertices in a path have degree 2, w.r.t the walk but not w.r.t
entire graph. For example V4 has degree 3 w.r.t the entire graph, but in the path
V1e1V2e2V3e3V4 it’s degree is 2 as it is connected with the edges e3 and e4 only
in the walk.
Circuit: A closed walk where no vertex (except initial and final) appears more than
once is called a circuit or cycle. For example V1e1V2e2V3e3V4e5V1 is a circuit in
the graph of Fig-1.
Euler Line: If in a graph some closed walk contains all the edges of the graph then
that walk is called Euler Line.
Euler Graph: A graph containing an Euler Line is called Euler Graph. The following
graph has a Euler line namely v1e1v2e6v5e8v6e7v2e2v3e3v4e5v1.
e6
e1 V5
V1 V2
e8
e7
e5 V6
e2
V4 V3
e3
Fig-2
Isolated Vertex: If in a graph a vertex is not connected to any other vertex then
that vertex is called an isolated vertex. Note that an isolated vertex must have
degree 0.
V1 V2
V4
V3
Fig-3
In Fig-3 V4 is an isolated vertex.
Pendant Vertex: In a graph a vertex with degree 1 is called pendant vertex. For
example in Fig-3 vertex v1 and v2 both are pendant vertex.
Connected Graph: A graph is called connected, if between any two vertices there
is a path otherwise called disconnected. The graphs in Fig-1 and Fig-2 are
connected but the graph Fig-3 is not connected.
V2 V4
V1 V5
V3
Fig-4
Note that the graph in Fig-4 is not connected since there is no path between v2
and v4.
Note that a disconnected graph always consists of two or more connected graphs.
These are called components. Note that the graph in Fig-4 has two connected
components, one consists of the vertices {v1,v2,v3} and other contains {v4,v5}.
Complete Graph: A simple graph is called complete if between any two pair of
vertices there is an edge.
The below graph Fig-5 is a compete graph with 5 vertices. Note that the number
of edges in the graph is 10.
Also note that each vertex in the complete graph has degree 4. In general in a
complete graph with n vertices, degree of each vertex is n-1. The simple reason is
any vertex is connected with all other vertices by an edge.
Now how many total number of edges in a complete graph with n vertices? Let
the total number of edges is T.
Then 2×T= Sum of the degree of all vertices=n(n-1) ,since each vertex of a
complete graph has degree n-1.
Hence T=n(n-1)/2
Note that if n=5, then T=5(5-1)/2=10, which we have seen just now.
Fig-5