Graphs (Part C)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
March 23, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 10c MdH W22 March 23, 2022 1 / 10
1 Connectivity
Md. Hasan (uOttawa) Discrete Structures 10c MdH W22 March 23, 2022 2 / 10
Connectedness in Undirected Graphs
Definition
An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph. An undirected graph that is not connected is called disconnected. We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph.
There is a simple path between every pair of distinct vertices of a connected undirected graph.
Md. Hasan (uOttawa) Discrete Structures 10c MdH W22 March 23, 2022 3 / 10
Connectedness in Undirected Graphs (cont.)
Connected Components
A connected component of a graph G is a connected subgraph of G that is not a proper subgraph of another connected subgraph of G. That is, a connected component of a graph G is a maximal connected subgraph of G. A graph G that is not connected has two or more connected components that are disjoint and have G as their union.
Sometimes the removal of a vertex and all incident edges from a graph produces a graph with more number of connected components. Such vertices are called cut vertices (or articulation points).
An edge whose removal produces a graph with more number of connected components than in the original graph is called a cut edge (or bridge).
Md. Hasan (uOttawa) Discrete Structures 10c MdH W22 March 23, 2022 4 / 10
Connectedness in Undirected Graphs (cont.)
Vertex Connectivity
• Not all graphs have cut vertices. For example, Kn with n ≥ 3 has no cut vertices. Connected graphs without cut vertices are called nonseparable graphs, and can be thought of as more connected than those with a cut vertex.
•AsubsetV′ ofthevertexsetV ofG=(V,E)isavertexcut,or separating set, if G − V ′ is a disconnected graph. Every connected graph, except a complete graph, has a vertex cut.
• The vertex connectivity of a noncomplete graph G, denoted by κ(G), is defined as the minimum number of vertices in a vertex cut. A graph is k-connected, if κ(G) ≥ k.
Md. Hasan (uOttawa) Discrete Structures 10c MdH W22 March 23, 2022 5 / 10
Connectedness in Undirected Graphs (cont.)
Edge Connectivity
•AsetofedgesE′ iscalledanedgecutofG ifthesubgraphG−E′ is disconnected.
• The edge connectivity of a graph G, denoted by λ(G), is the minimum number of edges in an edge cut of G. If G is a graph with n vertices, then 0 ≤ λ(G ) ≤ n − 1.
• λ(G ) = 0 for a single vertex graph and λ(G ) = n − 1 for a complete graph.
• κ(G) ≤ λ(G) ≤ minv∈V deg(v) for all graph G.
Md. Hasan (uOttawa) Discrete Structures 10c MdH W22 March 23, 2022 6 / 10
Connectedness in Directed Graphs
Strong Connectivity
A 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.
Weak Connectivity
A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph.
Strong Components
The subgraphs of a directed graph G that are strongly connected but not contained in larger strongly connected subgraphs, that is, the maximal strongly connected subgraphs, are called the strongly connected components or strong components of G.
Md. Hasan (uOttawa) Discrete Structures 10c MdH W22 March 23, 2022 7 / 10
Paths and Isomorphism
Paths and circuits can help determining isomorphism in multiple ways. The existence of a simple circuit of a particular length is a useful invariant that can be used to show that two graphs are not isomorphic.
Two isomorphic graphs contain the circuits that are of the same length.
Md. Hasan (uOttawa) Discrete Structures 10c MdH W22 March 23, 2022 8 / 10
Counting Paths Between Vertices
Let G be a graph with adjacency matrix A with respect to the ordering v1, v2, …, vn of the vertices of the graph (with directed or undirected eges, with multiple edges and loops allowed). The number of different paths of length r from vi to vj, where r is a positive integer, equals the (i,j)th entry of Ar .
• This theorem can be proved using mathematical induction. The adjacency matrix of a graph actually includes all paths between vertices that are of length 1.
Md. Hasan (uOttawa) Discrete Structures 10c MdH W22 March 23, 2022 9 / 10
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 10c MdH W22 March 23, 2022 10 / 10
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com