2022/05/02
Basics of graphs
– Reading assignment Ch 10: 10.2, 10.3. – Exercises:
– 10.2: 1-10, 18, 19, 20, 26, 27, 32, 37, 55, 56, 57 – 10.3: 1-21, 54, 56, 57, 58, 63, 77.
Copyright By PowCoder代写 加微信 powcoder
NTNU CSIE Discrete Math 1
2022/05/02
Graph: a mathematical structure consisting of – a set of vertices (or nodes)
– a set of edges (or arcs), within which each element specifies whether two vertices are related.
NTNU CSIE Discrete Math 2
2022/05/02
A graph that has neither a loop nor multiple edges is called a simple graph. – loop: an edge with identical endpoint
– multiple edges: edges that connects the same pair of vertices
A graph is undirected if the relation of adjacency is symmetric.
NTNU CSIE Discrete Math 3
2022/05/02
In an undirected graph,
– If two vertices u and v are connected by an edge, we say u and v are
adjacent / u is a neighbor of v / v is a neighbor of u.
– The number of edges adjacent to a vertex u (or, #neighbors of u) is the
degree of u, denoted by deg(u).
– The set of all neighbors of u is called the neighborhood of u, denoted by N(u).
NTNU CSIE Discrete Math 4
2022/05/02
Theorem [the handshaking lemma]. Let G = (V, E) be an undirected graph. Then
∑deg(v) = 2|E|. v∈V
Corollary. An undirected graph has an even number of vertices of odd degree.
Proof. Let G = (V, E) be the undirected graph, and let V1 and V2 be the sets of odd-degree and even-degree vertices, respectively.
– By the handshaking lemma, we have 2 | E | = ∑ deg(v) + ∑ deg(v). v∈V1 v∈V2
– Since 2|E| − ∑ deg(v) is even and for v ∈ V1 deg(v) is odd, it follows that v∈V2
the number of odd-degree vertices is even.
NTNU CSIE Discrete Math 5
2022/05/02
Special types of graphs – Path
– Complete graph
– hypercube
– bipartite graph
NTNU CSIE Discrete Math 6
2022/05/02
– A path on n vertices, denoted by Pn, is a simple graph consisting of n vertices which can be labeled by v1,v2,…,vn such that two vertices vi and vj areadjacentif |i−j|=1.
– A cycle on n vertices, denoted by Cn, is a simple graph consisting of n vertices which can be labeled by v1,v2,…,vn such that two vertices vi and vj are adjacent if |i−j|=1 or n−1.
– A complete graph on n vertices, denoted by Kn, is a simple graph in which every pair of vertices are adjacent.
Q: How many edges are there in Pn/Cn/Kn? Q: vertex degree?
NTNU CSIE Discrete Math 7
2022/05/02
An n-dimensional hypercube, or n-cube, denoted by Qn, is a graph that has vertices representing the 2n bit strings of length n.
Two vertices are adjacent if the two bit strings differ in exactly one bit position.
NTNU CSIE Discrete Math 8
2022/05/02
Hypercube-based computers
Source: http://www.new-npac.org/projects/cdroms/cewes-1999-06-vol1/foils/cps615arch98/foilsepimagedir/ 066image.html
NTNU CSIE Discrete Math 9
2022/05/02
Can you draw Q4?
– there are 24 vertices.
– How many edges are there?
— What is the degree of a vertex?
0000 1000
0010 1010
0100 1100
0110 1110
NTNU CSIE Discrete Math 10
2022/05/02
Bipartite graph (二分圖)
– A simple graph G is bipartite if its vertex set V can be partitioned into two sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2.
– The pair (V1, V2) is called a bipartition of the vertex set V; each of V1 and V2 is called a partite set.
NTNU CSIE Discrete Math 11
2022/05/02
Theorem. A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color.
Note: this theorem implies an algorithm that determines whether a graph is bipartite or not. (Breadth-First Search)
NTNU CSIE Discrete Math 12
2022/05/02
Questions:
– For n ∈ N, is Pn a bipartite graph?
– For n∈Nand n≥3, is Cn a bipartite graph? – For n∈N∪{0}, is Qn a bipartite graph?
– For n ∈ N, is Kn a bipartite graph?
NTNU CSIE Discrete Math 13
2022/05/02
Let G = (V, E) be a bipartite graph, with (V1, V2) be the bipartition. What is the maximum number of edges can G have?
– We call such a graph “complete bipartite”, denoted by Km,n, where m=|V1| and n=|V2|.
NTNU CSIE Discrete Math 14
2022/05/02
Definition [matching 配對、匹配]. A matching in a simple graph G = (V, E ) is a subset of E such that no two distinct edges in the set are incident with the same vertex.
NTNU CSIE Discrete Math 15
2022/05/02
Definition [complete matching]. Let G be a bipartite graph with bipartition (V1, V2). A complete matching M from V1 to V2 is a matching of G with every vertex in V1 being an endpoint of an edge in M.
NTNU CSIE Discrete Math 16
2022/05/02
Hall’s marriage Theorem [ , 1935].
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. Proof.
(Necessity “the only if part”): the |A| vertices matched with A must lie in N(A), and these vertices are distinct.
NTNU CSIE Discrete Math 17
2022/05/02
(Sufficiency “the if part”):
We prove by induction on the size of |V1|.
– Induction basis: if | V1 | = 1, then we may match the vertex in V1 with any of its neighbor(s).
– Inductive step: assume that theorem holds for | V1 | ≤ k, for some integer k at least 1. We claim that the theorem holds for |V1|=k+1.
— Case (i): all subset A ⊆ V1 of size at most k satisfy |A| < |N(A)|.
-- Case (ii): there exists a subset A ⊆ V1 of size at most k such that |A| = |N(A)|.
NTNU CSIE Discrete Math 18
2022/05/02
Case (i): Remove an edge e, along with its endpoints u and v, and let the resulting bipartite graph be G′ with bipartition (V′, V′).
-ForA⊆V′,|A|<|N(A)|≤|N(A)∩V′|+1.Namely, |A|≤|N(A)∩V′| forall 122
A ⊆ V′ in G′. 1
- By the inductive hypothesis, there is a complete matching from V′ to V′ in
- Along with e we have a complete matching from V′ to V′. 12
NTNU CSIE Discrete Math 19
2022/05/02
Case (ii): (there exists a subset A ⊆ V1 of size at most k such that |A| = |N(A)|.)
- Consider the bipartite graph induced by A ∪ N(A). Since | A | ≤ k, by the inductive hypothesis there is a complete matching M1 from A to N(A).
- Consider the bipartite graph with (V1 − A, V2 − N(A)).
NTNU CSIE Discrete Math 20
2022/05/02
- For B⊆V1−A, let N′(B)=N(B)∩(V2−N(A)).
- Claim: |B| ≤ |N′(B)|.
-- the claim holds since otherwise |B| > |N′(B)|, which implies
| B ∪ A | = | B | + | A | > | N′(B) | + | N(A) | = | N′(B) ∪ N(A) | = | N(A ∪ B) | .
– Since |B| ≤ k, by the inductive hypothesis there is a complete matching
M2 from V1 −A to V2 −N(A).
– The matching M1 ∪ M2 is a complete matching from V1 to V2. ∎
NTNU CSIE Discrete Math 21
2022/05/02
Question: For a given bipartite graph, there may exist no complete matching. In practice, what can you do (by modifying the formulation) if a matching, which may not be complete, is requested?
NTNU CSIE Discrete Math 22
2022/05/02
Maximum matching: Given a graph G = (V,E) and a function w: E → R, find a matching M such that ∑ w(e) is maximum.
– The augmenting path method [Berge, 1957; Kőnig 1931; Petersen 1891]
– Hungarian algorithm [Kuhn, 1955]
– Max-flow min-cut problem [Ford, Fulkerson, 1956; Edmond, Karp, 1972] – the primal-dual approach
NTNU CSIE Discrete Math 23
2022/05/02
Recall (Enumeration):
Given a matrix of numbers, find n elements, with any pair of them on different rows and different columns, such that the sum of the n numbers are maximum.
NTNU CSIE Discrete Math 24
2022/05/02
Recall (Enumeration):
Given a matrix of numbers, find n elements, with any pair of them on different rows and different columns, such that the sum of the n numbers is maximum.
→ Finding a maximum matching in the complete bipartite graph, with partite sets being the sets of row indices and column indices, respectively.
– the weight of edge (i, j) is the element at the corresponding position.
NTNU CSIE Discrete Math 25
2022/05/02
Graph representation – adjacency matrix
0111 1000 1000 1000
– adjacency list
1→2→3→4 2→1
– incidence matrix
e1(1 1 0 0) e2 1 0 1 0 e3 1 0 0 1
NTNU CSIE Discrete Math 26
2022/05/02
Graph isomorphism (同構)
– Two simple graphs G1 and G2 are isomorphic if there exists a bijection
f : V1 → V2 with the property that for a, b ∈ V1, a and b are adjacent in G1 iff f(a) and f(b) are adjacent in G2.
– Function f is called an isomorphism.
NTNU CSIE Discrete Math 27
2022/05/02
Q: Are the following graphs isomorphic?
NTNU CSIE Discrete Math 28
2022/05/02
Exercise (self-complementary graphs)
– For a simple graph G, its complement, denoted by G ̄, is a simple graph
satisfying {u, v} ∈ E(G) ⟺ {u, v} ∉ E(G ̄ ).
– A simple graph G is called self-complementary if G and G ̄ are isomorphic. – Question: For which integers n is Cn self-complementary?
NTNU CSIE Discrete Math 29
2022/05/02
Theorem [Ramsey]. Assume that in a group of six people, each pair of individuals consists of two friends or two enemies. Then, either there are three mutual friends or there are three mutual enemies.
(In other words) Let G be a graph with six vertices. Then either G or G ̄ has K3 as a subgraph.
NTNU CSIE Discrete Math 30
2022/05/02
Proof: Let w be one of the six people. By the pigeonhole principle, either w has three friends or three enemies, say x, y, z.
– Because of symmetry, we assume that x, y, and z are w’s friends.
– If x, y, and z are mutual enemies, then they are the requested three people.
– Otherwise (at least one pair of them are friends), along with w we have three people who are mutual friends. ∎
NTNU CSIE Discrete Math 31
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com