Graph Theory

Let k be a given positive integer to determine the required connectivity of a graph. Let G be a weighted graph. Determine a minimum-weight k-connected spanning subgraph of G.

If k=1, this problem reduces to find a minimum spanning tree. Kruskal’s algorithm can be applied to find such a tree.

However if k is greater than one, then the above problem becomes difficult and unsolvable. Only if G is a complete graph in which each edge is assigned unit weight, then the problem has a simple solution. It is an m-connected graph H(m,n) on n vertexes and the structure of H(m,n) depends on the parities of m and n; three cases can be considered

Case 1: if m=even, let m=2r, then H(2r,n) is constructed as follows. It has vertexes 0, 1, …, n-1 and two vertexes i and j are joined if i-r<=j<=(i+r)mod(n).
Case 2: if m=odd, and n=even, let m=2r+1, then H(2r+1,n) is constructed by first drawing H(2r,n) and then adding edges joining vertex i to vertex i+(n/2) for 1<=i<=n/2.
Case 3: if m=odd, n=odd, let m=2r+1, then H(2r+1,n) is constructed by first drawing H(2r,n) and then adding edges joining vertex 0 to vertex (n-1)/2 and (n+1)/2 and vertex i to vertex i+(n+1)/2 for 1<=i<=(n-1)/2.

Theorem (Harary Theorem): The graph H(m,n) is m-connected.

The problem is defined as: in a company, there are n workers, X1, X2, …, Xn, and n jobs Y1, Y2, …,Yn. Each worker is qualified for one ore more of these jobs. Can all workers be assigned, one work per job, to jobs for which they are qualified?

First X and Y make up a bipartite graph. This problem can be considered a matching problem to find a perfect matching make every vertex in X is saturated.

In a school, there are m teachers x1, x2, …, xm, and n classes y1, y2, …, yn. Given that teacher xi is required to teach class yj for pij periods, schedule a complete timetable in the minimum possible number of periods.

The above problem is known as timetable problem, and can be solved completely using the theory of edge coloring. We can represent the teaching task by a bipartite graph (X, Y), where X={x1,x2,…,xm) and Y=(y1,y2,…,yn) and vertexes xi and yj is joined by pij edges. Since the graph is bipartite, the edge chromatic number is the maximum degree of the graph. Thus, there is a complete solution to the timetable problem.

Description: in his job, a postman picks up mail at the post office, delivers it, and then returns to the post office. He must cover each street in his area at least once. Subject to this condition, he wishes to choose a route that he can travel at little as possible. This problem is known as Chinese Postman Problem, as it was first considered by a Chinese mathematician.

Mathematically, the Chinese Postman problem can be modelled as a tour in a weighted graph, whose tour weight is minimum. The weight of a tour is defined as the sum of weights of edges traversed by the tour. Such a tour is called optimal tour.

If a graph is eulerian, then an Euler tour of the graph is an optimal tour because an Euler tour is a tour that traverses each edge exactly once. The Chinese postman problem can be easily solved in this case; there is a good algorithm to find an Euler tour in an eulerian graph. The algorithm is called Fleury’s algorithm, due to Fleury.

Fleury’s algorithm:

1. Choose an arbitrary vertex v(0), and set W(0)=v(0).
2. Assume that the trail W(i)=v(0)e(1)v(1)…e(i)v(i) has been selected. Then select an edge e(i+1) from E\{e(1), e(2),…, e(i)} in such a way that
(i) e(i+1) is incident with v(i)
(ii) unless there is no alternative, e(i+1) is not a cut edge of
G(i)=G-{e(1),e(2),…,e(i)}
3. Stop when step 2 can no longer be implemented.

Theorem 1: if a graph is eulerian, then any trail in the graph constructed by Fleury’s algorithm is an Euler tour of G.

For a graph that is not eulerian, to find an optimal tour for the Chinese postman problem, some edges have to traversed for more than once. For a non-eulerian graph, an algorithm to find a minimum weighted tour can be constructed as follows:
(i) find, by duplicating edges, an eulerian weighted supergraph G* of G such that the sum of the weights of the duplicated edges is as small as possible;
(ii) find an Euler tour in G*.

