Graph Theory
Dileep Singh Rathore
Topics Covered
Definitions
Types
Terminology
Representation
Sub-graphs
Connectivity
Hamilton and Euler definitions
Shortest Path
Planar Graphs
Graph Coloring
Definitions - Graph
A generalization of the simple concept of
a set of dots, links, edges or arcs.
Representation: Graph G =(V, E) consists set of
vertices denoted by V, or by V(G) and set of edges E, or
E(G)
Definitions – Edge Type
Directed: Ordered pair of vertices.
Represented as (u, v) directed from vertex u to
v.
u v
Undirected: Unordered pair of vertices.
Represented as {u, v}. Disregards any sense
of direction and treats both end vertices
interchangeably.
u v
Definitions – Edge Type
Loop: A loop is an edge whose
endpoints are equal i.e., an edge
joining a vertex to it self is called a
loop. Represented as {u, u} = {u}
u
Multiple Edges: Two or more edges
joining the same pair of vertices.
Definitions – Graph Type
Simple (Undirected) Graph: consists of V, a
nonempty set of vertices, and E, a set of unordered
pairs of distinct elements of V called edges (undirected)
Representation Example: G(V, E), V = {u, v, w}, E =
{{u, v}, {v, w}, {u, w}}
u v
w
Definitions – Graph Type
Multigraph: When More than one path exists
between any pair of vertices.
Representation Example: V = {u, v, w}, E = {e1, e2,
e3}
u
e1 e2
w
e3
v
Definitions – Graph Type
Directed Graph: G(V, E), set of vertices V, and set of
Edges E, that are ordered pair of elements of V (directed
edges)
Representation Example: G(V, E), V = {u, v, w}, E =
{(u, v), (v, w), (w, u)}
u v
w
Definitions – Graph Type
Directed Multigraph: Existence of parallel path or Self
loop.
Representation Example: V = {u, v, w}, E = {e1, e2, e3,
e4}
u
u e4
e1 e2
u e3
Definitions – Graph Type
Type Edges Multiple Loops Allowed
Edges ?
Allowed ?
Simple Graph undirected No No
Multigraph undirected Yes No
Pseudograph undirected Yes Yes
Directed directed No Yes
Graph
Directed directed Yes Yes
Multigraph
Terminology – Undirected
graphs
u and v are adjacent if {u, v} is an edge, e is called incident with u
and v. u and v are called endpoints of {u, v}
Degree of Vertex (deg (v)): the number of edges incident on a
vertex. A loop contributes twice to the degree (why?).
Pendant Vertex: deg (v) =1
Isolated Vertex: deg (v) = 0
u v
k
w
Terminology – Directed
graphs
For the edge (u, v), u is adjacent to v OR v is adjacent from u, u –
Initial vertex, v – Terminal vertex
In-degree (deg- (u)): number of edges for which u is terminal vertex
Out-degree (deg+ (u)): number of edges for which u is initial vertex
u v
w
Theorems: Undirected Graphs
Theorem 1
The Handshaking theorem:
2e v
vV
(why?) Every edge connects 2 vertices
Simple graphs – special
cases
Complete graph: Kn, is the simple graph that contains
exactly one edge between each pair of distinct vertices.
Representation Example: K1, K2, K3, K4
K1 K2 K3
K4
Subgraphs
A subgraph of a graph G = (V, E) is a graph H =(V’, E’) where
V’ is a subset of V and E’ is a subset of E
Application example: solving sub-problems within a graph
Representation example: V = {u, v, w}, E = ({u, v}, {v, w},
{w, u}}, H1 , H2
u u u
v w v w v
G H1 H2
Subgraphs
G = G1 U G2 wherein E = E1 U E2 and V = V1 U V2, G, G1 and G2 are
simple graphs of G
Representation example: V1 = {u, w}, E1 = {{u, w}}, V2 = {w, v},
E1 = {{w, v}}, V = {u, v ,w}, E = {{{u, w}, {{w, v}}
u
u
w v
w w v
G1 G2 G
Representation- Incidence
Matrix
Representation Example: G = (V, E)
e1 e2 e3
u
v 1 0 1
e1 e2
u 1 1 0
v w w 0 1 1
e3
Connectivity
Basic Idea: In a Graph Reachability among
vertices by traversing the edges
Application Example:
- In a city to city road-network, if one city can be
reached from another city.
- Problems if determining whether a message can
be sent between two
computer using intermediate links
- Efficiently planning routes for data delivery in
the Internet
Connectivity – Path
A Path is a sequence of edges that begins at a
vertex of a graph and travels along edges of the
graph, always connecting pairs of adjacent vertices.
Representation example: G = (V, E), Path P
represented, from u to v is {{u, 1}, {1, 4}, {4, 5},
{5, v}}
2
1 v
3
u
4 5
Connectivity –
Connectedness
Undirected Graph
An undirected graph is connected if there
exists is a simple path between every pair of
vertices
Representation Example: G (V, E) is connected
since for V = {v1, v2, v3, v4, v5}, there exists a
path between {vi, vj}, 1 ≤ i, j≤ 5
v4
v1 v3
v2 v5
Connectivity –
Connectedness
Directed Graph
A directed graph is strongly connected if there is a
path from a to b and from b to a whenever a and b are
vertices in the graph
A directed graph is weakly connected if there is a
(undirected) path between every two vertices in the
underlying undirected path
A strongly connected Graph can be weakly connected
but the vice-versa is not true (why?)
Connectivity –
Connectedness
Directed Graph
Representation example: G1 (Strong component), G2 (Weak
Component), G3 is undirected graph representation of G2 or G1
G1 G2 G3
Connectivity –
Connectedness
Directed Graph
Strongly connected Components: subgraphs
of a Graph G that are strongly connected
Representation example: G1 is the strongly
connected component in G
G G1
Isomorphism
A isomorphic invariant for simple graphs is the
existence of a simple circuit of length k , k is
an integer > 2 (why ?)
Representation example: G1 and G2 are isomorphic
since we have the invariants, similarity in degree of
nodes, number of edges, length of circuits
G1 G2
The Seven Bridges of Königsberg,
Germany
The residents of Königsberg, Germany, wondered
if it was possible to take a walking tour of the town
that crossed each of the seven bridges over the
Presel river exactly once. Is it possible to start at
some node and take a walk that uses each edge
exactly once, and ends at the starting node?
The Seven Bridges of Königsberg,
Germany
Euler:
Has no tour that uses each edge exactly once.
(Even if we allow the walk to start and finish in different
places.)
Can you see why?
Shortest-Path Problems
Shortest-Path problems
Single-source (single-destination). Find a
shortest path from a given source (vertex s) to
each of the vertices. The topic of this lecture.
Single-pair. Given two vertices, find a shortest
path between them. Solution to single-source
problem solves this problem efficiently, too.
All-pairs. Find shortest-paths for every pair of
vertices. Dynamic programming algorithm.
Unweighted shortest-paths – BFS.
Traveling Salesman
Problem
Given a number of cities and the costs of
traveling from one to the other, what is the
cheapest roundtrip route that visits each city
once and then returns to the starting city?
An equivalent formulation in terms of graph
theory is: Find the Hamiltonian cycle with the
least weight in a weighted graph.
It can be shown that the requirement of returning
to the starting city does not change the
computational complexity of the problem.
A related problem is the (bottleneck TSP): Find
the Hamiltonian cycle in a weighted graph with
the minimal length of the longest edge.
Planar Graphs
A graph (or multigraph) G is called planar if G can be drawn in the
plane with its edges intersecting only at vertices of G, such a
drawing of G is called an embedding of G in the plane.
Application Example: VLSI design (overlapping edges requires extra
layers), Circuit design (cannot overlap wires on board)
Representation examples: K1,K2,K3,K4 are planar, Kn for n>4 are
non-planar
K4
Planar Graphs
Representation examples: Q3
Minimum spanning Tree