问题求解

Graph Theory

2018-11-10 08:00 CST
2019-12-22 15:33 CST
CC BY-NC 4.0

Introduction

  • order: vertices in G
  • trivial graph: order 1
  • labeled graph
  • word graph
  • incident: u and v are neighbors, then u and v are incident with each other
  • proper subgraph: E or V is different
  • spanning graph: same vertex as G
  • induced graph: if u and v are vertices of F and uv is an edge in G, then uv is in F
  • edge-induced subgraph
  • walk: W = (u=v0, v1, ..., vk = v)
  • open walk: u!=v
  • closed walk: u==v
  • trail: u-v walk in which no edge is traversed more than once
  • path: u-v walk in which no vertices are repeated
  • circuit: a closed trial of length 3 or more
  • cycle: a circuit that repeats no vertex, except for the first and last
  • component
  • geodesic: a u-v path of length d(u,v)
  • complement
  • $K_n$ : complete graph
  • $P_n$ : path (graph)
  • $C_n$: circle (graph)
  • bipartite graph: contains no odd cycle
  • $K_{s,t}$: complete bipartite graph
  • star: $K_{1,t}$ or $K_{s,1}$
  • k-partite graph
  • complete k-partite graph (complete multipartite graphs)
  • union: $G_1 \cup G_2$
  • join: $G+H$ consists of $G\cup H$ and all edges joining a vertex of G and a vertex of H.
  • Cartesian product $G * H$: V($GH$) = V($G$) $$ V($H$), two distinct vertices (u,v) and (x,y) are adjacent if u=x,vy$\in$E($H$) or v=y,ux$\in$E($G$)
  • n-cubes (hypercubes): $Q_n = Q_{n-1} * K_2$, $Q_1 = K_2$
  • multigraph
  • parallel edges: join the same pair of vertices
  • pseudograph: edge can join u and u which is a loop
  • digraph (directed graph): directed edges
  • adjacent to: (u,v)
  • adjacent from: (u,v)
  • oriented graph: at most one of (u,v) and (v,u) is a directed edge
  • oritentation of G

Degrees

  • degree: the number of edges incident with v
  • $N(v)$: the neighborhood of v
  • isolated vertex: $deg_G(v)=0$
  • $\delta(G)$: minimum degree of G
  • $\Delta(G)$: maximum degree of G
  • The First Theorem of Graph Theory: $\sum_{v\in V(G)} deg(v) = 2|E|$
  • r-regular graph: $\delta(G) = \Delta(G) = r$
  • cubic graph: 3-regular graph ($K_4, K_{3,3}, Q_3$, Petersen graph)
  • Petersen graph
  • $H_{r,n}$: Harary graphs, r-regular graph of order n if at least one of r and n is even
  • degree sequence
  • graphical: a finite sequence is a degree sequence of some graph
  • Havel-Hakimi Theorem: non-increaing sequence $s:d_1,d_2,...,d_n$ where $d_1\geq 1$ is graphical iff $s_1:d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n$ is graphical.

Isomorphic Graphs

  • isomorphic: exists a one-to-one $\phi$ from V(G) to V(H) such that $uv\in E(G)$ and $\phi(u)\phi(v)\in E(H)$
  • self-complementary: $G \equiv (\overline H)$

Trees

  • bridge: $G$ is connected, $G-e$ is disconnected
  • acyclic graph: no cycles
  • tree: acyclic connected graph
  • rooted tree
  • forests
  • $w(H)$: $sum_{e\in E(H)}w(e)$
  • spanning tree of G
    • cycle property
    • cut property
  • Kruskal's Algorithm
  • Prim's Algorithm
  • Carley's Theorem: the spanning tree of complete graph of order n is $n^{n-2}$
  • Matrix Tree Theorem: The spanning tree of an arbitrary graph is any cofactor of matrix C

$$\left[\begin{matrix} \deg v_1 & -a_{12} & ... & -a_{1n}\
-a_{21} & \deg v_2 & ... & -a_{2n}\
\vdots & \vdots & \ldots & \vdots\
-a_{n1} & -a_{n2} & ... & \deg v_n \end{matrix}\right]$$

