##
__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 graph*u*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*K*_{m}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 K

_{n}with*n*vertices is = t(K_{n})= n^{n-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

The *girth*of*G*is the length of a shortest cycle in*G*.*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

**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) n^{2}(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) 2`^{10} -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) N`^{N-1} (C) N^{N-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)

` `

## No comments:

## Post a Comment