Graphs and Their Models
Graphs
Graphs
9.1 Graphs and Graph Models
M
.
A
L
-
T
O
W
A
I
L
E
B
1
DEFINITION 1
•
A graph G = ( V , E) consists of V, a nonempty set of
vertices (or
nodes)
and E, a set of
edges.
•
Each edge has either one or two vertices associated with it, called
its endpoints.
•
An edge is said to connect its endpoints.
•
A graph with an infinite vertex set is called an
infinite graph.
•
a graph with a finite vertex set is called a
finite graph.
Graphs and Graph Models
M
.
A
L
-
T
O
W
A
I
L
E
B
2
•
Simple graph:
A graph in which each edge connects two different
vertices and where no two edges connect the same pair of vertices.
•
Multiple graph:
Graphs that may have multiple edges connecting
the same vertices.
•
Loop
is a closed curve whose initial and final vertices coincide.
•
Pseudographs :
Graphs that may include loops, (and possibly
multiple edges connecting the same pair of vertices).
M
.
A
L
-
T
O
W
A
I
L
E
B
3
Directed & Undirected Graphs
Definition2
•
A directed graph (or digraph) ( V,E) consists of a nonempty
set of vertices V and a set of directed edges (or arcs) E.
•
Each directed edge is associated with an ordered pair of
vertices.
•
The directed edge associated with the ordered pair (u ,v) is
said to start at u and end at v.
M
.
A
L
-
T
O
W
A
I
L
E
B
4
•
simple directed graph
a directed graph that has no loops and has
no multiple directed edges.
•
Directed multigraphs
: directed graphs that may have multiple
directed edges.
•
Edge of multiplicity m
When there are
m directed edges
, each
associated to an ordered pair of vertices (u,v).
•
Mixed graph
: a graph with both directed and undirected edges.
Types of Directed & Undirected Graphs
.
M
.
A
L
-
T
O
W
A
I
L
E
B
5
Homework
Homework
Page 596
•
3
•
4
•
5
•
7
•
9
M
.
A
L
-
T
O
W
A
I
L
E
B
6
9.2 Graph Terminology and
9.2 Graph Terminology and
Special Types of Graphs
Special Types of Graphs
M
.
A
L
-
T
O
W
A
I
L
E
B
7
Basic Terminology
DEFINITION 1
•
Two
vertices
u and v in an undirected graph G are called
adjacent
(or
neighbors
) in G if u and v are endpoints of an
edge of G .
•
If e is associated with {u,v}, the edge
e is called
incident
with the vertices u and v.
•
The
edge
e is also said to
connect
u and v.
•
The
vertices
u and v are called
endpoints
of an edge
associated with { u , v}.M
.
A
L
-
T
O
W
A
I
L
E
B
8
The degree of a vertex
DEFINITION 2
•
The degree of a vertex in an
undirected
graph is the
number of edges incident with it
, except
that a loop at a vertex contributes twice
to the degree of
that vertex.
•
The degree of the vertex v is denoted by
deg(v).
•
A vertex of
degree zero
is called
isolated
.
•
A vertex is
pendant
if and only if it has
degree one.
M
.
A
L
-
T
O
W
A
I
L
E
B
9
Example 1
:
What are the degrees of the vertices in the graphs G and H displayed
in Figure 1?
Solution:
In G:
deg(a) = 2 , deg(b) = deg(c) = deg(f ) = 4 , deg(d ) = 1 ,
deg(e) = 3 , and deg(g) = O.
In H:
deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1 , and deg(d ) = 5 .
M
.
A
L
-
T
O
W
A
I
L
E
B
10
10
•
A vertex of
degree zero
is called
isolated
.
•
It follows that an isolated vertex is not adjacent to any
vertex.
•
Vertex g in graph G in Example 1 is isolated.
•
A vertex is
pendant
if and only if it has
degree one.
•
Consequently, a pendant vertex is adjacent to exactly
one other vertex.
•
Vertex d in graph G in Example 1 is pendant.
M
.
A
L
-
T
O
W
A
I
L
E
B
11
11
T
T
H
H
E
E
H
H
A
A
N
N
D
D
S
S
H
H
A
A
K
K
I
I
N
N
G
G
T
T
H
H
E
E
O
O
R
R
E
E
M
M
THEOREM 1
Let G = (V, E) be an
undirected graph
with e
edges. Then 2e = ∑
v
ϵ
V
deg(v).
(Note that this applies even if multiple edges and
loops are present.)
M
.
A
L
-
T
O
W
A
I
L
E
B
12
12
EXAMPLE 3
How many edges are there in a graph with 1 0
vertices each of degree 6?
Solution:
Because the sum of the degrees of the vertices is 6 ·
1 0x6 = 60,
it follows that 2e = 60.
Therefore, e = 30.
M
.
A
L
-
T
O
W
A
I
L
E
B
13
13
THEOREM 2
An undirected graph has an
even
number of
vertices
of
odd degree.
M
.
A
L
-
T
O
W
A
I
L
E
B
14
14
DEFINITION 3
•
When (u ,v) is an edge of the graph G with
directed edges
, u is said to be
adjacent to
v and v
is said to be adjacent from u.
•
The vertex u is called
the initial vertex
of (u,v),
and v is called
the terminal or end vertex
of (u,v).
•
The initial vertex and terminal vertex of a loop
are the same.
M
.
A
L
-
T
O
W
A
I
L
E
B
15
15
In-degree & Out-degree
(directed graph)
(directed graph)
DEFINITION 4
•
In a graph with
directed edges
the
in-degree
of a vertex
v, denoted by
deg
-
(v)
, is the number of edges with v as
their
terminal vertex
.
•
The
out-degree
of v, denoted by
deg
+
(v),
is the number
of edges with v as
their initial vertex.
•
(Note that a loop at a vertex contributes 1 to
both the in-
degree and the out-degree
of this vertex.)
M
.
A
L
-
T
O
W
A
I
L
E
B
16
16
EXAMPLE 4
Find the in-degree and out-degree of each vertex in the graph G with
directed edges shown in Figure 2 .
Solution:
The in-degrees in G
are deg
-
(a)=2, deg
-
(b)=2, deg
-
(c)=3, deg
-
(d)=2,
deg
-
(e)=3, and deg
-
(f)=0.
The out-degrees
are deg
+
(a)=4, deg
+
(b)=1, deg
+
(c)=2,deg
+
(d)=2,
deg
+
(e)=3, and deg
+
(f) =0.
M
.
A
L
-
T
O
W
A
I
L
E
B
17
17
THEOREM 3
Let G = (V,E) b e a graph with
directed edges
.
Then:
∑
v
ϵ
V
deg
-
(v)= ∑
v
ϵ
V
deg
+
(v)=|E|.
M
.
A
L
-
T
O
W
A
I
L
E
B
18
18
Some Special Simple Graphs
Some Special Simple Graphs
EXAMPLE 5
Complete Graphs
The complete graph on n vertices,
denoted by K
n
, is the
simple graph
that contains exactly one edge between each pair of
distinct vertices.
The graphs K
n
, for n=1,2,3,4,5,6, are displayed in
Figure 3.
M
.
A
L
-
T
O
W
A
I
L
E
B
19
19
EXAMPLE 6
Cycles
The cycle C
n
≥3, consists of n vertices V
1
,
V
2
, . . . , V
n
and edges { V1
, V
2
} , { V2
,V
3
} , . . . ,
{ Vn-1
, V
n
} , and { Vn
,V
1
} .
The cycles C
3
,C
4
, C
5
, and C
6
are displayed in
Figure 4.
M
.
A
L
-
T
O
W
A
I
L
E
B
20
20
EXAMPLE 7
Wheels
We obtain the wheel W
n
when we add
an additional vertex to the cycle C
n
, for n≥3 ,
and connect this new vertex to each of the n
vertices in C
n
, by new edges.
The wheels W
3
, W
4
,W
5
, and W
6
are displayed
in Figure 5 .
21
21
How many vertices & edges in each
How many vertices & edges in each
type?
type?
M
.
A
L
-
T
O
W
A
I
L
E
B
22
22
Bipartite Graphs
DEFINITION 5
A
simple graph
G is called
bipartite
if its vertex set V can be
partitioned into two disjoint sets V
1
and V
2
such that every
edge in the graph connects a vertex in V
1
and a vertex in V
2
.
(so that no edge in G connects either two vertices in V
1
or two
vertices in V
2
).
When this condition holds, we call the pair (V
1
,V
2
) a
bipartition
of the vertex set V of G .
M
.
A
L
-
T
O
W
A
I
L
E
B
23
23
EXAMPLE 11
Are the graphs G and H displayed in Figure 8 bipartite?
Solution:
Graph G is bipartite
because its vertex set is the union of two disjoint sets, {a ,b,d} and {c, e, j,g}, and each edge connects a vertex in one of these subsets to a vertex in the other subset.
(Note that for G to be bipartite it is not necessary that every vertex in {a ,b,d} be adjacent toevery vertex in {c,e,j, g}. For instance, b and g are not adjacent.)Graph H is not bipartite
because its vertex set cannot be partitioned into two subsets so that
edges do not connect two vertices from the same subset. verify this by (consider the
vertices a , b, and j.)
M
.
A
L
-
T
O
W
A
I
L
E
B
24
24
H
H
o
o
m
m
e
e
w
w
o
o
r
r
k
k
Page 608
•
1
•
2
•
3
•
7
•
8
•
9
•
10
•
29(a,b,c)
•
37(a,b,d,e,f).
M
.
A
L
-
T
O
W
A
I
L
E
B
25
25
9.4 Connectivity
9.4 Connectivity
M
.
A
L
-
T
O
W
A
I
L
E
B
26
26
Paths
Informally,
a path
is a
sequence of edges
that begins at a vertex of a graph and
travels from vertex to vertex along edges of the graph.
Definition 1
•
Let n be a nonnegative integer and G an undirected graph.
A path of length n
from u to v in G is a sequence of n edges e
1
, . . . , e
n
of G such that e
1
is
associated with {x0
, x
1
}, e
2
is associated with {X1
, X
2
} , and so on, with e
n
associated with {xn-1
, x
n
}, where X
0
= u and X
n
=v.
•
When the graph is simple, we denote this path by its vertex sequence X
0
,X
1
,…,
Xn (because listing these vertices uniquely determines the path).
The path is a
circuit
if it begins and ends at the same vertex, that is, if u = v, and has
length greater than zero.
•
The path or circuit is said to
pass through the vertices
X
1
, X
2
, . . . , X
n-l
or
traverse the edges
e
1
, e
2
, . . . , e
n
.
•
A path or circuit is simple
if it does not contain the same edge more than once.
M
.
A
L
-
T
O
W
A
I
L
E
B
27
27
Remark:
•
in some books, the term
walk
is used instead of
path
, where a
walk
is defined to be an alternating sequence of vertices and edges of a
graph, V
0
, e
1
,V
1
, e
2
,… , V
n-1
, e
n
, V
n
, where V
i-1
and V
i
are the
endpoints of e
i
for i=1,2,…,n .
•
When this terminology is used,
closed walk
is used instead of
circuit
to indicate a walk that begins and ends at the same vertex,
•
and
trail
is used to denote a walk that has no repeated
edge (replacing the term
simple path
).
When this terminology is used, the terminology path
is often used for a trail with no repeated vertices.
M
.
A
L
-
T
O
W
A
I
L
E
B
28
28
EXAMPLE 1
•
In the simple graph shown in Figure 1 ,
a,d,c,f,e
is a
simple
path of length 4
,
because {a,d}, {d,c } , {c,f}, and {f,e} are alledges.
•
However,
d,e,c,a
is
not a path
, because {e,c} is not an edge.•
Note that
b, c, f, e, b
is a
circuit of length 4
because {b, c},{c,f}, {f, e}, and {e, b} are edges, and this path begins and endsat b.
•
The path
a, b, e, d, a, b
, which
is of length 5
, is
not simple
because it contains the edge {a,b} twice.29
29
DEFINITION 2
Let n be a nonnegative integer and G a
directed graph
.
•
A path of length n from u to v
in G is a sequence of edges e
1
,e
2
,..,e
n
of G such that e
1
is associated with (x
0
,x
1
), e
2
is associated with (x
1
,
x
2
), and so on, with e
n
associated with (x
n-1
,x
n
), where x
0
= u and x
n
= v.
•
When there are no multiple edges in the directed graph, this path is
denoted by its vertex sequence x
0
, x
1
, x
2
, …, x
n
.
•
A path of length greater than zero that begins and ends at the same
vertex is called
a circuit or cycle
.
•
A path or circuit is called
simple
if it does not contain the same edge
more than once.
M
.
A
L
-
T
O
W
A
I
L
E
B
30
30
Connectedness In Undirected Graphs
DEFINITION 3
An
undirected graph
is called
connected
if
there is a path between every pair of distinct
vertices of the graph.
M
.
A
L
-
T
O
W
A
I
L
E
B
31
31
EXAMPLE 5
•
The graph G
1
in Figure 2 is
connected
, because for every
pair of distinct vertices there is a path between them.
•
However, the graph G
2
in Figure 2 is
not connected
.
•
For instance, there is no path in G
2
between vertices
a
and d.
M
.
A
L
-
T
O
W
A
I
L
E
B
32
32
Homework
Page 629
•
1(a,b,c,d)
•
3
M
.
A
L
-
T
O
W
A
I
L
E
B
33
33
Explore the world of graphs through definitions, types, and special features. Learn about vertices, edges, simple and multiple graphs, directed and undirected graphs, and more. Discover the terminology and special types of graphs along with basic concepts and properties.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Graphs 9.1 Graphs and Graph Models 1 M. AL-TOWAILEB
Graphs and Graph Models DEFINITION 1 A graph G = ( V , E) consists of V, a nonempty set of vertices (or nodes) and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints. A graph with an infinite vertex set is called an infinite graph. a graph with a finite vertex set is called a finite graph. M. AL-TOWAILEB 2
Simple graph: A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices. Multiple graph: Graphs that may have multiple edges connecting the same vertices. Loop is a closed curve whose initial and final vertices coincide. a Pseudographs : Graphs that may include loops, (and possibly multiple edges connecting the same pair of vertices). 3 M. AL-TOWAILEB
Directed & Undirected Graphs Definition2 A directed graph (or digraph) ( V,E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u ,v) is said to start at u and end at v. 4 M. AL-TOWAILEB
Types of Directed & Undirected Graphs simple directed graph a directed graph that has no loops and has no multiple directed edges. Directed multigraphs: directed graphs that may have multiple directed edges. Edge of multiplicity m When there are m directed edges, each associated to an ordered pair of vertices (u,v). Mixed graph: a graph with both directed and undirected edges. . M. AL-TOWAILEB 5
Homework Page 596 3 4 5 7 9 M. AL-TOWAILEB 6
9.2 Graph Terminology and Special Types of Graphs M. AL-TOWAILEB 7
Basic Terminology DEFINITION 1 Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge of G . If e is associated with {u,v}, the edge e is called incident with the vertices u and v. The edge e is also said to connect u and v. The vertices u and v are called endpoints of an edge associated with { u , v}. M. AL-TOWAILEB 8
The degree of a vertex DEFINITION 2 The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by deg(v). A vertex of degree zero is called isolated. A vertex is pendant if and only if it has degree one. M. AL-TOWAILEB 9
Example 1: What are the degrees of the vertices in the graphs G and H displayed in Figure 1? Solution: In G: deg(a) = 2 , deg(b) = deg(c) = deg(f ) = 4 , deg(d ) = 1 , deg(e) = 3 , and deg(g) = O. In H: deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1 , and deg(d ) = 5 . M. AL-TOWAILEB 10
A vertex of degree zero is called isolated. It follows that an isolated vertex is not adjacent to any vertex. Vertex g in graph G in Example 1 is isolated. A vertex is pendant if and only if it has degree one. Consequently, a pendant vertex is adjacent to exactly one other vertex. Vertex d in graph G in Example 1 is pendant. M. AL-TOWAILEB 11
THE HANDSHAKING THEOREM THEOREM 1 Let G = (V, E) be an undirected graph with e edges. Then 2e = v V deg(v). (Note that this applies even if multiple edges and loops are present.) M. AL-TOWAILEB 12
EXAMPLE 3 How many edges are there in a graph with 1 0 vertices each of degree 6? Solution: Because the sum of the degrees of the vertices is 6 1 0x6 = 60, it follows that 2e = 60. Therefore, e = 30. M. AL-TOWAILEB 13
THEOREM 2 An undirected graph has an even number of vertices of odd degree. M. AL-TOWAILEB 14
DEFINITION 3 When (u ,v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u. The vertex u is called the initial vertex of (u,v), and v is called the terminal or end vertex of (u,v). The initial vertex and terminal vertex of a loop are the same. M. AL-TOWAILEB 15
In-degree & Out-degree (directed graph) DEFINITION 4 In a graph with directed edges the in-degree of a vertex v, denoted by deg-(v), is the number of edges with v as their terminal vertex. The out-degree of v, denoted by deg+(v), is the number of edges with v as their initial vertex. (Note that a loop at a vertex contributes 1 to both the in- degree and the out-degree of this vertex.) M. AL-TOWAILEB 16
EXAMPLE 4 Find the in-degree and out-degree of each vertex in the graph G with directed edges shown in Figure 2 . Solution: The in-degrees in G are deg-(a)=2, deg-(b)=2, deg-(c)=3, deg-(d)=2, deg-(e)=3, and deg-(f)=0. The out-degrees are deg+(a)=4, deg+(b)=1, deg+(c)=2,deg+(d)=2, deg+(e)=3, and deg+(f) =0. M. AL-TOWAILEB 17
THEOREM 3 Let G = (V,E) b e a graph with directed edges. Then: v V deg-(v)= v V deg+(v)=|E|. M. AL-TOWAILEB 18
Some Special Simple Graphs EXAMPLE 5 Complete Graphs The complete graph on n vertices, denoted by Kn, is the simple graph that contains exactly one edge between each pair of distinct vertices. The graphs Kn, for n=1,2,3,4,5,6, are displayed in Figure 3. M. AL-TOWAILEB 19
EXAMPLE 6 Cycles The cycle Cn 3, consists of n vertices V1, V2, . . . , Vnand edges { V1, V2} , { V2,V3} , . . . , { Vn-1, Vn} , and { Vn,V1} . The cycles C3,C4, C5, and C6are displayed in Figure 4. M. AL-TOWAILEB 20
EXAMPLE 7 Wheels We obtain the wheel Wnwhen we add an additional vertex to the cycle Cn, for n 3 , and connect this new vertex to each of the n vertices in Cn, by new edges. The wheels W3, W4,W5, and W6are displayed in Figure 5 . 21
How many vertices & edges in each type? Type of the Simple Graph Number of Vertices Number of Edges ?(? ?) ? n Kn n Cn n Wn n+1 2n M. AL-TOWAILEB 22
Bipartite Graphs DEFINITION 5 A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V1and V2such that every edge in the graph connects a vertex in V1and a vertex in V2. (so that no edge in G connects either two vertices in V1or two vertices in V2). When this condition holds, we call the pair (V1,V2) a bipartition of the vertex set V of G . M. AL-TOWAILEB 23
EXAMPLE 11 Are the graphs G and H displayed in Figure 8 bipartite? Solution: Graph G is bipartite because its vertex set is the union of two disjoint sets, {a ,b,d} and {c, e, j, g}, and each edge connects a vertex in one of these subsets to a vertex in the other subset. (Note that for G to be bipartite it is not necessary that every vertex in {a ,b,d} be adjacent to every vertex in {c,e,j, g}. For instance, b and g are not adjacent.) Graph H is not bipartite because its vertex set cannot be partitioned into two subsets so that edges do not connect two vertices from the same subset. verify this by (consider the vertices a , b, and j.) M. AL-TOWAILEB 24
Homework Page 608 1 2 3 7 8 9 10 29(a,b,c) 37(a,b,d,e,f). M. AL-TOWAILEB 25
9.4 Connectivity M. AL-TOWAILEB 26
Paths Informally, a path is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph. Definition 1 Let n be a nonnegative integer and G an undirected graph. A path of length n from u to v in G is a sequence of n edges e1, . . . , enof G such that e1is associated with {x0, x1}, e2is associated with {X1, X2} , and so on, with en associated with {xn-1, xn}, where X0= u and Xn=v. When the graph is simple, we denote this path by its vertex sequence X0,X1, , Xn (because listing these vertices uniquely determines the path). The path is a circuit if it begins and ends at the same vertex, that is, if u = v, and has length greater than zero. The path or circuit is said to pass through the vertices X1, X2, . . . , Xn-l or traverse the edges e1, e2, . . . , en. 27 A path or circuit is simple if it does not contain the same edge more than once. M. AL-TOWAILEB
Remark: in some books, the term walk is used instead of path, where a walk is defined to be an alternating sequence of vertices and edges of a graph, V0, e1,V1, e2, , Vn-1, en, Vn, where Vi-1and Viare the endpoints of eifor i=1,2, ,n . When this terminology is used, closed walk is used instead of circuit to indicate a walk that begins and ends at the same vertex, and trail is used to denote a walk that has no repeated edge (replacing the term simple path). When this terminology is used, the terminology path is often used for a trail with no repeated vertices. M. AL-TOWAILEB 28
EXAMPLE 1 In the simple graph shown in Figure 1 , a,d,c,f,e is a simple path of length 4, because {a,d}, {d,c } , {c,f}, and {f,e} are all edges. However, d,e,c,a is not a path, because {e,c} is not an edge. Note that b, c, f, e, b is a circuit of length 4 because {b, c}, {c,f}, {f, e}, and {e, b} are edges, and this path begins and ends at b. The path a, b, e, d, a, b, which is of length 5, is not simple because it contains the edge {a,b} twice. 29
DEFINITION 2 Let n be a nonnegative integer and G a directed graph. A path of length n from u to v in G is a sequence of edges e1,e2,..,en of G such that e1is associated with (x0,x1), e2is associated with (x1, x2), and so on, with enassociated with (xn-1,xn), where x0= u and xn= v. When there are no multiple edges in the directed graph, this path is denoted by its vertex sequence x0, x1, x2, , xn. A path of length greater than zero that begins and ends at the same vertex is called a circuit or cycle. A path or circuit is called simple if it does not contain the same edge more than once. M. AL-TOWAILEB 30
Connectedness In Undirected Graphs DEFINITION 3 An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph. M. AL-TOWAILEB 31
EXAMPLE 5 The graph G1in Figure 2 is connected, because for every pair of distinct vertices there is a path between them. However, the graph G2in Figure 2 is not connected. For instance, there is no path in G2between vertices a and d. M. AL-TOWAILEB 32
Homework Page 629 1(a,b,c,d) 3 M. AL-TOWAILEB 33
