Graph Theory

Ms. G. Gowri

Assistant Professor of Computer Science

C.P.A. College

Bodinayakanur.

Varying Applications (examples)

• 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

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.

​

​

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

​

​

​

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

​

u

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: 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 – Graph Type

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 – 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

w

v

Definitions – Graph Type

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 – Graph Type

​

​

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

THANK YOU