Connectivity

  • cut-vertex: G is connected and G-v is disconnected
  • nonseparable graph: a nontrivial connected graph with no cut-vertices
  • block: a maximal nonseparable subgraph of G
  • vertex-cut: a set U of vertices of G such that G-U is disconnected
  • minimum vertex-cut
  • $\kappa(G)$: vertex-connectivity, the cardinality of a minimum vertex-cut; also the maximum number of disjoint u-v path for which u and v are connected
  • k-connected: $\kappa(G)\geq k$
  • Theorem: 2-connected $\iff$ any 2 adjacent edges of G lie on a common cycle of G
  • edge-cut
  • minimum edge-cut
  • $\lambda(G)$: edge-connectivity
  • k-edge-connected
  • Theorem: $\kappa(G)\leq\lambda(G)\leq\delta(G)$
  • u-v separating set: the set separate G
  • minimum u-v separating set
  • internal vertex of u-v path P: a vertex of P different from u and v
  • internally disjoint: A collection of u-v paths that every two of them have no vertices in common other than u and v
  • Menger's Theorem: minimum cardinality of u-v separating set = maximum number of internally disjoint u-v paths in G
  • Whitney's Theorem: k-connected iff for each pair u, v there are at least k internally disjoint u-v paths

Traversability

  • Eulerian circuit: a circuit contains every edge of G
  • Eulerian graph: graph G contians an Eulerian circuit
  • Eulerian trail: an open trail that contains every edge of G
  • $K\ddot{o}nigsberg$ Bridge Problem
  • Theorem: A nontrivial connected graph G is Eulerian iff every vertex of G has even degree
  • Theorem: A connected graph G contains an Eulerian trail iff exactly two vertices of G have odd degree.
  • Hamiltonian cycle: a cycle in a graph G that contains every vertex of G
  • Hamiltonian graph
  • Hamiltonian path: a path in G contains every vertex of G
  • $k(G)$: number of components in G
  • Theorem: For Hamiltonian Graph, $k(G-S)\leq|S|$
  • Theorem: $n\geq3$, if $degu+degv\geq n$ for each pair u,v of nonadjacent vertices of G, then G is Hamiltonian
  • closure C(G): the graph obtained from G(order n) by recursively joining pairs of nonadjacent vertices whose degree sum is at least n until no such pair remains
  • Theorem: A graph is Hamiltonian iff C(G) is Hamiltonian

Matching

  • independent: a set of edges in which no two edges are adjacent
  • matching: an independent set of edges in G
  • $N(X)$: neighborhood of X
  • Hall's condition: $|N(X)|\geq|X|$ for every nonempty subset X of U
  • Theorem: Let G be a partite graph with partite sets U and W such that $r=|U|\leq|W|$. Then G contains a matching of cardinality r iff G satisfies Hall's condition.
  • a system of distinct representatives
  • perfect matching: a graph of order 2k has a matching M of cardinality k
  • Theorem: Every r-regular bipartite graph has a perfect matching
  • maximum matching: $|M| = \alpha'(G)$
  • edge independence number $\alpha'(G)$: the maximum cardinality of an independent set of edges
  • cover: a vertex and an incident edge are said to cover each other
  • edge cover: a set of edges of G that covers all vertices of G
  • edge covering number $\beta'(G)$: cardinality of minimum edge cover
  • vertice independence: no two vertices in the set are adjacent
  • vertice independence number $\alpha(G)$: maximum cardinality of an independent set of vertices in G
  • maximum independent set
  • vertex cover
  • vertex covering number $\beta(G)$
  • minimum vertex cover
  • Theorem: Gallai Identity: For every graph G of order n containing no isolated vertices, $\alpha'(G)+\beta'(G)=n, \alpha(G)+\beta(G)=n$
  • Konig Theorem: If G is a bipartite graph then $\alpha'(G)=\beta(G)$

