2022/05/13
Paths and circuits
– Reading assignment Ch 10: 10.4, 10.5.
– Exercises:
Copyright By PowCoder代写 加微信 powcoder
– 10.4: 19, 21, 24, 30, 44, 45
– 10.5: 1-8, 40, 41, 45, 46, 47, 48 – 6.2: 4, 12, 25, 26, 36, 38, 42.
NTNU CSIE Discrete Math 1
2022/05/13
In graph theory, the word “path” may refer to – a specific kind of graphs, namely Pn, or
– a sequence of edges in a given graph, depicting a route between two (not necessarily distinct) vertices
NTNU CSIE Discrete Math 2
2022/05/13
Let G be an undirected graph, and let u, v ∈ V(G).
-ApathoflengthnfromutovinGisasequenceofedgese1,…,en for which there exists a sequence x0 = u, x1, . . . , xn−1, xn = v of vertices such that ei, for i ∈ [n], has endpoints xi−1 and xi.
– If G is simple, then the path can be denoted by the vertex sequence x0, x1, …, xn.
– We say that “the path passes through the vertices x1, …, xn−1” or “traverse the edges e1,…,en”.
NTNU CSIE Discrete Math 3
2022/05/13
Alternative terminology in graph theory – path ↔ walk
– circuit ↔ closed walk (a path/walk with identical start and end) – simple path ↔ trail (no repeated edges)
– elementary path ↔ path (no repeated vertices)
– circuit with no repeated vertices ↔ cycle
NTNU CSIE Discrete Math 4
2022/05/13
– 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.
– A subgraph of a graph G = (V, E) is a graph G′ = (V′, E′) with V′ ⊆ V and E′ ⊆ E.
– A graph G′is a proper subgraph of G if it is a subgraph of G and G′≠G.
– 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.
NTNU CSIE Discrete Math 5
2022/05/13
Question: Let G be a simple graph with n vertices and m edges.
– If G is connected, what is the largest and the least possible values of m?
– If G has k components, what is the least possible value of m (depending on n and k)?
NTNU CSIE Discrete Math 6
2022/05/13
Eulerian paths and circuits
– An Eulerian circuit in a graph G is a simple circuit containing every edge
– An Eulerian path in G is a simple path containing every edge of G.
Theorem. A connected multigraph has an Eulerian circuit if and only if the degree of each vertex is even.
NTNU CSIE Discrete Math 7
2022/05/13
Proposition. Let G be a connected graph with every vertex of even degree. Then G has an Eulerian circuit.
NTNU CSIE Discrete Math 8
2022/05/13
Proof: We prove by induction on the number of edges m.
– For m = 0, the graph consists of one vertex, which itself is a circuit.
– Assume the proposition holds for all m with 0 ≤ m ≤ k, where k is an integer at least 0.
– Let m = k + 1. There exists a vertex, say v0, with degree greater than zero. – There must be a circuit C′ = v0, e0, v1, e1, v2, e2, …, vx, ex, v0 starting from (and
ending at) v0.
– Every vertex of G − C′ has even degree, and by the induction hypothesis there is an Eulerian circuit for each component.
NTNU CSIE Discrete Math 9
2022/05/13
– Let C1, C2, …, Cy be the Eulerian circuits of the components of G − C′. – Each Ci shares a common vertex with C′.
– Let vij, j ∈ [y], be a vertex of C′ that belongs to Cj.
– Assume that ij < ij′ for j < j′. Then an Eulerian circuit of G can be built by
traversing the edges in the following way:
v0 ⇝C′ vi1 ⇝C1 vi1 ⇝C′ vi2 ⇝C2 vi2 ⇝C′ ⋯⇝C′ viy ⇝Cy viy ⇝C′ vx →v0. ∎
NTNU CSIE Discrete Math 10
2022/05/13
Algorithm: Constructing Eulerian circuits.
input : G, a connected multigraph with all vertices of even degree output: C, an Eulerian circuit of G
1 2 3 4 5 6 7
C ← an arbitrary circuit in G
H ← G with the edges of C removed while H has edges do
| C′ ← a circuit in H beginning at a vertex that is a vertex of C | H ← H with the edges of C′ removed
| C ← C with C′ inserted “appropriately”
NTNU CSIE Discrete Math 11
2022/05/13
NTNU CSIE Discrete Math 12
2022/05/13
Hamiltonian paths and circuits
- A simple path in a graph G that passes through every vertex exactly once is called a Hamiltonian path.
- A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit.
NTNU CSIE Discrete Math 13
2022/05/13
- Show a graph that has both an Eulerian circuit and a Hamiltonian circuit. - Show a graph that has an Eulerian circuit but has no Hamiltonian circuit. - Show a graph that has no Eulerian circuit but has a Hamiltonian circuit.
- Show a graph that has neither an Eulerian circuit nor a Hamiltonian circuit.
NTNU CSIE Discrete Math 14
2022/05/13
Theorem. [Dirac's condition] If G is a simple graph with n vertices with
n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a Hamiltonian circuit.
Theorem. [Ore's condition] If G is a simple graph with n vertices with n ≥ 3 such that deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a Hamiltonian circuit.
NTNU CSIE Discrete Math 15
2022/05/13
Proof (Ore's condition is sufficient): - G is connected.
-- Otherwise there are two components C1 and C2. Let n1 and n2 be the number of vertices in the two components, respectively.
-- For vertex u1 in C1 and u2 in C2, we have
deg(u1) + deg(u2) ≤ n1 − 1 + n2 − 1 ≤ n − 2,
which contradicts the assumption.
NTNU CSIE Discrete Math 16
2022/05/13
- Let v1,v2,...,vp be a longest path with no repeated vertices. We claim that this path is Hamiltonian, i.e., every vertex is on the path.
- Observe that all neighbors of v1 and vp are on this longest path. (why?) - Any set of deg(v1) distinct vertices of the path contains either vp or a
neighbor of vp.
-- Otherwise, deg(v1) + deg(vp) ≤ deg(v1) + (p − 1) − deg(v1) < n.
- There is a neighbor vk of v1 such that vk−1 is a neighbor of vp. (why?)
- v1,v2,...,vk−1,vp,vp−1,...,vk,v1 is a circuit.
- Every vertex is on the path. Otherwise, the path can be extended. ∎
NTNU CSIE Discrete Math 17
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com