Transcript Still Image Compression

Lecture 5.3: Graph Isomorphism and
Connectivity
CS 250, Discrete Structures, Fall 2011
Nitesh Saxena
*Adopted from previous lectures by Zeph Grunschlag
HW1



Submitted yesterday
Grading now – expect results in about a week
Solution to be posted soon
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Course Admin -- Final Exam

Thursday, December 8, 10:45am1:15pm, lecture room




Heads up!
Please mark the date/time/place
Emphasis on post mid-term 2 material
Coverage:



65% post mid-term 2 (lectures 4.*, 5.*, 6.*), and
35% pre mid-term 2 (lecture 1.*. 2.* and 3.*)
Our last lecture will be on December 6

We plan to do a final exam review then
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Course Admin -- Homework 5



Heads up: will be posted by the coming
weekend
Due in 10 days after the day of posting
Covers the chapter on Graphs (lecture 5.*)
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Outline


Graph Isomorphism
Paths and Connectivity
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Warm-up Exercise
Theorem: No. of edges in an n-cube is n2n-1
Proof: Use mathematical induction.
Let’s use the whiteboard.
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Graph Isomorphism
Various mathematical notions come with their
own concept of equivalence, as opposed to
equality:
 Equivalence for sets is bijectivity:


EG {23, 12, 43}  {12, 23, 43}
Equivalence for graphs is isomorphism:

EG

Lecture 5.3 -- Graph Isomorphism
and Connectivity
Graph Isomorphism
Intuitively, two graphs are isomorphic 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:
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Graph Isomorphism
Undirected Graphs
DEF: Suppose G1 = (V1, E1 ) and G2 = (V2, E2 ) are
pseudographs. Let f :V1V2 be a function
s.t.:
1)
f is bijective
2)
for all vertices u,v in V1, the number of
edges between u and v in G1 is the same as
the number of edges between f (u) and f (v )
in G2.
Then f is called an isomorphism and G1 is said to
be isomorphic to G2.
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Graph Isomorphism
Digraphs
DEF: Suppose G1 = (V1, E1 ) and G2 = (V2, E2 ) are
directed multigraphs. Let f :V1V2 be a
function s.t.:
1)
f is bijective
2)
for all vertices u,v in V1, the number of
edges from u to v in G1 is the same as the
number of edges between f (u) and f (v ) in
G2.
Then f is called an isomorphism and G1 is said to
be isomorphic to G2.
Note: Only difference between two definitions is the
italicized “from” in no. 2 (was “between”).
Graph Isomorphism
-Example
EG: Prove that
is isomorphic to
First label the vertices:
1
2
3
1
2
5 4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
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
Lecture 5.3 -- Graph Isomorphism
and Connectivity
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
Lecture 5.3 -- Graph Isomorphism
and Connectivity
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
Lecture 5.3 -- Graph Isomorphism
and Connectivity
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
Lecture 5.3 -- Graph Isomorphism
and Connectivity
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
Lecture 5.3 -- Graph Isomorphism
and Connectivity
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
isomorphism.
1
2
3
1
2
5 4
5 4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
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
Properties of Isomorphims
Since graphs are completely defined by their
vertex sets and the number of edges
between each pair, isomorphic graphs must
have the same intrinsic properties. I.e.
isomorphic graphs have the same…
 number of vertices and edges
 degrees at corresponding vertices
 types of possible subgraphs
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Exercise


