Graph theory presentation

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.Graph theory is also important in real life.

1. Welcome to Discrete Mathematics
PRESENTATION
Topics: Graph Theory

Submited by:
Md: Aliul Kadir akib
Daffodil International University
Mail:[email protected]

2. Introduction
What is a graph G?
It is a pair G = (V, E),
where
V = V(G) = set of vertices
E = E(G) = set of edges
Example:
V = {s, u, v, w, x, y, z}
E = {(x,s), (x,v), (x,v), (x,u),
(v,w), (s,v), (s,u), (s,w), (s,y),
(w,y), (u,y), (u,z),(y,z)}

3. Special edges
Parallel edges
Two or more edges
joining a pair of vertices
in the example, a and b
are joined by two parallel
edges
Loops
An edge that starts and
ends at the same vertex
In the example, vertex d
has a loop

4. Special graphs
Simple graph
A graph without loops
or parallel edges.
Weighted graph
A graph where each
edge is assigned a
numerical label or
“weight”.

5. Directed graphs (digraphs)

G is a directed graph or
digraph if each edge
has been associated
with an ordered pair
of vertices, i.e. each
edge has a direction

6. 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
Representation Example: For V = {u, v, w} , E = { {u, w}, {u, w}, (u,
v) }, deg (u) = 2, deg (v) = 1, deg (w) = 1, deg (k) = 0, w and v are
pendant , k is isolated

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

8. Theorems: Undirected Graphs
Theorem 1
The Handshaking theorem:

(why?) Every edge connects 2 vertices
å
Î
=
Vv
ve2

9. Theorems: Undirected Graphs
Theorem 2:
An undirected graph has even number of vertices
with odd degree
even
Voof
=Þ
Þ
Þ
ÎÞ
+==
å
ååå
Î
ÎÎÎ
2
21
V v
1,
V vV u V v
deg(v) termsecond
even also is termsecond Hence
2e. is sum sinceeven is inequalitylast the
of side handright on the termslast two theof sum The
even. is inequalitylast theof side handright in the first term The
V for veven is (v) deg
deg(v) deg(u) deg(v) 2e
verticesdegree odd torefers V2 and verticesdegreeeven ofset theis 1 Pr

10. Definitions – Graph Type

11. Simple graphs – special cases
Wheels: W
n
, obtained by adding additional
vertex to Cn and connecting all vertices to
this new vertex by new edges.
Representation Example: W
3
, W
4

12. Complete graph K
n
Let n > 3
The complete graph K
n
is
the graph with n vertices
and every pair of vertices
is joined by an edge.
The figure represents K
5

13. Bipartite graphs
A bipartite graph G is a
graph such that
V(G) = V(G
1
) È V(G
2
)
|V(G
1
)| = m, |V(G
2
)| = n
V(G
1
) ÇV(G
2
) = Æ
No edges exist between
any two vertices in the
same subset V(G
k
), k =
1,2

14. Complete bipartite graph K
m,n
A bipartite graph is the
complete bipartite graph K
m,n
if
every vertex in V(G
1
) is joined
to a vertex in V(G
2
) and
conversely,
|V(G
1
)| = m
|V(G
2
)| = n

15. Connected graphs
A graph is connected if
every pair of vertices
can be connected by a
path
Each connected
subgraph of a non-
connected graph G is
called a component of G

16. Paths and cycles
A path of length n is a
sequence of n + 1
vertices and n
consecutive edges
A cycle is a path that
begins and ends at
the same vertex

17. Euler cycles
An Euler cycle in a graph G is a
simple cycle that passes through
every edge of G only once.
The Konigsberg bridge problem:
Starting and ending at the same point, is it
possible to cross all seven bridges just
once and return to the starting point?
This problem can be represented
by a graph
Edges represent bridges and
each vertex represents a region.

18. Degree of a vertex
The degree of a vertex
v, denoted by d(v), is
the number of edges
incident on v
Example:
d(a) = 4, d(b) = 3,
d(c) = 4, d(d) = 6,
d(e) = 4, d(f) = 4,
d(g) = 3.

19. Sum of the degrees of a graph
Theorem : If G is a graph with m edges and n
vertices v
1
, v
2
,…, v
n
, then

n
S d(v
i
) = 2m

i = 1
In particular, the sum of the degrees of all the
vertices of a graph is even.

20. Shortest Path Problems
•Directed weighted graph.
•Path length is sum of weights of edges on path.
•The vertex at which the path begins is the source
vertex.
•The vertex at which the path ends is the
destination vertex.
0
3 9
5 11
3
6
5
7
6
s
t x
y z
2
2 1
4
3

21. Example
1
2
3
4
5
6
7
2
6
16
7
8
10
3
14
4
4
5 3
1
•A shorter path will cost only 11

22. Representations of graphs
Adjacency matrix
Rows and columns are
labeled with ordered
vertices
write a 1 if there is an edge
between the row vertex
and the column vertex
and 0 if no edge exists
between them
vwxy
v0101
w1011
x0101
y1110

23. Euler’s formula
If G is planar graph,
v = number of vertices
e = number of edges
f = number of faces,
including the exterior face
Then: v – e + f = 2