Step (ii) can be easily solved by Fleury’s algorithm; and step (i) can be solved by using an algorithm given by Edmonds and Johnson (1973).

Reference:
Edmonds and Johnson (1973), Matching, Euler tours and the Chinese postman. Math. Programming, 5, 88-124.

Description: a traveling salesman wishes to visit a number of towns and then return to his starting point. Given the traveling times between towns, how should he plan his trip so that he visits each town exactly once and travels in all for as short a time as possible? This is known as traveling salesman problem.

In graph terms, the problem is to find a minimum-weighted Hamilton cycle in a weighted complete graph. We call such a cycle optimal cycle. So far, no efficient solution has been found to the traveling salesman problem, which has been proved to be an NP-complete problem.

There is a possible heuristic for this problem. We can first find a Hamilton cycle C, then by modifying edges on the cycle to find another new Hamilton cycle that has smaller weight than the old one C. After performing a sequence of the above modifications, one is left with a cycle can be improved no more by these methods. This final cycle will almost certainly not be optimal, but it is a reasonable assumption that it will often be fairly good. Moreover, for better accuracy, the procedure can be repeated several times, starting with a different cycle each time.

Neighbor set: for any set S of vertexes in a graph, the neighbor set of S is defined to be the set of all vertexes that are adjacent to vertexes in S, denoted as N(S).

Theorem 1: Let G be a bipartite graph with bipartition (X,Y). The G contains a matching that saturates every vertex in X if and only if |N(S)|>=|S| for all S in X.

Theorem 2: If a graph G is a k-regular bipartite graph with k>0, then the graph has a perfect matching.

Theorem 2 is also called marriage theorem, which can be described as: if every girl in a village knows exactly k boys, and every boy knows exactly k girls, then each girl can marry a boy she knows, and each boy can marry a girl he knows.

A covering of a graph is a subset of K of V such that every edge in the graph has at least one end in K. If covering K is a minimum covering if there is no covering K’ that has |K’|<|K|.

Relationship between matching and covering
If K is a covering of a graph, and M is a matching of the graph, then K contains at least one end of each edge in M. Thus, for any matching M and any covering K, |K|>=|M|. If M* is a maximum matching of the graph, and K* is a minimum covering of the graph, then |M*|<=|K*|. Equality holds when the graph is bipartite. This theorem is due to Konig.

Theorem 3: Let M be a matching and K be a covering such that |M|=|K|. Then M is a maximum matching and K is a minimum covering.

Theorem 4: in a bipartite graph, the number of edges in a maximum matching is equal to the number of vertexes in a minimum covering.

Theorem 5: A graph G has a perfect matching if and only if the number of odd components o(G-S)<=|S| for all S on V.

Theorem 6: Every 3-regular graph without cut edges has a perfect matching.

A trail that traverses every edge of a graph is called an Euler trail of the graph.

A tour of G is a closed walk that traverses each edge of a graph at least once.

An Euler tour is a tour which traverses each edge exactly once (a closed Euler trail). A graph is eulerian if it contains an Euler tour.

Theorem 1: A nonempty connected graph is eulerian if and only if it has no vertexes of odd degree.

Theorem 2: A connected graph has an Euler trail if and only if it has at most two vertexes of odd degree.

Hamilton cycles

A path that contains every vertexes of a graph is called a Hamilton path of the graph.

A cycle that contain every vertexes of a graph is called a Hamilton cycle of the graph.

A graph is Hamiltonian if it contains a Hamilton cycle.

No nontrivial necessary and sufficient condition has been found for a graph to be Hamiltonian, which is so far an unsolved NP-complete problem in graph theory.

Theorem 1: if a graph G is Hamiltonian, then for every subset S of vertex set V, the number of components of the graph G after S is removed should be no greater than the size of set S.

Theorem 2: if a graph is a simple graph with the number of vertexes (v) no smaller than 3 (i.e., v>=3) and smallest vertex degree (delta) no smaller than a half of the number of vertexes (i.e., delta>=v/2), then the graph is Hamiltonian.

