Some Basic Definitions
Graph
A simple graph
can be thought of as a triple G=(V,E,I), where V and E
are disjoint finite sets and I is an incidence relation such
that every element of E is incident with exactly two distinct
elements of V and no two elements of E are incident to
the same pair of elements of V. Obviously, these requirements
can be varied (and we get general graphs, hypergraphs, infinite
graphs, directed graphs, oriented graphs, etc.). We call V the
vertex set and E the edge set of G.
Regular Graph
If
all the vertices
of G have the same degree k, then G is k-regular ,
or simply
regular . A
cubic
3-regular graph is called cubic.
Degree
of a vertex
The degree,
d(v), of a vertex v is the number of edges with which
it is incident. Two vertices are adjacent if they are incident
to a common edge. The set of neighbours, N(v), of a
vertex v is the set of vertices which are adjacent to v.
The degree of a vertex is also the cardinality of its neighbour
set.
Digraph
- A digraph (or a directed graph) is a graph in which the
edges are directed. (Formally: a digraph is a (usually finite) set
of vertices V and set of ordered pairs (a,b) (where a,
b are in V) called edges. The vertex a is the initial
vertex of the edge and b the terminal vertex.
-
Pseudograph
- Informally, a pseudograph is a graph with multiple edges (or loops)
between the same vertices (or the same vertex). Formally: a
pseudograph is a set V of vertices along, a set E of
edges, and a function f from E to {{u,v}|u,v
in V}. (The function f shows which vertices are connected by
which edge.) An edge is a loop if f(e) = {u}
for some vertex u in V.
-
Loop
- A loop is an edge that connects a vertex to itself.
Walk
A
walk is an
alternating sequence of vertices and edges, with each edge being
incident to the vertices immediately preceding and succeeding it in
the sequence.
Trail
A
trail
is a walk with no repeated edges.
Path
A
path is a walk
with no repeated vertices. A walk is
closed if the initial
vertex is also the terminal vertex.
The length of a
walk is the number of edges in the sequence defining the walk. Thus,
the length of a path or cycle is also the number of edges in the path
or cycle. If u and v are vertices, the distance
from connected graphu to v, written d(u,v), is
the minimum length of any path from u to v. In an
undirected graph, this is obviously a metric. The eccentricity,
e(u), of the vertex u is the maximum value of d(u,v),
where v is allowed to range over all of the vertices of the
graph. The radius of the graph G, rad(G), is the
minimum value of e(u), for any vertex u, and the
diameter, diam(G), is the corresponding maximum value.
It should be obvious that diam(G) ≤ 2rad(G).
For a
set of vertices X, we use G[X] to denote the induced
subgraph of G whose vertex set is X and whose edge
set is the subset of E(G) consisting of those edges with both
ends in X. For a set S of edges, we use G[S] to
denote the edge induced subgraph of G whose edge set is
S and whose vertex set is the subset of V(G) consisting
of those vertices incident with any edge in S. If Y is
a subset of V(G), we write G-Y for the subgraph
G[V(G)-Y].
Complete Graph
A graph is
complete, or a
clique, if every pair of
distinct vertices is adjacent. (The adjacency matrix of a complete
graph has zeroes on the main diagonal, and ones off the diagonal.) We
write
Km for the complete graph on
m
vertices. Number of edges = m(m-1)/2
Connected
Graph
A non-empty graph G is called
connected if any two of its vertices are
linked by a path in
G. If U ⊆ V (G) and G [ U ] is connected, we also
call U itself
connected (in G). Instead of ‘not connected’ we usually say
‘disconnected’.
A graph G has connectivity k
if G is k-connected but not (k+1)-connected. A
complete graph on k+1 vertices is defined to have connectivity
k.
Bipartite graphs
Let r
>2 be an integer. A graph G = (V, E) is called r-partite
if
V admits a partition into r classes such that every edge has its
ends
in different classes: vertices in the same partition class must
not be
adjacent. Instead of ‘2-partite’ one usually says
bipartite.
An r-partite graph in which every two
vertices from different partition classes are adjacent is called
complete; the complete r-partite
graphs for all r together are the
complete multipartite graphs. Graphs of the form K1,n are
called
stars; the vertex in the singleton partition class of this K1,n is
the
star’s centre.
Cycle
A
cycle is a
closed trail with at least one edge and with no repeated vertices
except that the initial vertex is the terminal vertex.
- Circuit
- A circuit is a path which ends at the vertex it begins (so a loop is
an circuit of length one).
Forest
A graph is acyclic if it has no
cycles. An acyclic graph is also called a forest.
Acyclic
Graph
An acyclic graph is a graph having no graph cycles.
A connected acyclic graph is known as a tree, and a possibly
disconnected acyclic graph is known as a forest (i.e., a collection
of trees).
The numbers of acyclic graphs (forests) on n =1, 2, ... are 1, 2,
3, 6, 10, 20, 37, 76, 153, ...
Tree
A
tree
is a connected, acyclic graph. Thus every connected component
of a forest is a tree.
Spanning
tree
A
spanning
tree of a graph
G is a subgraph
T of
G which
is a tree and which satisfies
|V(T)|=V|(G)|.
If
T is a tree, then
|V(T)|=E|(T)|+1. Any tree with at least two vertices must have
a vertex of degree one. Alternately, one could define a tree as a
connected graph
T satisfying
|V(T)|=E|(T)|+1 or as an
acyclic graph
T satisfying
|V(T)|=E|(T)|+1. Every
connected graph must have a spanning tree.
The number of spanning trees in the complete graph Kn
with n vertices is = t(Kn)= nn-2
Minimum Spanning Tree
(MST)
A minimum spanning tree (MST) or
minimum weight spanning tree is a spanning tree with weight less than
or equal to the weight of every other spanning tree. More generally,
any undirected graph (not necessarily connected) has a minimum
spanning forest, which is a union of minimum spanning trees for its
connected components.
Kruskal's algorithm
Kruskal's algorithm is an
algorithm in graph theory that finds a minimum spanning tree for a
connected weighted graph. This means it finds a subset of the edges
that forms a tree that includes every vertex, where the total weight
of all the edges in the tree is minimized. If the graph is not
connected, then it finds a minimum spanning forest (a minimum
spanning tree for each connected component). Kruskal's algorithm is
an example of a greedy algorithm. If E is the number of edges
in the graph and V is the number of vertices, Kruskal's
algorithm can be shown to run in O(E
log E) time, or equivalently, O(E log V)
time
Eccentricity
Let G be a graph and v be
a vertex of G. The
eccentricity
of the vertex v is the maximum distance from v
to any vertex. That is, e(v)=max{d(v,w):w in V(G)}.
The
radius
of G
is the minimum eccentricity among the vertices of G.
Therefore, radius(G)=min{e(v):v in V(G)}.
Diameter
The
diameter
of G
is the maximum eccentricity among the vertices of G.
Thus, diameter(G)=max{e(v):v in V(G)}.
The
girth
of G is
the length of a shortest cycle in G.
The
center
of
G is the set of vertices of eccentricity equal to
the radius. Hence,
center(G)={v in
V(G):e(v)=radius(G)}.
- Planar
- A graph is planar if it can be drawn on a plane so that the edges
intersect only at the vertices. (For example, of the five first
complete graphs all but the fifth, K5, is
planar.)
Hamiltonian path
A Hamiltonian path or traceable path is a path that
visits each vertex exactly once. A graph that contains a Hamiltonian
path is called a traceable graph. A graph is
Hamiltonian-connected if for every pair of vertices there is a
Hamiltonian path between the two vertices.
A Hamiltonian cycle, Hamiltonian circuit, vertex
tour or graph cycle is a cycle that visits each vertex
exactly once (except the vertex that is both the start and end, and
so is visited twice). A graph that contains a Hamiltonian cycle is
called a Hamiltonian graph.
Similar notions may be defined for directed graphs, where
each edge (arc) of a path or cycle can only be traced in a single
direction (i.e., the vertices are connected with arrows and the edges
traced "tail-to-head").
Eulerian Path
An Eulerian trail (or Eulerian
path) is a trail in a graph which visits every edge exactly once.
Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail
which starts and ends on the same vertex.
The term Eulerian graph has two
common meanings in graph theory. One meaning is a graph with an
Eulerian circuit, and the other is a graph with every vertex of even
degree. These definitions coincide for connected graphs.
For the existence of Eulerian trails
it is necessary that no more than two vertices have an odd degree;
this means the Königsberg graph is not Eulerian. If there are
no vertices of odd degree, all Eulerian trails are circuits. If there
are exactly two vertices of odd degree, all Eulerian trails start at
one of them and end at the other. A graph that has an Eulerian trail
but not an Eulerian circuit is called semi-Eulerian.
Some important things in graph theory
1.The sum of
degrees of the vertices of a graph is even
2. Every graph has an even number of odd vertices
If the number of odd vertices is
greater than 2 no euler walk exists
If the number of odd vertices is
2, euler walks exist starting at either of the odd vertices
- With no odd vertices, euler walks can start at an arbitrary
vertex
For
a graph, the sum of degrees of all its nodes equals twice the
number of edges.
For a
graph, the sum of degrees of all its nodes is even
Elements of an edge are said to be
incident to that edge.
Likewise,
an edge is incident to its elements.
A
degree of a vertex is the number of edges incident to it
(
loops being counted twice).
A vertex of odd (even) degree is said to be
odd (
even).
A walk v
0,
e
1, v
1, e
2, ..., v
n is
said to connect v
0 and v
n.
A walk is
closed if v
0n. A closed walk is called
a
cycle.
A walk which is not closed is
open.
A walk is an
euler walk if every edge of the graph appears
in the walk exactly once.
A graph is
connected if every two vertices can be connected
by a walk.
1. If
a graph has a closed euler walk then every vertex is even.
2. If
every vertex of a connected graph is even, the graph has an euler
walk.
3. If a
graph has an open euler walk it has exactly two odd vertices.
4. If a connected graph has exactly
two odd vertices it also has an open euler walk.
Previous year question and answer on graph theory
and answer:
1) The graph K3,4 has :
(A) 3 edges (B) 4 edges (C) 7 edges (D) 12 edges
2) The total number of spanning
trees that can be drawn using five labelled vertices is :
(A) 125 (B) 64 (C) 36 (D) 16
3) Which of the following does not define a tree ?
(A) A tree is a connected acyclic graph.
(B) A tree is a connected graph with n-1 edges where 'n' is the number of
vertices in the graph.
(C) A tree is an acyclic graph with n-1 edges where 'n' is the number of
vertices in the graph.
(D) A tree is a graph with no cycles.
4) The complexity of Kruskal's minimum spanning tree algorithm on a
graph with 'n' nodes and 'e' edges is :
(A) O (n) (B) O (n log n) (C) O (e log n) (D) O (e)
5) The number of edges in a complete graph with 'n' vertices is equal
to :
(A) n(n-1) (B)n(n-1)/2
(C) n2 (D) 2n-1
6) Depth travels option of the following directed graph is :
(A) ABCDEF (B) ABDEFC
(C) ACEBDF (D) None of the above
7) The maximum number of nodes in a binary tree of depth 10 :
(A) 1024 (B) 210 -1 (C) 1000 (D) None of them
8) The number of edges in a complete graph with N vertices is equal
to :
(A) N (N−1) (B) 2N−1 (C) N−1 (D) N(N−1)/2
9) For a complete graph with N vertices, the total number of spanning
trees is given by :
(A) 2N-1 (B) NN-1 (C) NN-2 (D) 2N+1
10) T is a graph with n vertices. T is connected and has exactly n-1
edges, then :
(A) T is a tree
(B) T contains no cycles
(C) Every pairs of vertices in T is connected by exactly one path
(D) All of these
11) Which of the following statement is false ?
(A) Every tree is a bipertite graph
(B) A tree contains a cycle
(C) A tree with n nodes contains n-1 edges
(D) A tree is a connected graph
12) The following lists are the degrees of all the vertices of a
graph :
(i) 1, 2, 3, 4, 5 (ii) 3, 4, 5, 6, 7
(iii) 1, 4, 5, 8, 6 (iv) 3, 4, 5, 6
then
(A) (i) and (ii) (B) (iii) and (iv)
(C) (iii) and (ii) (D) (ii) and (iv)
