GATE CS/IT

GATE 2015 paper discussion

GRAPH THEORY

Definition of a graph : A linear undirected graph G=(V,E) consists of a set of objects V={v₁,v₂,v₃...} called vertices and another set E={e₁,e₂,e₃...} whose elements are called edges, such that each edge is identified with an unordered pair (v_i,v_j) of vertices.
A Graph is also called as Linear complex, 1-complex or one dimensional complex.

Some characteristics of vertices and edges :

• There may be any number of edges from a vertex to another vertex. All these edges are called as parallel edges.
• An edge that starts and ends on the same vertex is known as self-loop.
• Two non parallel edges are said to be adjacent if they are incident on a common vertex.
• Two vertices are said to be adjacent if they are end vertices of same edge.
• The number of edges incident on a vertex, with self loop counted twice, is called the degree or valency of vertex.

example-

Here, in this diagram vertex set,V={a,b,c,d,e,f} and edge-set,E={a-b,a-c,a-d,b-e,d-f,d-f,f-f}. Note that, there are two edges between vertex d and f. These type of edges which have both vertex in common, are called as parallel edges.
Also, There is an edge which starts with and ends on vertex f. These type of edges with starts with and ends on the same vertex are called as self-loops.

SIMPLE GRAPH : A Graph that has neither self-loops nor parallel edges is called as simple graph.

---

Graph theory previous year Questions and Answers