Theorem 3: Let G be a simple graph and let u and v be nonadjacent vertexes in G such that the sum of degrees of u and v is no smaller than the total number of vertexes in G, then the graph G is Hamiltonian if and only if G+uv is Hamiltonian.

Definition: The closure of a graph G is the graph obtained from G by recursively joining pairs of nonadjacent vertexes whose degree sum is at least the total number of vertexes until no such pair remains.

Theorem 4: a simple graph is Hamiltonian if and only if its closure is Hamiltonian.

Theorem 5: Let G be a simple graph with the number of vertexes at least 3. If the closure of G is complete, then G is Hamiltonian.

A subset M of E is called a matching in a graph if its elements are links and no two are adjacent in the graph; the two ends of an edge in M are called matched under M. A Matching M saturates a vertex v, and v is M-saturated, if some edge of M is incident with v; otherwise, v is M-unsaturated. If every vertex of the graph is M-saturated, the matching M is perfect. M is a maximum matching if the graph has no matching M’ with a larger size than that of M; obviously, every perfect matching is maximum.

Let M be a matching in a graph. An M-alternating path in the graph is a path whose edges are alternately in E\M and M. An M-augmenting path is an M-alternating path whose origin and terminus are M-unsaturated.

Theorem 1 (Berge): a Matching M in G is a maximum matching if and only if G contains no M-augmenting path.

A k-edge coloring of a loopless graph is an assignment of k colors to the edges of G. The coloring is proper if no two adjacent edges are assigned the same color.

Alternatively, a k-edge coloring can be considered a partition (E1, E2, …, Ek) of E, where Ei denotes a subset of E allocated color i. A proper k-coloring is a k-edge coloring (E1, E2, …, Ek), in which each Ei is a matching.

A graph is defined as k-edge colorable if the graph has a proper k-edge coloring. Every loopless graph is |E|-edge colorable. If l>=k and a graph is k-edge colorable, then the graph is l-edge colorable as well. The edge chromatic number of a graph is defined as a minimum k, which ensure the graph is k-edge colorable. A graph is k-edge-chromatic if k is a minimum integer to ensure the graph to be k-edge colorable.

Because edges incident to a common vertex must be assigned different colors, thus the edge chromatic number must be at the maximum degree of a graph. If a graph is bipartite, then the edge chromatic number is equal to the maximum degree of the graph.

A color i represented at vertex v if some edge incident to v has color i.

Theorem 1: Let a graph be a connected graph that is not an odd cycle. Then the graph has a 2-edge coloring in which both colors are represented at each vertex of degree at least two.

Theorem 2: Given an optimal k-edge coloring of a graph, if there is a vertex u and colors i and j such that i is not represented at u and j is represented at least twice at u, then the component of G[EiUEj] that contains u is an odd cycle.

Theorem 3: If a graph is bipartite, then the edge chromatic number is equal to the maximum degree of the graph.

Theorem 4 (Vizing’s Theorem): If a graph is simple, then edge chromatic number is equal to either the maximum degree of the graph or the maximum degree of the graph plus one.

A vertex cut is a subset of vertexes in a graph whose removal from the graph will cause the remaining graph disconnected. A k-vertex cut is a vertex cut of k elements.

An edge cut is a subset of edges in a graph whose removal from the graph will cause the remaining graph discounted. A k-edge cut is an edge cut of k elements.

A connected graph that has no cut vertexes is called block. Every block with at least three vertexes is 2-connected. A block of graph is a subgraph that is a block and is maximal with respect to this property. Every graph is the union of its blocks.

A group of paths in a graph is called to be internally-disjoint if no vertex of the graph is an internal vertex of more than one path of the group.

Theorem: A graph containing at least 3 vertexes is 2-connected if and only if any two vertexes of the graph are connected at least two internally-disjoint paths.

Theorem: If a graph is 2-connected, then any two vertexes of the graph are on a common cycle.

Theorem: If a graph is a block containing at least 3 vertexes, then any two vertexes of the graph are on a common cycle.

Theorem (Menger’s theorem): A graph containing at lease v+1 vertexes is k-connected if and only if any two distinct vertexes of the graph are connected by at least k internally-disjoint paths.