Graphs (Part B)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
March 18, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 1 / 14
1 Special Graphs
2 Isomorphism
3 Connectivity
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 2 / 14
Bipartite Graphs
Definition
A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 (so that no edge in G connects either two vertices in V1 or two vertices in V2). When this condition holds, we call the pair (V1,V2) a bipartition of the vertex set V of G.
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 3 / 14
Bipartite Graphs (cont.)
Theorem: Bipartite Graph
A simple graph is bipartite if and only if it is possible to assign one of two colors to each vertex of the graph so that no two adjacent vertices are assigned the same color.
Hall’s Marriage Theorem
The bipartite graph G = (V,E) with bipartition (V1,V2) has a complete matching from V1 to V2 if and only if |N(A)| ≥ |A| for all subsets A of V1.
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 4 / 14
Applications of Special Graphs
• Construction of network topologies
– Communications
– Transportations and highways – Cloud computing
• High performance computing: multiprocessor topologies
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 5 / 14
• A subgraph of a graph G = (V,E) is a graph H = (W,F), where
W ⊆ V and F ⊆ E. A subgraph H is a proper subgraph of G if H ̸= G.
• Let G = (V,E) is a simple graph. The subgraph induced by a subset W of the vertex set V is the graph (W , F ), where the edge set F contains an edge in E if and only if both endpoints of this edge are in W .
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 6 / 14
from Old (cont.)
Removing or Adding Edges of a Graph
• Given a graph G = (V,E) and an edge e ∈ E, we can produce subgraphs:
– G − e = (V , E − e) (removing) – G + e = (V , E + e) (adding)
Edge Contractions
• Merging endpoints of an edge that is removed. Removing Vertices from a Graph
• G − V ′ = (V − V ′ , E ′ ) . Graph Unions
• The union of two simple graphs G1 = (V1, E1) and G2 = (V2, E2) is the simple graph with vertex set V1 ∪ V2 and edge set E1 ∪ E2.
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 7 / 14
Graph Representation
Isomorphism
Two graphs are isomorphic when they have exactly the same form, in the sense that there is a one-to-one correspondence between their vertex sets that preserves edges.
Graph Representation Methods
• Adjacency lists
– Graphs with no multiple edges can be represented
– Lists specify vertices that are adjacent to each vertex of the graph.
• Adjacency matrices
– Square matrices are used to specify edges between vertices.
• Incidence matrices
– Incidence matrices whose rows correspond to vertices and columns
correspond to edges.
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 8 / 14
Graph Representation (cont.)
Adjacency Matrix
Suppose that G = (V,E) is a simple graph where |V| = n. Suppose that the vertices of G are listed arbitrarily as v1, v2, …, vn. The adjacency matrix A (or AG) of G, with respect to this listing of the vertices, is the n × n zero-one matrix with 1 as its (i, j)th entry when vi and vj are adjacent, and 0 as its its (i,j)th entry when they are not adjacent.
The adjacency matrix A = [aij ] is given by
1 if {vi,vj} is an edge of G, 0 otherwise.
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 9 / 14
Graph Representation (cont.)
Incidence Matrix
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
1 when edge ej is incident with vi , 0 otherwise.
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 10 / 14
Isomorphism
Definitions
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.
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 11 / 14
Determining Isomorphism
A property preserved by isomorphism of graphs is called a graph invariant. Three key properties:
• Isomorphic simple graphs must have the same number of vertices. • Isomorphic simple graphs must have the same number of edges.
• The degrees of the vertices in isomorphic simple graphs must be the same.
Note:This is not an exclusive list! Check Examples 9 and 10 of Section 10.3 from the textbook.
• Degrees of the adjacent vertices are also required to be matched.
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 12 / 14
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.
Formal Definition
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,e2,…,en of G for which there exists a sequence x0 = u, x1, …, xn−1, xn = v of vertices such that ei has, for i = 1,…,n, the endpoints xi−1 and xi. When the graph is simple, we denote this path by its vertex sequence x0, x1, …, xn.
•Apathisacircuitifu=v andn>0.
• A path is simple if does not contain the same edge more than once.
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 13 / 14
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 10b MdH W22 March 18, 2022 14 / 14
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com