Factorization

  • $k_o(G)$: the number of odd components of a graph G.
  • factor-factorization-factorable
  • 1-factorization: there exists 1-factors $F_1, F_2, \cdots, F_r$ of G such that ${E(F_1),E(F_2),\cdots,E(F_r)}$ is a partition of $E(G)$ (e.g. $K_{2k}$,r-regular bipartite graph)
  • Petersen's Theorem: Every 3-regular bridgeless graph contains a 1-factor
  • cyclic factorization
  • Theorem: G is 2-factorable iff G is r-regular for some positive even integer r
  • Hamiltonian factorization
  • Theorem: For every integer $k\geq1$, $K_{2K+1}$ is Hamiltonian-factorable
  • Theorem: For every integer $k\geq1$, $K_{2K}$ can be factored into k-1 Hamiltonian-cycles and a 1-factor
  • F-factorable: G is factorable into factors $F_1, F_2,\dots, F_k$ if ${E(F_1),E(F_2),\dots,E(F_k)}$ is a partition of $E(G)$. Each factor $F_i$ is isomorphic to some graph $F$.
  • Kirkman's Schoolgirl Problem
  • Kirkman triple system: exists iff $n\equiv3(mod\ 6)$
  • decomposable: A graph is decomposable into the subgraphs $H_1,H_2,\dots,H_k$ if ${E(H_1),E(H_2),\dots,E(H_k)}$ is a partition of E(G).
  • decompsition-decomposable
  • H-decomposable and H-decomposition: $H_i$ is isomorphic to some graph H
  • graceful labeling: a one-to-one function $f:V(G)\rightarrow{0,1,2,\dots,m}$ is a graceful labeling if the induced edge labeling $f'(e)=|f(u)-f(v)|$ is one-to-one.
  • graceful graph: G possessing a graceful labeling
  • Conjecture: Every tree is graceful
  • Instant Insanity
  • girth: the length of a smallest cycle in a graph
  • g-cage: a 3-regular graph of minimum order that has girth $g\geq3$ (for $g\leq8$, the g-cages are all sole, $K_4,K_{3,3}$,Petersen,Heawood,McGee,Tutte-Coxeter)
  • Petersen Graph
    • counter-example to 'Every 3-regular bridgeless graph is 1-factorable'
    • The only 5-cage

Distance

  • distance: positive; reflexivity; symmetric; triangle inequatity
  • metric space: (V(G), d)
  • $e(v)$: eccentricity, the distance between v and a vertex farthest from v in G
  • $rad(G)$: radius, $min_{v\in V(G)}e(v)$
  • $diam(G)$: diameter, $max_{v\in V(G)}e(v)$
  • $Cen(G)$: central vertex, e(v)=rad(G)
  • self-centered: Cen(G) = G
  • Theorem: $rad(G)\leq diam(G) \leq 2rad(G)$
  • $Per(G)$: peripheral vertex, e(v)=diam(G)
  • eccentric vertex of u: d(u,v)=e(u)
  • boundary vertex of a vertex u: d(u,w)$\leq$d(u,v) for each neighbor w of v
  • complete vertex (extrem or simplicial vertex): the subgraph of G induced by the neighbors of v is complete
  • $Int(G)$: interior vertex of G if for every vertex u distinct from v, there exists a vertex w such that v lies between u and w
  • Theorem: $G = Bound(G) \cup Int(G)$

Planar Graph

  • planar graph: G can be drawed on a plane without edge crossing
  • plane graph: G is drawed on a plane with no edge crossing
  • regions: connected area divied by plane graph
  • exterior regions: a region without bounding
  • boundary: subgraph corresponding to a region
  • Euler Identity: a planar graph of order n, number of edge m and r regions, n-m+r=2
  • Theorem: a planar graph of order $n\geq3$ then $m\leq3n-6$
  • maximal planar
  • subdivision: one or more vertex of degree 2 are inserted into edge of graph G
  • Kuratowski Theorem: G is planar $\iff$ it does not contain a subgraph of $K_5,K_{3,3}$ or subdivision of $K_5, K_{3,3}$
  • embedding
  • G can be embedded into a plane $\iff$ it can be embedded into a sphere
  • $S_K$ surface of genus k: a surface with k handle
    • $S_0$: sphere
    • $S_1$: torus
  • $\gamma(G)$: minimal integer k that G can be embedded into $S_k$
  • $A$ and $A'$ are in the same region if there is a line connecting there without crossing edges or vertices of G
  • 2-cell: a region in which any closed curves can shrink into a node continuously
  • 2-cell embedding: every region is 2-cell embedding
  • Theorem: If G is 2-cell embedded into $S_k$ then $n-m+r=2-2k$
  • For $n\geq3$, $\gamma(G)\geq\frac{m}{6}-\frac{n}{2}+1$
  • $\gamma(K_n)=\lceil\frac{(n-3)(n-4)}{12}\rceil$
  • $G'$ is got from $G$ by contracting edge e (or identifying the vertices u,v)
  • minor: $H$ can be got be a series of edge contraction from $G$
  • Theorem: If $G$ is a subdivision of $H$, then $H$ is a minor of $G$
  • Theorem: If $H$ is a minor of $G$, $\gamma(H)\leq\gamma(G)$
  • Wagner Theorem: $G$ is planar $\iff$ $K_5,K_{3,3}$ is not a minor of $G$
  • minor of graph theorem: For any set of graph $S$, there are two graph in S that one is a minor of the other

