10.3 Representing Graphs and Graph Isomorphism Flashcards
When are 2 graphs isomorphic?
Sometimes, two graphs have exactly the same form, in the sense that there is a one-to-one
correspondence between their vertex sets that preserves edges. In such a case, we say that the
two graphs are isomorphic
Representing graphs 10.3.2 :
One way to represent a graph without multiple edges is to list all the edges of this graph. Another
way to represent a graph with no multiple edges is to use adjacency lists, which specify the
vertices that are adjacent to each vertex of the graph.
Adjacency Matrix :
for a graph , how many adjacency matrices are possible?
Properties:
Ag = [aij] where g = (V , E ) and |V| = n.
vertices of g are listed arbitrarily as v1, v2, … , vn.
aij = 1 if {vi, vj} is an edge of G,
0 otherwise.
Note that an adjacency matrix of a graph is based on the ordering chosen for the vertices.
Hence, there may be as many as n! different adjacency matrices for a graph with n vertices.
- This matrix is symmetric for simple graph and diag elements = 0 as no loops.
-All undirected graphs, including multigraphs and pseudographs, have symmetric adjacency
matrices.
-For multigraphs the matrix is no more a zero one matric.
Adjacency Matrix for directed graph:
G = (V, E)
A = [aij]
aij = 1 if (vi, vj) is an edge of G,
0 otherwise.
Not symmetric.
Multigraph again wont be zero one matrix.
TRADE-OFFS BETWEEN ADJACENCY LISTS AND ADJACENCY MATRICES
If simple graph with few edges, sparse then adjacency lists preferred.
If degree of each vertex < c < n.
akthough we have space Matrix to deal w it.
To get data from from matrix we just need to check i,t the position otherwise in list it will get hectic especially in dense graph.
Incidence matrices
Let G = (V, E) be an
undirected graph. Suppose that v1, v2, … , vn are the vertices and e1, e2, … , em are the edges
of G.
Then the incidence matrix with respect to this ordering of V and E is the n × m matrix
M = [mij], where
mij = 1 when edge ej is incident with vi
0 otherwise.
Multiple edges : Identical column
Loops : Column with one entry.
Isomorphism ?
Isomorphic graph?
Definition:
What type of relation is isomorphism ?
The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there exists a one-to one and onto function f from V1 to V2 with the property that a and b are adjacent in G1
if and only if f(a) and f(b) are adjacent in G2,
for all a and b in V1.
Such a function f is called an isomorphism.
Two simple graphs that are not isomorphic are called nonisomorphic.
In other words, when two simple graphs are isomorphic, there is a one-to-one correspondence
between vertices of the two graphs that preserves the adjacency relationship. Isomorphism of
simple graphs is an equivalence relation.
Graph Invariant :
definition and examples :
A property preserved by isomorphism of graphs is
called a graph invariant.
For instance, isomorphic simple graphs must have the same number
of vertices, because there is a one-to-one correspondence between the sets of vertices of the
graphs.
Isomorphic simple graphs also must have the same number of edges, because the one-to one correspondence between vertices establishes a one-to-one correspondence between edges.
Degrees of the vertices in isomorphic simple graphs must be the same. i.e a vertex v of degree d in G must correspond to a vertex f(v) of degree d in H, because a vertex
w in G is adjacent to v f(v) and f(w) are adjacent in H.
Determining Two Simple Graphs are not Isomorphic
Difficult, n! possible one-to-one correspondences between the vertex sets of two simple graphs with n vertices. Testing each such correspondence to see whether it preserves adjacency and nonadjacency is
impractical if n is at all large.
The number of vertices, the number of edges, and the number of vertices of each degree
are all invariants under isomorphism. But if these are valid, we still cant say they are isomorphic.
Subgraphs of isomorphic graphs are isomorphic.
Determining whether Two Simple Graphs are Isomorphic:
To show that a function f from the vertex set of a graph G to the vertex set of a graph H is an
isomorphism, we need to show that f preserves the presence and absence of edges.
This can be done using Adjacency matrix.
In particular, to show that f is an isomorphism, we
can show that the adjacency matrix of G is the same as the adjacency matrix of H, when rows
and columns are labeled to correspond to the images under f of the vertices in G that are the
labels of these rows and columns in the adjacency matrix of G. .
Note that if f turned out not to be an isomorphism, we would not have
established that G and H are not isomorphic, because another correspondence of the vertices in
G and H may be an isomorphism.
quasi-polynomial time
which is between polynomial time and exponential time
ALGORITHMS FOR GRAPH ISOMORPHISM
Check the applications.
Graph isomorphism is the basis for the verification that a particular layout of a circuit produced
by an automated tool corresponds to the original schematic of the design. Graph isomorphism
can also be used to determine whether a chip from one vendor includes intellectual property
from a different vendor. This can be done by looking for large isomorphic subgraphs in the
graphs modeling these chips.
Until recently, the best algorithms known Links for determining whether two graphs are isomorphic have exponential worst-case time complexity (in the number of vertices of the graphs). However, in early 2017 Laszl ´ o Babai announced ´
that he had an algorithm that determines whether two graphs with n vertices are isomorphic
in 2^[f(n)] time, where f(n) is O((log n)^3).
Even though
no polynomial-time algorithms have been found for solving this problem, it can be solved by
linear average-case time complexity algorithms. There is some hope, but also skepticism, that
an algorithm with polynomial worst-case time complexity for determining whether two graphs
are isomorphic can be found.
NAUTY : can determine whether two graphs with as many as 100 vertices are isomorphic in less
than a second on a modern PC.
The problem of determining whether any two graphs are isomorphic is of
special interest because it is one of only a few NP problems (see Exercise 78) not known to be
either tractable or NP-complete (see Section 3.3).
