Transcript Graphs

Graphs
Discrete Structure CS203
Uses of Graph in CS
A graph is a set of vertices (or nodes)
represented by circles
which are connected
by edges, represented by line segments
.
Car navigation system
Efficient database
computer network
Representing computational models
Transportation networks
Graph terminology often derived from
transportation metaphors

E.g. “shortest path“, “flow“, “diameter“
A structural network
The physics of rigidity theory is applied
at every network node to design stable
structures
An electrical network
The physics of Kirchoff‘s laws is applied
at every network node and closed paths
to design circuits
Introduction to graph theory
 Begun in 1735
 Bridges of Konigsberg (today’s Kaliningrad):
walk all 7 bridges without crossing a bridge twice
1
6
2
5
3
4
7
Solved by: parity of node
6
6
Graph Theory - History
Leonhard Euler's paper on
“Seven Bridges of
Königsberg” ,
published in 1736.
Famous problems
“The traveling salesman
problem”

A traveling salesman is to visit
a number of cities; how to
plan the trip so every city is
visited once and just once and
the whole trip is as short as
possible ?
Graph Theory
Euler
Trails and Circuits
Ex. The Seven Bridge of Konigsberg
area a
area b
area d
area c
a
b
c
Find a way to walk about the city so as
to cross each bridge exactly once and
d
then return to the
starting point.
Pencil Drawing Problem
-Euler Paths
Which of the following pictures can be
drawn on paper without ever lifting the
pencil and without retracing over any
segment?
Introduction to graph theory
Graph – mathematical object consisting
of a set of:
V = nodes (vertices, points).
E = edges (links, arcs) between pairs of
nodes.
Denoted by G = (V, E).
Captures pairwise relationship between
objects.
Graph size parameters: n = |V|, m =
|E|.
11
Introduction to graph theory
 Graph – mathematical object consisting of a set of:
 V = nodes (vertices, points).
 E = edges (links, arcs) between pairs of nodes.
