Thursday, May 3, 2012

Graph Theory Notes and Previous years solutions for UGC NET Computer Science & Application

Some Basic Definitions

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.
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.
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.
A loop is an edge that connects a vertex to itself.
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.
A trail is a walk with no repeated edges.
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.

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.
A circuit is a path which ends at the vertex it begins (so a loop is an circuit of length one).
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, ...

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
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)}.
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)}.
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
    1. If the number of odd vertices is greater than 2 no euler walk exists
    2. If the number of odd vertices is 2, euler walks exist starting at either of the odd vertices
    3. With no odd vertices, euler walks can start at an arbitrary vertex
    4. For a graph, the sum of degrees of all its nodes equals twice the number of edges.
    5. For a graph, the sum of degrees of all its nodes is even

  1. Elements of an edge are said to be incident to that edge.
  2. Likewise, an edge is incident to its elements.
  3. A degree of a vertex is the number of edges incident to it (loops being counted twice).
  4. A vertex of odd (even) degree is said to be odd (even).
  1. A walk v0, e1, v1, e2, ..., vn is said to connect v0 and vn.
  2. A walk is closed if v0n. A closed walk is called a cycle.
  3. A walk which is not closed is open.
  4. A walk is an euler walk if every edge of the graph appears in the walk exactly once.
  5. 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
     (A) (i) and (ii)                           (B) (iii) and (iv)
     (C) (iii) and (ii)                         (D) (ii) and (iv)

1 comment:

  1. Great Work boss

    Thanks to provide such a good details about important topics .

    Great Thanks a lot