Basics of Graph Theory� III B.sc Mathematics,� Graph Theory�

Presented by,

B.Suguna Selvarani,

Assistant Professor,

Department of Mathematics,

Cardamom Planters’ Association College,

Bodinayakanur.

Applications of Graph Theory

• Computer networks
• Distinguish between two chemical compounds with the same molecular formula but different structures
• Solve shortest path problems between cities
• Scheduling exams and assign channels to television stations

Topics Covered

​

​

​

• Definitions
• Types
• Terminology
• Representation
• Sub-graphs

​

​

​

Definition – 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 –Types of Edges

Directed: Ordered pair of vertices. Represented as (u, v) directed from vertex u to v.

​

​

Undirected: Unordered pair of vertices. Represented as {u, v}. Disregards any sense of direction and treats both end vertices interchangeably.

​

​

​

​

​

u

v

u

v

Definitions – Types of Edges

• 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}

​

​

​

• Multiple Edges: Two or more edges joining the same pair of vertices.

​

u

Definitions –Types of Graphs

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 – Types of Graphs

Multigraph: G(V,E), consists of set of vertices V, set of Edges E and a function f from E to {{u, v}| u, v V, u ≠ v}. The edges e1 and e2 are called multiple or parallel edges if f (e1) = f (e2).

Representation Example: V = {u, v, w}, E = {e₁, e₂, e₃}

​

u

v

w

e₁

e₂

e₃

Definitions – Types of Graphs

Pseudograph: G(V,E), consists of set of vertices V, set of Edges E and a function F from E to {{u, v}| u, v Î V}. Loops allowed in such a graph.

Representation Example: V = {u, v, w}, E = {e₁, e₂, e₃, e₄}

​

​

u

v

w

e₁

e₃

e₂

e₄

Definitions – Types of Graphs

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

w

v

Definitions – Types of Graphs

Directed Multigraph: G(V,E), consists of set of vertices V, set of Edges E and a function f from E to {{u, v}| u, v V}. The edges e1 and e2 are multiple edges if f(e1) = f(e2)

Representation Example: V = {u, v, w}, E = {e₁, e₂, e₃, e₄}

u

w

v

e₁

e₂

e₃

e₄

Definitions – Types of Graphs

​

​

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 (k) = 0

​

Representation Example: For V = {u, v, w} , E = { {u, w}, {u, v} }, deg (u) = 2, deg (v) = 1, deg (w) = 1, deg (k) = 0, w and v are pendant , k is isolated

u

k

w

v

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

​

Note: A loop contributes 1 to both in-degree and out-degree (why?)

​

Representation Example: For V = {u, v, w} , E = { (u, w), ( v, w), (u, v) }, deg^- (u) = 0, deg⁺ (u) = 2, deg^- (v) = 1,

deg⁺ (v) = 1, and deg^- (w) = 2, deg⁺ (u) = 0

​

u

w

v

Theorems: Undirected Graphs

Theorem 1

The Handshaking theorem:

(why?) Every edge connects 2 vertices

​

Theorems: Undirected Graphs

Theorem 2:

An undirected graph has even number of vertices with odd degree

Simple graphs – special cases

• Complete graph: K_n, is the simple graph that contains exactly one edge between each pair of distinct vertices.

Representation Example: K₁, K₂, K₃, K₄

K₂

K₁

K₄

K₃

Simple graphs – special cases

• Cycle: C_n, n ≥ 3 consists of n vertices v₁, v₂, v₃ … v_n and edges {v₁, v₂}, {v₂, v₃}, {v₃, v₄} … {v_n-1, v_n}, {v_n, v₁}

Representation Example: C₃, C₄

C₃

C₄

Bipartite graphs

• In a simple graph G, if V can be partitioned into two disjoint sets V₁ and V₂ such that every edge in the graph connects a vertex in V₁ and a vertex V₂ (so that no edge in G connects either two vertices in V₁ or two vertices in V₂)

Application example: Representing Relations

Representation example: V₁ = {v₁, v₂, v₃} and V₂ = {v₄, v₅, v₆},

v₁

v₂

v₃

v₄

v₅

v₆

V₁

V₂

Complete Bipartite graphs

• K_m,n is the graph that has its vertex set portioned into two subsets of m and n vertices, respectively There is an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset.

Representation example: K_2,3, K_3,3

K_2,3

K_3,3

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}}, H₁ , H₂

u

v

w

u

u

w

v

v

H₁

H₂

G

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

v

w

w

v

w

u

G1

G2

G

Representation

• Incidence (Matrix): Most useful when information about edges is more desirable than information about vertices.

​

• Adjacency (Matrix/List): Most useful when information about the vertices is more desirable than information about the edges. These two representations are also most popular since information about the vertices is often more desirable than edges in most applications

Representation- Incidence Matrix

• G = (V, E) be an unditected graph. Suppose that v₁, v₂, v₃, …, v_n are the vertices and e₁, e₂, …, e_m are the edges of G. Then the incidence matrix with respect to this ordering of V and E is the nx m matrix M = [m _ij], where

​

​

​

​

​

Can also be used to represent :

Multiple edges: by using columns with identical entries, since these edges are incident with the same pair of vertices

Loops: by using a column with exactly one entry equal to 1, corresponding to the vertex that is incident with the loop

Representation- Incidence Matrix

• Representation Example: G = (V, E)

v

w

u

e1

e3

e2

Representation- Adjacency Matrix

• There is an N x N matrix, where |V| = N , the Adjacenct Matrix (NxN) A = [a_ij]

​

For undirected graph

​

​

​

​

​

​

• For directed graph

​

​

​

​

​

​

• This makes it easier to find subgraphs, and to reverse graphs if needed.

​

​

Representation- Adjacency Matrix

• Adjacency is chosen on the ordering of vertices. Hence, there as are as many as n! such matrices.
• The adjacency matrix of simple graphs are symmetric (a_ij = a_ji) (why?)
• When there are relatively few edges in the graph the adjacency matrix is a sparse matrix
• Directed Multigraphs can be represented by using aij = number of edges from v_i to v_j

​

Representation- Adjacency Matrix

• Example: Undirected Graph G (V, E)

u

v

w

Representation- Adjacency Matrix

• Example: directed Graph G (V, E)

u

v

w

Graph - Isomorphism

• G1 = (V1, E2) and G2 = (V2, E2) are isomorphic if:
• There is a one-to-one and onto function f from V1 to V2 with the property that
• a and b are adjacent in G1 if and only if f (a) and f (b) are adjacent in G2, for all a and b in V1.
• Function f is called isomorphism

Application Example:

In chemistry, to find if two compounds have the same structure

Graph - Isomorphism

Representation example: G1 = (V1, E1) , G2 = (V2, E2)

f(u₁) = v₁, f(u₂) = v₄, f(u₃) = v₃, f(u₄) = v₂,

u₁

u₃

u₄

u₂

v₃

v₄

v₁

v₂

​

​

• Thank You