Denoted by G = (V, E).
Captures pairwise relationship between objects.
Graph size parameters: n = |V|, m = |E|.
V = { 1, 2, 3, 4, 5, 6, 7, 8 }
E = { {1,2}, {1,3}, {2,3}, {2,4}, {2,5}, {3,5}, {3,7}, {3,8}, {4,5}, {5
n=8
m = 11
12
Directed Graph (digraph)
Edges have directions

An edge is an ordered pair of
nodes
loop
multiple arc
arc
node
Graph Theory
Undirected graph
Directed graph
loop
isolated vertex
multiple
edges
G=(V,E)
simple graph: an undirected graph without loop or multiple edges
degree of a vertex: number of edges connected
(indegree, outdegree)
The number of odd degree vertices is even
Graph
1
e3
e1
e2
3
2
e4 e5
e6
4
Edge-labels distinguish between edges
sharing same endpoints. Labeling can be
thought of as function:
e1  {1,2}, e2  {1,2}, e3  {1,3},
e4  {2,3}, e5  {2,3}, e6  {1,2}
Digraphs
A: Each edge is directed so an ordered pair
(or tuple) rather than unordered pair.
2
(1,1)
(2,2)
(2,3)
(1,2)
1 (1,3)
3
(2,4) (3,4)
4
(3,3)
(4,4)
Thus the set of edges E is just the
represented relation on V.
16
Simple graph
Local computer network
1
{1,2}
{1,3}
3
2
{2,3}
{2,4}
{3,4}
4
{1,4}



Has no loops (no “self-communication”)
Has unique connections between computers
Vertices are labeled to associate with particular
computers
Draw the graph with degree 3, 3, 1, 2 &
3, 3, 1, 3
Weighted Graph
A weighted graph is a graph for which each edge has an
associated weight, usually given by a weight function w: E
R
2
2
0.5
1.2
1
0.2
2
4
3
6
3
1
9
2.1
4
8
4
Page Rank
Determine the value
of a page based on
link analysis
Model of randomly
traversing a graph


Weighting factors on
nodes
Damping (random
transitions)
Graph Theory
path: no vertex can be repeated
a-b-c-d-e
trail: no edge can be repeat
a-b-c-d-e-b-d
walk: no restriction
a-b-d-a-b-c
a
e
b
d
c
length: number of edges in this (path,trail,walk)
closed trail: circuit (a-b-c-d-b-e-d-a,
one draw without lifting pen)
closed path: cycle (a-b-c-d-a)
Connected Graph
Let G=(V,E) be an undirected graph. We
call G connected if there is a path
between any two distinct vertices of G.
b
a
e
d
c
b
a
e
disconnected with
two components
d
c
Connectivity
Q: Which of the following graphs are
connected?
1
2
3
4
22
Connectivity in
Directed Graphs
Q: Classify the connectivity of each
graph.
23
English Connectivity Puzzle
Can define a puzzling graph G as follows:
V = {3-letter English words}
E : two words are connected if can get
one word from the other by changing a
single letter.
One small subgraph of G is:
rob
job
jab
Q: Is “fun” connected to “car” ?
Handshaking Theorem
1
e3
e1
e2
3
e6
2
e4
e5
e7
4
There are two ways to count the number of
edges in the above graph:
1. Just count the set of edges: 7
2. Count seeming edges vertex by vertex and
divide by 2 because double-counted edges:
( deg(1)+deg(2)+deg(3)+deg(4) )/2
= (3+7+2+2)/2 = 14/2 = 7
25
Degree sequence
Find a graph with
degree sequence

3, 3, 2, 1, 1
Find a graph with
degree sequence

3, 3, 3, 3, 3
Handshaking Theorem
Lemma: The number of vertices of odd
degree must be even in an undirected
graph.
Proof : Otherwise would have
2|E | = Sum of even no.’s
+ an odd number of odd no.’s
even = even + odd
–this is impossible. •
27
Cycles - Cn
The cycle graph Cn is a closed walk does
not have repeated vertex:
C1
C2
C3
C4
C5
Graph Patterns
Wheels - Wn
The wheel graph Wn is just a cycle graph
with an extra vertex in the middle:
W1
W2
W3
W4
W5
Usually consider wheels with 3 or more
spokes only.
Bipartite Graphs
• A simple graph is bipartite if V can be
partitioned into V = Z1 W2 so that
•
•
•
There is no edge from zi to zj
There is no edge from wi to wj
There is an edge rom vk to wh
• The total degree o any graph is even
Bipartite Graph
A bipartite graph
is an undirected
graph
G = (V,E) in which V
can be partitioned
into 2 sets V1 and V2
such that ( u,v)  E
implies either
u  V1 and v  V2
OR
v  V1 and u  V2.
V1
V2
u1
u2
v1
v2
u3
v3
u4
An example of bipartite graph application to telecommunication problems can be found in,
C.A. Pomalaza-Ráez, “A Note on Efficient SS/TDMA Assignment Algorithms,” IEEE Transactions
on Communications, September 1988, pp. 1078-1082.
For another example of bipartite graph applications see the slides in the Addendum section
Bipartite Graphs
EG: C4 is a bichromatic:
And so is bipartite, if we redraw it:
Bipartite Graphs
EG: C4 is a bichromatic:
And so is bipartite, if we redraw it:
Bipartite Graphs
EG: C4 is a bichromatic:
And so is bipartite, if we redraw it:
Bipartite Graphs
EG: C4 is a bichromatic:
And so is bipartite, if we redraw it:
Bipartite Graphs
EG: C4 is a bichromatic:
And so is bipartite, if we redraw it:
Bipartite Graphs
EG: C4 is a bichromatic:
And so is bipartite, if we redraw it:
Q: For which n is Cn bipartite?
Subgraphs
Notice that the 2-cube
occurs
inside the 3-cube
. In other
words, Q2 is a subgraph of Q3 :
DEF: Let G = (V,E ) and H = (W,F ) be
graphs. H is said to be a subgraph of G,
if W  V and F  E.
Q: How many Q2 subgraphs does Q3 have?
38
Unions
In previous example can actually
reconstruct the 3-cube from its 6 2cube faces:
Graph Isomorphism
Two graphs are isomorphic (equivalence)
if can bend, stretch and reposition
vertices of the first graph, until the
second graph is formed. Etymologically,
isomorphic means “same shape”.
EG: Can twist or relabel:
to obtain:
Isomorphism of Graphs
For this purpose we can check invariants, that is,
properties that two isomorphic simple graphs must
both have.
the same number of vertices,
• the same number of edges, and
• the same degrees of vertices.
Note that two graphs that differ in any of these
invariants are not isomorphic, but two graphs that
match in all of them are not necessarily isomorphic.
Graph Isomorphism
-Example
EG: Prove that
is isomorphic to
.
First label the vertices:
1
2
3
1
2
5 4
5 4
3
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around
clockwise on the star.
1
2
3
1
2
5 4
5 4
3
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around
clockwise on the star. The next vertex seen
is 3, not 2 so set f (2) = 3.
1
2
3
1
2
5 4
5 4
3
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around
clockwise on the star. The next vertex seen
is 3, not 2 so set f (2) = 3. Next vertex is 5
so set f (3) = 5.
1
2
3
2
1
3
5 4
5
4
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around
clockwise on the star. The next vertex seen
is 3, not 2 so set f (2) = 3. Next vertex is 5
so set f (3) = 5. In this fashion we get f (4)
=2
2
1
5
3
4
2
1
5
3
4
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around
clockwise on the star. The next vertex seen
is 3, not 2 so set f (2) = 3. Next vertex is 5
so set f (3) = 5. In this fashion we get f (4)
= 2, f (5) = 4.
1
5
2
3
4
1
2
5 4
3
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around
clockwise on the star. The next vertex seen
is 3, not 2 so set f (2) = 3. Next vertex is 5
so set f (3) = 5. In this fashion we get f (4)
= 2, f (5) = 4. If we would continue, we
would get back to f (1) =1 so this process is
well defined and f is a morphism.
1
2
3
1
2
5 4
5 4
3
Graph Isomorphism
-Example
Next, set f (1) = 1 and try to walk around
clockwise on the star. The next vertex seen
is 3, not 2 so set f (2) = 3. Next vertex is 5
so set f (3) = 5. In this fashion we get f (4)
= 2, f (5) = 4. If we would continue, we
would get back to f (1) =1 so this process is
well defined and f is a morphism. Finally
since f is bijective, f is an isomorphism.
1
2
3
1
2
5 4
5 4
3
Isomorphism of Graphs
Are the following two graphs isomorphic?
a
b
c
a
e
d
c
b
e
d
Solution: Yes, they are isomorphic, because they can be
arranged to look identical. You can see this if in the right graph
you move vertex b to the left of the edge {a, c}. Then the
isomorphism f from the left to the right graph is: f(a) = e, f(b) =
a, f(c) = b, f(d) = c, f(e) = d.
Isomorphism of Graphs
How about these two graphs?
b
a
a
e
c
d
b
c
e
d
Solution: No, they are not isomorphic, because they differ in
the degrees of their vertices.
Vertex d in right graph is of degree one, but there is no such
vertex in the left graph.
Isomorphism Problem
Determining whether two
graphs are isomorphic
Although these graphs look
very different, they are
isomorphic; one
isomorphism between
them is
f(a) = 1 f(b) = 6 f(c) = 8
f(d) = 3
f(g) = 5 f(h) = 2 f(i) = 4 f(j)
=7
Paths
A path in a graph is a continuous way of getting
from one vertex to another by using a sequence
of edges.
1
e3
e1
e2
3
e6
2
e4
e5
e7
4
EG: could get from 1 to 3 circuitously as follows:
e
1-e12-e11-e33-e42-e62-e52- 43
Paths
A: For simple graphs, any edge is unique
between vertices so listing the vertices
gives us the edge-sequence as well.
DEF: A simple path contains no
duplicate edges (though duplicate
vertices are allowed).
A cycle (or circuit) is a path which starts
and ends at the same vertex.
Note: Simple paths need not be in simple
graphs. E.g., may contain loops.
a. Find out the truth value of
(p˄q) ⊕ (p˅q), when p is known to be
true and q is known to be false
b. Show that ((p ˅ q) ˄ (p  q))  q, is
a tautology.
a) Find the Boolean circuits of
[(p v q) ˄ (-p v r)] ˄ (q v r)
a) Let M(x) be the statement x loves Mathematics. Let F(x,y) be the statement x and
y are friends. Assume that the universe of discourse consists of all students with
computer science major. Translate the following into English
∀x ∃y (M(x)˅(M(y)˄F(x,y))).
a) By using only the logical identities, show that p ˄ (p  q) ≡ q ˄ p
Let P(x) , Q(x), and R(x) be the
statements x is a duck, x is annoying,
and x is a dancer, respectively. Express
each of these statements using
quantifiers, logical connectives, and
P(x) , Q(x), and R(x)
a) All ducks are annoying.
b) Some dancers are not annoying.
c) Some dancers are not ducks.
57
a. Find the negation of
1. ∀x∀y[((x > 0) ∧ (y > 0)) → (x + y > 0)]
Everybody loves somebody sometime
By using only the logical identities, show that (p  q) ˅ (¬q) is a tautology
58