Scribd
Upload
9 views66 pages

Graph Theory Concepts and Applications

Module 6 focuses on Graph Theory, covering various types of graphs, their representations, and key concepts such as subgraphs, connectivity, and isomorphism. It includes examples and applications of Euler and Hamiltonian graphs, as well as planar graphs and operations on graphs. The module is designed to provide a foundational understanding of graph structures and their significance in computer networks.

Uploaded by

siddharthchillapwar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views66 pages

Graph Theory Concepts and Applications

Module 6 focuses on Graph Theory, covering various types of graphs, their representations, and key concepts such as subgraphs, connectivity, and isomorphism. It includes examples and applications of Euler and Hamiltonian graphs, as well as planar graphs and operations on graphs. The module is designed to provide a foundational understanding of graph structures and their significance in computer networks.

Uploaded by

siddharthchillapwar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Module 6 - Graph Theory

CE– SE–DSGT
Dr. Anil Kale
Associate Professor
Dept. of Computer Engineering,
MGMCET, Navi Mumbai

1
Module 6 - Graph Theory
Types of graphs, Graph Representation, Sub graphs, Operations
on Graphs, Walk, Path, Circuit, Connected Graphs, Disconnected
Graph, Components, Homomorphism and Isomorphism of
Graphs, Euler and Hamiltonian Graphs, Planar Graph, Cut Set,
Cut Vertex, Applications.
Graph Theory
Definition

3
Now suppose that a network is made up of data centers and communication links
between computers. We can represent the location of each data center by a point and
each communications link by a line segment, as shown in Figure 1.
This computer network can be modeled using a graph in which the vertices of the
graph represent the data centers and the edges represent communication links. In
general, we visualize graphs by using points to represent vertices and line segments,
possibly curved, to represent edges, where the endpoints of a line segment
representing an edge are the points representing he endpoints of the edge.

4
Types of graphs
Basic Terminology

5
6
7
EXAMPLE 2:

How many edges are there in a graph with 10 vertices each of degree six?

Solution: Because the sum of the degrees of the vertices is 6 ⋅ 10 = 60, it follows
that 2m = 60 where m is the number of edges. Therefore, m = 30.

8
9
10
Bipartite Graphs

11
12
13
Graph Representation

14
15
Adjacency Matrices

16
17
Incidence Matrices

18
19
Sub graphs
Definition

20
Operations on Graphs

21
22
Definition

EXAMPLE

23
24
Connectivity
Paths

25
Connectedness in Undirected Graphs

26
EXAMPLE

27
28
Isomorphism of Graphs

EXAMPLE: 1
Show that the graphs G = (V, E) and H = (W, F), displayed in Figure 8, are isomorphic.

29
30
Determining whether Two Simple Graphs are
Isomorphic

EXAMPLE : Show that the graphs displayed in Figure 9 are not isomorphic.

31
32
EXAMPLE: Determine whether the graphs shown in Figure 10 are isomorphic.

33
34
35
36
Path Example

37
38
How Connected is a Graph?

39
40
Planar Graphs

Dr. Rajesh Kadu 41


42
43
44
45
46
Euler Paths and Circuits

47
48
49
50
51
52
53
54
55
Applications of Hamilton Circuits

56
Cut Set, Cut Vertex

57
58
59
60
61
62
64
65
66

You might also like