Graphs (Part D)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
March 24, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 10d MdH W22 March 24, 2022 1 / 10
1 Euler Paths and Circuits
2 Hamilton Paths and Circuits
Md. Hasan (uOttawa) Discrete Structures 10d MdH W22 March 24, 2022 2 / 10
Euler Paths and Circuits
Definition: Euler Circuit and Path
An Euler Circuit in a graph G is a simple circuit containting every edge of G. An Euler Path in a graph G is a simple path containting every edge of G.
Note: the vertices can be repeated but not the edges. Definition: Multigraph
An undirected graph that may contain multiple edges but no loops.
Definition: Pseudograph
An undirected graph that may contain multiple edges and loops.
Md. Hasan (uOttawa) Discrete Structures 10d MdH W22 March 24, 2022 3 / 10
Necessary Conditions for Euler Circuits and Paths
Obtaining Necessary Conditions
• An Euler circuit begins with a vertex a and continues with an edge incident with a, say {a,b}. The edge {a,b} contributes one to deg(a).
• Each time the circuit passes through a vertex it contributes two to the vertexs degree.
• Finally, the circuit terminates where it started, contributing one to deg(a). Therefore, deg(a) must be even.
• We conclude that the degree of every other vertex must also be even.
• By the same reasoning, we see that the initial vertex and the final vertex of an Euler path have odd degree, while every other vertex has even degree. So, a graph with an Euler path has exactly two vertices of odd degree.
Md. Hasan (uOttawa) Discrete Structures 10d MdH W22 March 24, 2022 4 / 10
Theorems: Euler Circuits and Paths
A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree.
A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.
Md. Hasan (uOttawa) Discrete Structures 10d MdH W22 March 24, 2022 5 / 10
Applications: Euler Circuits and Paths
• Highway planning
• Utility grid designing
• Routing in communication networks • DNA sequencing
Md. Hasan (uOttawa) Discrete Structures 10d MdH W22 March 24, 2022 6 / 10
Hamilton Paths and Circuits
Definition
A simple path in a graph G that passes through every vertex exactly once is called a Hamiltion path, and a simple circuit in a graph G that passes through every vertex exactly once is called a Hamilton circuit. That is, the simple path x0,x1,…,xn−1,xn in the graph G = (V,E) is a Hamilton path if V = {x0,x1,…,xn−1,xn} and xi ̸= xj for 0 ≤ i < j ≤ n, and the simple circuit x0, x1, ..., xn−1, xn, x0 (with n > 0) is a Hamilton circuit if x0,x1,…,xn−1,xn isaHamiltonpath.
Md. Hasan (uOttawa) Discrete Structures 10d MdH W22 March 24, 2022 7 / 10
Conditions for the Existence of Hamilton Circuits
• There are no simple necessary and sufficient conditions known for the existence of a Hamiton circuit.
• There are some useful sufficient conditions given by:
Dirac’s Theorem: If G is a simple graph with n ≥ 3 vertices such that the
degree of every vertex in G is at least n/2, then G has a Hamilton circuit.
Ore’s Theorem: If G is a simple graph with n vertices with n ≥ 3 vertices such that deg (u) + deg (v ) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit.
Md. Hasan (uOttawa) Discrete Structures 10d MdH W22 March 24, 2022 8 / 10
Applications of Hamilton Paths and Circuits
• Circuit design • TSP
• Gray Codes
Md. Hasan (uOttawa) Discrete Structures 10d MdH W22 March 24, 2022 9 / 10
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 10d MdH W22 March 24, 2022 10 / 10
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com