Coloring

  • reducible configuration
  • unavoidable set of reducible configurations
  • dual: a graph corresponding to a map
  • coloring (proper coloring): give every vertex a color and the neighboring ones with different colors (The minimal number of independent set G can be divided into; $c:V(G)\rightarrow\mathbb{N}$, when $uv\in E(G)$, $c(u)=\not c(v)$)
  • $\chi(G)$: chromatic number, the minimal number of color to color G
  • $k$-colorable: $\chi(G)\leq k$
  • Four Color Theorem: For every planar graph G, $\chi(G)\leq4$
  • color class: the independet set division corresponding to a coloring
  • $\chi(G)=1\iff G$ has no edges
  • $\chi(G)=2\iff G$ is a nonempty partite graph
  • $\chi(C_{2n+1})=3$
  • clique: a complete subgraph of graph
  • $\omega(G)$: clique number, the largest order of clique in G, $\beta(G)=\omega(\overline G)$
  • $\chi(G)\geq\omega(G),\chi(G)\geq\frac{n}{\beta(G)}$
  • $\chi(G)\leq 1+\Delta(G)$ (Brook Theorem equal only when G is odd circle or complete graph)
  • $\chi(G)\leq 1+\max(\delta(H))$, H is all possible induced subgraph
  • Grotzsch graph: triangle-free, $\chi(G)=4$
  • edge coloring
  • $\chi_1(G)$: edge chromatic number(chromatic index; Divide $G$ into minimum number of 1-regulation graph)
  • Vizing Theorem: $\chi_1(G)=\Delta G$ or $=\Delta G+1$
  • If $m>\frac{(n-1)\Delta G}{2}$ then $\chi_1(G)=1+\Delta(G)$
  • Konig Theorem: For nonempty partite graph, $\chi_1(X)=\Delta(G)$

Decomposition

  • depth-first forest: predecessor subgraph of DFS
  • Classification of Edges
    • Tree edge: edge in $G_\pi$
    • Back edge: ancestor
    • Forward edge: descendant
    • Cross edge
  • Theorem: There is no Forward edges and Cross edge in undirected graphs.
  • Parenthesis Theorem
  • Nesting of descendant's intervals
  • White-path Theorem
  • DAG: directed acyclic graph $\iff$ no back edge $\iff$ has topo. ordering
  • Toposort: sort vertices in descending order of their finish times
  • Connected Component
  • Strong Connected Component
  • Theorem: Every digraph is a dag of its SCCs
  • Kasaraju's Algorithm
  • Tarjan's Algorithm
  • Semiconnected Digraph
    • Toposort+Check edges($v_i,v_{i+1}$)
  • Biconnected Graph: contains no cut-nodes
  • bicomponenct: a maximal biconnected subgraph

SSSP & APSP

  • Properties of shortest path and relaxation
    • Triangle inequality
    • Upper-bound property
    • No-path property
    • Convergence property
    • Path-relaxation property
    • Predecessor-subgraph property
  • Bellman-Ford Algorithm
  • Dijkstra Algorithm
    • Array: $O(V^2)$
    • Min-heap: $O(ElogV)$
    • Fib-heap: $O(VlogV+E)$
  • DAG-SSSP
  • Shortest Simple Path problem: NP
  • Difference constraints
    • Constraint graph
  • Floyed-Warshall Algorithm
  • Transitive closure of a directed graph

Flow

  • Flow network: $G=(V,E)$
  • Capacity constraint: For all $u,v\in V$, we require $0\leq f(u,v)\leq c(u,v)$
  • Flow conservation: For all $u\in V-{s,t}$, $\sum_{v\in V}f(v,u)=\sum_{v\in V}f(u,v)$
  • Ford-Fulkerson Method
  • net flow: $f(S,T)=\sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in S}\sum_{v\in T}f(v,u)$
  • capacity of cut: $c(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v)$
  • Max-flow min-cut theorem: The maximum flow is equal to the minimum cut capacity
  • Basic Ford-Fulkerson Algorithm: $O(|f^*|E)$
  • Edmonds-Karp Algorithm: $O(VE^2)$