Is “isomorphism” on graphs an equivalence
relation?
If so, what are the equivalence classes?
Let’s use the whiteboard!
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Graph Isomorphism
-Negative Examples
To show that two graphs are non-isomorphic
need to show that no function can exist
that satisfies defining properties of
isomorphism. In practice, you try to find
some intrinsic property that differs
between the 2 graphs in question.
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Graph Isomorphism
-Negative Examples
Q: Why are the following non-isomorphic?
u2
u1
u5
u3
v2
v1
u4
v3
v4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Graph Isomorphism
-Negative Examples
A: 1st graph has more vertices than 2nd.
Q: Why are the following non-isomorphic?
u2
u1
u5
u3
u4
v2
v1
v5
Lecture 5.3 -- Graph Isomorphism
and Connectivity
v3
v4
Graph Isomorphism
-Negative Examples
A: 1st graph has more edges than 2nd.
Q: Why are the following non-isomorphic?
u2
u1
u5
u3
u4
v2
v1
v5
Lecture 5.3 -- Graph Isomorphism
and Connectivity
v3
v4
Graph Isomorphism
-Negative Examples
A: 2nd graph has vertex of degree 1, 1st
graph doesn't.
Q: Why are the following non-isomorphic?
u1
u2
u3
u7
u8
u4
u5
u9
u6
v1
v2
v7
Lecture 5.3 -- Graph Isomorphism
and Connectivity
v3
v4
v5
v8
v9
v6
Graph Isomorphism
-Negative Examples
A: 1st graph has 2 degree 1 vertices, 4 degree
2 vertex and 2 degree 3 vertices. 2nd graph
has 3 degree 1 vertices, 3 degree 2 vertex
and 3 degree 3 vertices.
Q: Why are the following non-isomorphic?
u1
u2
u7
u3
u4
u5
u8
u6
v1
v2
v7
Lecture 5.3 -- Graph Isomorphism
and Connectivity
v3
v4
v8
v5
v6
Graph Isomorphism
-Negative Examples
A: None of the previous approaches work as
there are the same no. of vertices, edges,
and same no. of vertices per degree.
u1
u2
u7
u3
u4
u5
u8
u6
v1
v2
v7
v3
v4
v8
v5
LEMMA: If G and H are isomorphic, then any
subgraph of G will be isomorphic to some
subgraph of H.
Q: Find a subgraph of 2nd graph which isn’t a
subgraph of 1st graph.
v6
Graph Isomorphism
-Negative Examples
u1
A: This subgraph is not a subgraph of the left
graph.
u2
u7
u3
u4
u5
u8
u6
v1
v2
v7
v3
v4
v5
v8
Why not? Deg. 3 vertices must map to deg. 3 vertices.
Since subgraph and left graph are symmetric, can
assume v2 maps to u2. Adjacent deg. 1 vertices to v2
must map to degree 1 vertices, forcing the deg. 2
adjacent vertex v3 to map to u3. This forces the
other vertex adjacent to v3, namely v4 to map to u4.
But then a deg. 3 vertex has mapped to a deg. 2
vertex.
v6
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:
1-e12-e11-e33-e42-e62-e52-e43
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:
1-e12-e11-e33-e42-e62-e52-e43
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:
1-e12-e11-e33-e42-e62-e52-e43
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:
1-e12-e11-e33-e42-e62-e52-e43
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:
1-e12-e11-e33-e42-e62-e52-e43
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:
1-e12-e11-e33-e42-e62-e52-e43
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:
1-e12-e11-e33-e42-e62-e52-e43
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:
1-e12-e11-e33-e42-e62-e52-e43
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:
1-e12-e11-e33-e42-e62-e52-e43
Paths
DEF: A path of length n in an undirected
graph is a sequence of n edges e1, e2, … ,en
such that each consecutive pair ei , ei+1
share a common vertex. In a simple graph,
one may instead define a path of length n as
a sequence of n+1 vertices v0, v1, v2, … ,vn
such that each consecutive pair vi , vi+1 are
adjacent. Paths of length 0 are also allowed
according to this definition.
Q: Why does the second definition work for
simple graphs?
Lecture 5.3 -- Graph Isomorphism
and Connectivity
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.
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Paths
Q: Find a longest possible simple path in the
following graph:
1
e3
e1
e2
e6
2
e4
e5
3
Lecture 5.3 -- Graph Isomorphism
and Connectivity
e7
4
Paths
A: The following path from 1 to 2 is a maximal
simple path because
 simple: each of its edges appears exactly
once
 maximal: because it contains every edge
except the unreachable edge e7
1
e3
e1
e2
2
e4
e6
e5
3
e7
4
The maximal path: e1,e5,e6,e2,e3,e4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Paths in Directed Graphs
One can define paths for directed graphs by
insisting that the target of each edge in
the path is the source of the next edge:
DEF: A path of length n in a directed graph
is a sequence of n edges e1, e2, … ,en such
that the target of ei is the source ei+1 for
each i. In a digraph, one may instead
define a path of length n as a sequence of
n+1 vertices v0, v1, v2, … ,vn such that for
each consecutive pair vi , vi+1 there is an
edge from vi to vi+1 .
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Paths in Directed Graphs
Q: Consider digraph adjacency matrix:
1

0
1

0

1.
2.
0
1
1
1
1
0
0
0
0

1
0


0
Find a path from 1 to 4.
Is there a path from 4 to 1?
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Paths in Directed Graphs
A:
2.
1

0
1

0

0 1 0

1 0 1
1 0 0

1 0 0 
1.
13
.
There’s no path from 4 to 1. From 4 must
go to 2, from 2 must stay at 2 or return to
4. In other words 2 and 4 are
disconnected from 1.
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Paths in Directed Graphs
A:
1

0
1

0

1
0
0
0
0

1
0


