際際滷

際際滷Share a Scribd company logo

ch8.3-8.4.ppt

Download as PPT, PDF
Deepali Hejib
Deepali Hejib

The document discusses representing graphs using adjacency and incidence matrices. It defines adjacency and incidence matrices and provides examples of computing them for simple graphs. It also covers graph isomorphism, defining when two graphs are isomorphic, and providing examples of determining if graphs are isomorphic. Finally, it discusses connectivity in graphs, defining when a graph is connected and the connected components of a graph, as well as cut vertices and edges.

1 of 25
Download to read offline
1 Representing Graphs and Graph Isomorphism (Chapter 8.3) Connectivity (Chapter 8.4) Based on slides by Y. Peng University of Maryland
2 Representing Graphs a b c d a b c d a, d b a, d c a, b, c d b, c, d a Adjacent Vertices Vertex a b c a, b, c d c a Terminal Vertices Initial Vertex
3 Representing Graphs Definition: Let G = (V, E) be a simple graph with |V| = n. Suppose that the vertices of G are listed in arbitrary order as v1, v2, , vn. The adjacency matrix A (or AG) of G, with respect to this listing of the vertices, is the nn zero-one matrix with 1 as its (i, j) entry when vi and vj are adjacent, and 0 otherwise. In other words, for an adjacency matrix A = [aij], aij = 1 if {vi, vj} is an edge of G, aij = 0 otherwise.
4 Representing Graphs a b c d Example: What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ? Solution: 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 G A Note: Adjacency matrices of undirected graphs are always symmetric.
5 Representing Graphs Definition: Let G = (V, E) be an undirected graph with |V| = n. Suppose that the vertices and edges of G are listed in arbitrary order as v1, v2, , vn and e1, e2, , em, respectively. The incidence matrix of G with respect to this listing of the vertices and edges is the nm zero- one matrix with 1 as its (i, j) entry when edge ej is incident with vi, and 0 otherwise. In other words, for an incidence matrix M = [mij], mij = 1 if edge ej is incident with vi mij = 0 otherwise.
6 Representing Graphs Example: What is the incidence matrix M for the following graph G based on the order of vertices a, b, c, d and edges 1, 2, 3, 4, 5, 6? Solution: 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1 M Note: Incidence matrices of directed graphs contain two 1s per column for edges connecting two vertices and one 1 per column for loops. a b c d 1 2 4 5 3 6
7 Isomorphism of Graphs Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there is a bijection (an 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. In other words, G1 and G2 are isomorphic if their vertices can be ordered in such a way that the adjacency matrices MG1 and MG2 are identical.
8 Isomorphism of Graphs From a visual standpoint, G1 and G2 are isomorphic if they can be arranged in such a way that their displays are identical (of course without changing adjacency). Unfortunately, for two simple graphs, each with n vertices, there are n! possible isomorphisms that we have to check in order to show that these graphs are isomorphic. However, showing that two graphs are not isomorphic can be easy.
9 Isomorphism of Graphs For this purpose we can check invariants, that is, properties that two isomorphic simple graphs must both have. For example, they must 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.
10 Isomorphism of Graphs Example I: Are the following two graphs isomorphic? d a b c e d a b c e 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.
11 Isomorphism of Graphs Example II: How about these two graphs? d a b c e d a b c e 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.
12 Examples Determine if the following two graphs G1 and G2 are isomorphic: Ex. 35 and 41, p. 565
13 Connectivity Definition: A path of length n from u to v, where n is a positive integer, in an undirected graph is a sequence of edges e1, e2, , en of the graph such that e1 = {x0, x1}, e2 = {x1, x2}, , en = {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, since it uniquely determines the path. The path is a circuit if it begins and ends at the same vertex, that is, if u = v.
14 Connectivity Definition (continued): The path or circuit is said to pass through or traverse x1, x2, , xn-1. A path or circuit is simple if it does not contain the same edge more than once.
15 Connectivity Let us now look at something new: Definition: An undirected graph is called connected if there is a path between every pair of distinct vertices in the graph. For example, any two computers in a network can communicate if and only if the graph of this network is connected. Note: A graph consisting of only one vertex is always connected, because it does not contain any pair of distinct vertices.
16 Connectivity Example: Are the following graphs connected? d a b c e Yes. d a b c e No. d a b c e Yes. d a b c e f No.
17 Connectivity Definition: A graph that is not connected is the union of two or more connected subgraphs, each pair of which has no vertex in common. These disjoint connected subgraphs are called the connected components of the graph. Definition: A connected component of a graph G is a maximal connected subgraph of G. E.g., if vertex v in G belongs to a connected component, then all other vertices in G that is connected to v must also belong to that component.
18 Connectivity Example: What are the connected components in the following graph? a b c d i h g j f e Solution: The connected components are the graphs with vertices {a, b, c, d}, {e}, {f}, {i, g, h, j}.
19 Connectivity Definition: An directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph. Definition: An directed graph is weakly connected if there is a path between any two vertices in the underlying undirected graph.
20 Connectivity Example: Are the following directed graphs strongly or weakly connected? a b c d Weakly connected, because, for example, there is no path from b to d. a b c d Strongly connected, because there are paths between all possible pairs of vertices.
21 Cut vertices and edges If one can remove a vertex (and all incident edges) and produce a graph with more components, the vertex is called a cut vertex or articulation point. Similarly if removal of an edge creates more components the edge is called a cut edge or bridge.
22 In the graphs G1 and G2 every edge is a cut edge. In the union, no edge is a cut edge. Vertex e is a cut vertex in all graphs. In the star network the center vertex is a cut vertex. All edges are cut edges.
23
24
25

More Related Content

ch8.3-8.4.ppt

  • 1. 1 Representing Graphs and Graph Isomorphism (Chapter 8.3) Connectivity (Chapter 8.4) Based on slides by Y. Peng University of Maryland
  • 2. 2 Representing Graphs a b c d a b c d a, d b a, d c a, b, c d b, c, d a Adjacent Vertices Vertex a b c a, b, c d c a Terminal Vertices Initial Vertex
  • 3. 3 Representing Graphs Definition: Let G = (V, E) be a simple graph with |V| = n. Suppose that the vertices of G are listed in arbitrary order as v1, v2, , vn. The adjacency matrix A (or AG) of G, with respect to this listing of the vertices, is the nn zero-one matrix with 1 as its (i, j) entry when vi and vj are adjacent, and 0 otherwise. In other words, for an adjacency matrix A = [aij], aij = 1 if {vi, vj} is an edge of G, aij = 0 otherwise.
  • 4. 4 Representing Graphs a b c d Example: What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ? Solution: 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 G A Note: Adjacency matrices of undirected graphs are always symmetric.
  • 5. 5 Representing Graphs Definition: Let G = (V, E) be an undirected graph with |V| = n. Suppose that the vertices and edges of G are listed in arbitrary order as v1, v2, , vn and e1, e2, , em, respectively. The incidence matrix of G with respect to this listing of the vertices and edges is the nm zero- one matrix with 1 as its (i, j) entry when edge ej is incident with vi, and 0 otherwise. In other words, for an incidence matrix M = [mij], mij = 1 if edge ej is incident with vi mij = 0 otherwise.
  • 6. 6 Representing Graphs Example: What is the incidence matrix M for the following graph G based on the order of vertices a, b, c, d and edges 1, 2, 3, 4, 5, 6? Solution: 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1 M Note: Incidence matrices of directed graphs contain two 1s per column for edges connecting two vertices and one 1 per column for loops. a b c d 1 2 4 5 3 6
  • 7. 7 Isomorphism of Graphs Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there is a bijection (an 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. In other words, G1 and G2 are isomorphic if their vertices can be ordered in such a way that the adjacency matrices MG1 and MG2 are identical.
  • 8. 8 Isomorphism of Graphs From a visual standpoint, G1 and G2 are isomorphic if they can be arranged in such a way that their displays are identical (of course without changing adjacency). Unfortunately, for two simple graphs, each with n vertices, there are n! possible isomorphisms that we have to check in order to show that these graphs are isomorphic. However, showing that two graphs are not isomorphic can be easy.
  • 9. 9 Isomorphism of Graphs For this purpose we can check invariants, that is, properties that two isomorphic simple graphs must both have. For example, they must 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.
  • 10. 10 Isomorphism of Graphs Example I: Are the following two graphs isomorphic? d a b c e d a b c e 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.
  • 11. 11 Isomorphism of Graphs Example II: How about these two graphs? d a b c e d a b c e 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.
  • 12. 12 Examples Determine if the following two graphs G1 and G2 are isomorphic: Ex. 35 and 41, p. 565
  • 13. 13 Connectivity Definition: A path of length n from u to v, where n is a positive integer, in an undirected graph is a sequence of edges e1, e2, , en of the graph such that e1 = {x0, x1}, e2 = {x1, x2}, , en = {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, since it uniquely determines the path. The path is a circuit if it begins and ends at the same vertex, that is, if u = v.
  • 14. 14 Connectivity Definition (continued): The path or circuit is said to pass through or traverse x1, x2, , xn-1. A path or circuit is simple if it does not contain the same edge more than once.
  • 15. 15 Connectivity Let us now look at something new: Definition: An undirected graph is called connected if there is a path between every pair of distinct vertices in the graph. For example, any two computers in a network can communicate if and only if the graph of this network is connected. Note: A graph consisting of only one vertex is always connected, because it does not contain any pair of distinct vertices.
  • 16. 16 Connectivity Example: Are the following graphs connected? d a b c e Yes. d a b c e No. d a b c e Yes. d a b c e f No.
  • 17. 17 Connectivity Definition: A graph that is not connected is the union of two or more connected subgraphs, each pair of which has no vertex in common. These disjoint connected subgraphs are called the connected components of the graph. Definition: A connected component of a graph G is a maximal connected subgraph of G. E.g., if vertex v in G belongs to a connected component, then all other vertices in G that is connected to v must also belong to that component.
  • 18. 18 Connectivity Example: What are the connected components in the following graph? a b c d i h g j f e Solution: The connected components are the graphs with vertices {a, b, c, d}, {e}, {f}, {i, g, h, j}.
  • 19. 19 Connectivity Definition: An directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph. Definition: An directed graph is weakly connected if there is a path between any two vertices in the underlying undirected graph.
  • 20. 20 Connectivity Example: Are the following directed graphs strongly or weakly connected? a b c d Weakly connected, because, for example, there is no path from b to d. a b c d Strongly connected, because there are paths between all possible pairs of vertices.
  • 21. 21 Cut vertices and edges If one can remove a vertex (and all incident edges) and produce a graph with more components, the vertex is called a cut vertex or articulation point. Similarly if removal of an edge creates more components the edge is called a cut edge or bridge.
  • 22. 22 In the graphs G1 and G2 every edge is a cut edge. In the union, no edge is a cut edge. Vertex e is a cut vertex in all graphs. In the star network the center vertex is a cut vertex. All edges are cut edges.
  • 23. 23
  • 24. 24
  • 25. 25