Chapter 10 Graph¶
10.1 Graph and Graph Models¶
- infinite/finite graph
- multiple edges, multiplicity
| Type | Edges | Multiple Edges Allowed? | Loops Allowed? |
|---|---|---|---|
| Simple graph | Undirected | No | No |
| Multigraph | Undirected | Yes | No |
| Pseudograph | Undirected | Yes | Yes |
| Simple directed graph | Directed | No | No |
| Directed multigraph | Directed | Yes | Yes |
| Mixed graph | Directed and undirected | Yes | Yes |
Construct a precedence graph for the following program
Extra
10.2 Graph Terminology and Special Types of Graphs¶
- adjacent(neighbor)
- adjacent from \(u\)(initial vertex) to \(v\)(terminal/end vertex)
- incident(connect)
- neighborhood \(N(v)\): \(N(A) = \cup_{v \in A}N(v)\)
- degree: deg(\(v\))=0 -> isolated; deg(\(v\))=1 -> pendant
- undirected graph
- The handshaking theorem: \(2m = \sum_{v\in V}deg(v)\) (m edges)
- An undirected graph has an even number of vertices of odd degree
- directed graph
- in-degree: \(deg^-(v)\)
- out-degree: \(deg^+(v)\)
- **\(\sum_{v\in V}deg^-(v) = \sum_{v\in V}deg^+(v) = |E|\)
a loop contributed 1 to both the in-degree and out-degree of the vertex
- undirected graph
Question
Proof: G is an nonempty simple graph, then there must exist vertices with same degrees.
- underlying undirected graph: ignore directions of edges
Special Simple Graph¶
- complete graph \(K_n\): has \(\frac{n(n-1)}{2}\) edges
- cycle \(C_n\)
- wheel \(W_n\)(n>2): can construct from adding an additional vertex to \(C_n\)
- note \(W_n\) has n+1 vertices
- n-cube/n-dimensional hypercube \(Q_n\): two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position
- How to construct \(Q_{n+1}\) NOTE: \(W_3\) = \(K_4\)
Bipartition¶
- bipartite, bipartition
- completely bipartite graph \(K_{m, n}\): every vertex in \(V_1\)(\(|V_1| = m\)) is connected to every vertex in \(V_2\)(\(|V_2| = n\))
- A simple graph is bipartite if and only if it's 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
Regular¶
- regular: if every vertex of this graph has the same degree. -> n-regular
Example
\(K_n\) is n-1-regular
Subgraph¶
- subgraph, proper subgraph, spanning subgraph
- subgraph induced(the max subgraph with given vertices)
- remove or add edges of a graph
- edge contraction(merge two vertex into one)
- remove vertices from a graph
- union of graphs
Example
How many subgraphs with at least one vertex does \(K_n\) have? \(\sum_{k=1}^{n}C(n, k) \times 2^{C(k, 2)}\)
\(W_3: \sum_{k=1}^{4}C(4, k) \times 2^{C(k, 2)}\)
10.3 Representing Graphs and Graph Isomorphism¶
representation:
- adjacency matrix
- NOTE: a loop to itself is 1, not 2
- adjacency list
- incidence matrix: row <-> vertex; column <-> edge
| graph\the sum of the entries in a | row | column |
|---|---|---|
| adjacency matrix for undirected graph | \(deg(v) - loop(v)\) | \(deg(v) - loop(v)\) |
| adjacency matrix for directed graph | \(deg^+(v)\) | \(deg^-(v)\) |
| incidence matrix for undirected graph | \(deg(v) - loop(v)\) | judge if it's a loop |
| incidence matrix for undirected graph |
\(deg(v) - loop(v)\) means the number of edges incident to j\(v\)
isomorphic: one-to-one correspondence of two graphs
- find an isomorphism \(f\) + write the matrix to show \(f\) preserve edges 找到同构的映射+写出相应的矩阵去表明该映射也保证了边的一对一关系
- prove nonisomorphic: use graph invariant
- the number of vertices
- the number of edges
- degree -> degree of adjacent vertex(EXAPMLE10)
- path
- bipartite/complete/wheel
- the length of circuit
- 是否可以二染色
- etc.
Example
- Draw all nonisomorphic undirected simple graph with 4 vertices and 3 edges
- by handshaking theroem, the sum of degree of vertices is 6, and the maximal degree is 3(since 4 vertices)
- we can list 3 possible situation: 3111, 2220, 2211 这里有个不要求的结婚定理可以判断某个序列是否是图
- Draw 3 nonisomorphic undirected simple graph with the sequence of degrees 1,1,1,2,2,3 ![[Pasted image 20240606033357.png]]
- Draw all nonisomorphic spanning subgraphs of \(K_4\) ![[Pasted image 20240606033302.png]]
- prove: isomorphism of simple graphs is equivalence relation
10.4 Connectivity¶
- path/circuit(cycle) -> simple path/circuit: doesn't contain same edge(not same vertex)
- connected/disconnected There is a simple path between every pair of distinct vertices of a connected undirected graph. Proof: Because the graph is connected there is a path between u and v. Throw out all redundant circuits to make the path simple.
- connected components: maximal connected subgraph
- cut vertex(articulation point)
- nonseparable graphs: Connected graphs without cut vertices
- vertex cut(separating set)
- vertex connectivity \(\kappa(G)\): the minimum number of vertices in a vertex cut
- \(0 \le \kappa(G) \le n-1\)
- disconnected graph or single vertex: \(\kappa(G) = 0\)
- connected graph with cut vertex: \(\kappa(G) = 1\)
- \(\kappa(K_n) = n-1\)
-
k-connected(k-vertex-connected): \(\kappa(G) \ge k\) -> 2-connected=biconnected NOTE: \(\kappa(G) \ge k\) rather than \(\kappa(G) = k\)
-
cut edge(bridge)
- edge cut
- edge connectivity \(\lambda(G)\)
- \(0 \le \lambda(G) \le n-2\)
- connected graph with cut vertex: \(\lambda(G) = 1\)
- \(\lambda(K_n) = n-1\) \(\(\kappa(G) \le \lambda(G) \le min_{v\in V}deg(v)\)\)
Example
- Every connected graph except a complete graph has a vertex cut.(EX51)
Strongly connected¶
- strongly/weakly connected
- strongly connected components
Question
- How to determine whether a given directed graph is strongly connected or weakly connected ?
- How to find the strongly connected components in a directed graph ?
Tip
- Some other graph invariants involving path
- Two graphs are isomorphic only if they have simple circuits of the same length.
- Two graphs are isomorphic only if they contain paths that go through vertices so that the corresponding vertices in the two graphs have the same degree.
- We can also use paths to find mapping that are potential isomorphisms.
Path¶
counting paths between vertices \(A^r[i][j]\)(the \((i, j)\)-th entry of \(A^r\)) represent the number of paths of length \(r\) from \(v_i\) to \(v_j\)
10.5 Euler and Hamilton Paths¶
- Euler path: a simple path containing every edge of \(G\)
- Euler circuit: a simple circuit containing every edge of \(G\)
- Euler Graph: a graph contains an Euler circuit
- 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
-
A directed multigraph having no isolated vertices has an Euler circuit if and only if
- the graph is weakly connected
- the in-degree and out-degree of each vertex are equal.
-
A directed multigraph having no isolated vertices has an Euler path but not an Euler circuit if and only if
- the graph is weakly connected
- the in-degree and out-degree of each vertex are equal for all but two vertices, one that has in-degree 1 larger than its outdegree and the other that has out-degree 1 larger than its indegree.
Pseduocode of constructing Euler Circuits
procedure Euler(G: connected multigraph with all vertices of even degree)
circuit := a circuit in G beginning at an arbitrarily chosen vertex with edges
successively added to form a path that returns to this vertex
H := G with the edges of this circuit removed
while H has edges
subcircuit := a circuit in H beginning at a vertex in H that also is an
endpoint of an edge of circuit
H := H with edges of subcircuit and all isolated vertices removed
circuit := circuit with subcircuit inserted at the appropriate vertex
return circuit {circuit is an Euler circuit}
- Hamilton path: a simple path in a graph \(G\) that passes through every vertex exactly once
- Hamilton circuit: a simple circuit in a graph G that passes through every vertex exactly once
- Hamilton graph: a connected graph \(G\) has a Hamilton circuit
- No useful necessary and sufficient conditions for the existence of Hamilton circuit.
- sufficient condition
- DIRAC's theorem: If \(G\) is a simple graph with n vertices with \(n\ge 3\) such that the degree of every vertex in \(G\) is at least \(\frac{n}{2}\),then \(G\) has a Hamilton circuit.
- ORE's theorem: If \(G\) is a simple graph with n vertices with \(n\ge 3\) such that \(deg(u)+deg(v) \ge n\)for every pair of nonadjacent vertices \(u\) and v \(in\) \(G\), then \(G\) has a Hamilton circuit.
-
necessary condition
- a graph with a vertex of degree one cannot have a Hamilton circuit.
-
property
- If a vertex in the graph has degree two, then both edges that are incident with this vertex must be part of any Hamilton circuit.
- When a Hamilton circuit is being constructed and this circuit has passed through a vertex, then all remaining edges incident with this vertex, other than the two used in the circuit , can be removed from consideration
For any nonempty subset S of set V, the number of connected components in G-S <=|S|.
10.6 Short-Path Problems¶
Dijkstra Algorithm