0
132 .
There’s no path from 4 to 1. From 4 must
go to 2, from 2 must stay at 2 or return to
4. In other words 2 and 4 are
disconnected from 1.
1.
2.
0
1
1
1
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Paths in Directed Graphs
A:
1

0
1

0

1
0
0
0
0

1
0


0
1324.
There’s no path from 4 to 1. From 4 must
go to 2, from 2 must stay at 2 or return to
4. In other words 2 and 4 are
disconnected from 1.
1.
2.
0
1
1
1
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity
DEF: Let G be a pseudograph. Let u and v be
vertices. u and v are connected to each
other if there is a path in G which starts at
u and ends at v. G is said to be connected if
all vertices are connected to each other.
Note: Any vertex is automatically connected
to itself via the empty path.
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity
Q: Which of the following graphs are
connected?
1
2
3
4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity
A: First and second are disconnected. Last is
connected.
1
2
3
4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity
A: First and second are disconnected. Last is
connected.
1
2
3
4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity
A: First and second are disconnected. Last is
connected.
1
2
3
4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity
A: First and second are disconnected. Last is
connected.
1
2
3
4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity
A: First and second are disconnected. Last is
connected.
1
2
3
4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity
A: First and second are disconnected. Last is
connected.
1
2
3
4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
English Connectivity Puzzle
Can define a puzzling graph G as follows:
V = {3-letter English words}
E : two words are connected if we 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” ?
Lecture 5.3 -- Graph Isomorphism
and Connectivity
English Connectivity Puzzle
A: Yes: funfanfarcar
Or: funfinbinbanbarcar
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connected Components
DEF: A connected component (or just
component) in a graph G is a set of vertices
such that all vertices in the set are
connected to each other and every possible
connected vertex is included.
Q: What are the connected components of
1
the following graph?
6
5
Lecture 5.3 -- Graph Isomorphism
and Connectivity
2
7
8
3
4
Connected Components
A: The components are {1,3,5},{2,4,6},{7} and
{8} as one can see visually by pulling
components apart:
1
6
2
5
8
3
7
4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connected Components
A: The components are {1,3,5},{2,4,6},{7} and
{8} as one can see visually by pulling
components apart:
1
6
2
5
3
7
4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
8
Connected Components
A: The components are {1,3,5}, {2,4,6}, {7}
and {8} as one can see visually by pulling
components apart:
6
1
2
7
5
3
4
Lecture 5.3 -- Graph Isomorphism
and Connectivity
8
Degree of Connectivity
Not all connected graphs are treated equal!
Q: Rate following graphs in terms of their
design value for computer networks:
1)
2)
3)
4)
Degree of Connectivity
A: Want all computers to be connected, even if
1 computer goes down:
1) 2nd best. However, there’s
a weak link— “cut vertex”
2) 3rd best. Connected
but any computer can disconnect
3) Worst!
Already disconnected
4) Best! Network dies
only with 2 bad computers
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Degree of Connectivity
The network
is best because it
can only become disconnected when 2
vertices are removed. In other words, it is
2-connected. Formally:
DEF: A connected simple graph with 3 or more
vertices is 2-connected if it remains
connected when any vertex is removed.
When the graph is not 2-connected, we call
the disconnecting vertex a cut vertex.
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Degree of Connectivity
There is also a notion of N-Connectivity where
we require at least N vertices to be removed
to disconnect the graph.
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity in
Directed Graphs
In directed graphs may be able to find a path
from a to b but not from b to a.
However, Connectivity was a symmetric
concept for undirected graphs. So how
to define directed Connectivity is nonobvious:
1)
Should we ignore directions?
2)
Should we insist that can get from a to b
in actual digraph?
3)
Should we insist that can get from a to b
and that can get from b to a?
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity in
Directed Graphs
Resolution: Don’t bother choosing which definition is
better. Just define to separate concepts:
1)
Weakly connected : can get from a to b in
underlying undirected graph
2)
Semi-connected (my terminology): can get from
a to b OR from b to a in digraph
3)
Strongly connected : can get from a to b AND
from b to a in the digraph
DEF: A graph is strongly (resp. semi, resp. weakly)
connected if every pair of vertices is connected
in the same sense.
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity in
Directed Graphs
Q: Classify the connectivity of each graph.
Lecture 5.3 -- Graph Isomorphism
and Connectivity
Connectivity in
Directed Graphs
A:
semi
weak
Lecture 5.3 -- Graph Isomorphism
and Connectivity
strong
Today’s Reading

Rosen 10.3 and 10.4
Lecture 5.3 -- Graph Isomorphism
and Connectivity