Graph Theory Cheatsheet

Cheatsheet Content

### 1. Introduction to Graph Theory #### What is a Graph? - A graph $G = (V, E)$ consists of a set of vertices $V$ and a set of edges $E$. - Each edge connects two vertices. - **Self-loop:** An edge connecting a vertex to itself. - **Parallel edges:** Multiple edges connecting the same pair of vertices. - **Simple graph:** No self-loops or parallel edges. - **Degree of a vertex $d(v)$:** Number of edges incident to $v$, with self-loops counted twice. - **Handshaking Lemma:** $\sum_{v \in V} d(v) = 2|E|$. - **Theorem 1-1:** The number of vertices with odd degree in any graph is always even. #### Types of Graphs - **Finite graph:** Finite number of vertices and edges. - **Infinite graph:** Infinite number of vertices or edges. - **Null graph:** A graph with no edges. - **Isolated vertex:** A vertex with degree zero. - **Pendant vertex:** A vertex with degree one. - **Regular graph:** All vertices have the same degree. ### 2. Paths and Circuits #### Isomorphism - Two graphs $G$ and $G'$ are **isomorphic** if there's a one-to-one correspondence between their vertices and edges that preserves incidence. - Isomorphic graphs have the same number of vertices, edges, and degree distribution. #### Subgraphs - **Subgraph $g$ of $G$:** $V(g) \subseteq V(G)$ and $E(g) \subseteq E(G)$, with incidence preserved. - **Edge-disjoint subgraphs:** No common edges. - **Vertex-disjoint subgraphs:** No common vertices. #### Walks, Paths, and Circuits - **Walk:** An alternating sequence of vertices and edges, starting and ending with a vertex. Edges are not repeated. - **Closed walk:** Starts and ends at the same vertex. - **Open walk:** Starts and ends at different vertices. - **Path:** An open walk where no vertex is repeated (except possibly start/end for closed walks). - **Length of a path:** Number of edges in it. - **Circuit (Cycle):** A closed walk where no vertex is repeated (except start/end). #### Connectedness - **Connected graph:** A path exists between every pair of vertices. - **Disconnected graph:** Not connected. - **Component:** A maximal connected subgraph of a disconnected graph. - **Theorem 2-1:** A graph $G$ is disconnected iff $V$ can be partitioned into $V_1, V_2$ such that no edge connects $V_1$ and $V_2$. - **Theorem 2-2:** If a graph has exactly two odd-degree vertices, there must be a path joining them. #### Euler Graphs - **Euler line:** A closed walk that traverses every edge exactly once. - **Euler graph:** A graph containing an Euler line. - **Theorem 2-4:** A connected graph $G$ is an Euler graph iff all its vertices are of even degree. - **Unicursal line (Open Euler line):** An open walk traversing every edge exactly once. - **Theorem 2-5:** A connected graph with $2k$ odd vertices has $k$ edge-disjoint unicursal graphs covering all edges. #### Hamiltonian Paths and Circuits - **Hamiltonian circuit:** A closed walk that visits every vertex exactly once (except start/end). - **Hamiltonian path:** A path that visits every vertex exactly once. - **Complete graph:** A simple graph where every pair of vertices is connected by an edge. - **Theorem 2-8:** In a complete graph with $n$ odd vertices ($\ge 3$), there are $(n-1)/2$ edge-disjoint Hamiltonian circuits. - **Traveling Salesman Problem:** Find the shortest Hamiltonian circuit in a weighted complete graph. ### 3. Trees and Fundamental Circuits #### Trees - **Tree:** A connected graph without any circuits. - **Properties of Trees:** - **Theorem 3-1:** There is one and only one path between every pair of vertices in a tree. - **Theorem 3-3:** A tree with $n$ vertices has $n-1$ edges. - **Theorem 3-4:** Any connected graph with $n$ vertices and $n-1$ edges is a tree. - **Theorem 3-5:** A graph is a tree iff it is minimally connected. - **Theorem 3-7:** In any tree (with two or more vertices), there are at least two pendant vertices. #### Distance and Centers in a Tree - **Distance $d(v_i, v_j)$:** Length of the shortest path between $v_i$ and $v_j$. - **Eccentricity $E(v)$:** Maximum distance from $v$ to any other vertex in the graph. - **Center:** A vertex with minimum eccentricity. - **Theorem 3-9:** Every tree has either one or two centers. - **Radius:** Eccentricity of a center. - **Diameter:** Length of the longest path in a tree. #### Rooted and Binary Trees - **Rooted tree:** A tree with a designated root vertex. - **Binary tree:** A tree with exactly one vertex of degree two, and all other vertices of degree one or three. - Number of vertices $n$ is always odd. - Number of internal vertices is one less than the number of pendant vertices. - **Level of a vertex:** Distance from the root. - **Height of a tree:** Maximum level of any vertex. - **Path length:** Sum of path lengths from the root to all pendant vertices. - **Weighted path length:** $\sum l_j w_j$ for pendant vertex $v_j$ with weight $w_j$ at level $l_j$. #### Counting Trees - **Labeled trees:** Vertices are distinguishable. - **Cayley's Theorem (3-10):** The number of labeled trees with $n$ vertices ($n \ge 2$) is $n^{n-2}$. - **Unlabeled trees:** Vertices are indistinguishable. More complex counting methods (generating functions, partitions, Pólya's theorem). #### Spanning Trees - **Spanning tree:** A subgraph of a connected graph $G$ that is a tree and includes all vertices of $G$. - **Theorem 3-11:** Every connected graph has at least one spanning tree. - **Branch:** An edge in a spanning tree. - **Chord:** An edge in $G$ not in a given spanning tree. - **Theorem 3-12:** For a connected graph with $n$ vertices and $e$ edges, any spanning tree has $n-1$ branches and $e-n+1$ chords. - **Rank $r = n-k$:** Number of branches in a spanning tree of a $k$-component graph. - **Nullity $\mu = e-n+k$:** Number of chords in a $k$-component graph. Also called cyclomatic number. #### Fundamental Circuits and Cut-Sets - **Fundamental circuit:** A circuit formed by adding one chord to a spanning tree. There are $\mu$ fundamental circuits. - **Theorem 3-13:** A connected graph is a tree iff adding an edge between any two vertices creates exactly one circuit. - **Theorem 3-15:** Starting from any spanning tree, all other spanning trees can be obtained by successive cyclic exchanges (replacing one branch with one chord). #### Spanning Trees in a Weighted Graph - **Weight of a spanning tree:** Sum of weights of its branches. - **Shortest (Minimal) spanning tree:** A spanning tree with the smallest weight. - **Kruskal's Algorithm:** Sort edges by weight, add smallest edges that don't form a circuit. - **Prim's Algorithm:** Start with a vertex, grow tree by adding closest connected vertex. - **Degree-constrained shortest spanning tree:** Shortest spanning tree with vertex degrees limited. ### 4. Cut-Sets and Cut-Vertices #### Cut-Sets - **Cut-set:** A minimal set of edges whose removal disconnects a connected graph. - **Properties of Cut-Sets:** - **Theorem 4-1:** Every cut-set in a connected graph $G$ must contain at least one branch of every spanning tree of $G$. - **Theorem 4-3:** Every circuit has an even number of edges in common with any cut-set. - **Fundamental cut-set:** A cut-set containing exactly one branch of a spanning tree. There are $r$ fundamental cut-sets. - **Theorem 4-4:** The ring sum of any two cut-sets is either a third cut-set or an edge-disjoint union of cut-sets. - **Theorem 4-5:** With respect to a given spanning tree $T$, a chord $c_i$ that determines a fundamental circuit $\Gamma$ occurs in every fundamental cut-set associated with the branches in $\Gamma$ and in no other. #### Connectivity and Separability - **Edge connectivity:** The minimum number of edges in a cut-set. - **Vertex connectivity (Connectivity):** The minimum number of vertices whose removal disconnects the graph. - **Separable graph:** A connected graph with vertex connectivity one. - **Cut-vertex (Articulation point):** A vertex whose removal disconnects the graph. - **Theorem 4-7:** A vertex $v$ is a cut-vertex iff there exist two vertices $x, y$ such that every path between $x, y$ passes through $v$. - **Theorem 4-8:** Edge connectivity $\le$ minimum vertex degree. - **Theorem 4-9:** Vertex connectivity $\le$ edge connectivity. - **Theorem 4-10:** Max vertex connectivity for $n$ vertices, $e$ edges is $\lfloor 2e/n \rfloor$. - **$k$-connected graph:** Vertex connectivity is $k$. - **Theorem 4-11 (Menger's Theorem - Vertex):** A graph is $k$-connected iff every pair of vertices is joined by $k$ or more vertex-disjoint paths. - **Theorem 4-12 (Menger's Theorem - Edge):** A graph has edge connectivity $k$ iff every pair of vertices is joined by $k$ or more edge-disjoint paths. #### Network Flows - **Max-Flow Min-Cut Theorem (4-13):** The maximum flow possible between two vertices $s, t$ in a network equals the minimum capacity of all cuts separating $s$ from $t$. #### Isomorphism Generalizations - **1-isomorphism:** Two graphs $G_1, G_2$ are 1-isomorphic if their blocks are isomorphic. - **Block:** A maximal nonseparable subgraph. - **2-isomorphism:** Two graphs are 2-isomorphic if they become isomorphic after repeated application of splitting a cut-vertex or splitting a pair of vertices whose removal disconnects the graph, and then rejoining. - **Theorem 4-15 (Whitney's Theorem):** Two graphs are 2-isomorphic iff they have circuit correspondence (one-to-one correspondence between edges and circuits). ### 5. Planar and Dual Graphs #### Planarity - **Planar graph:** Can be drawn on a plane without edges crossing. - **Nonplanar graph:** Cannot be drawn on a plane without edges crossing. - **Embedding:** A drawing of a graph on a surface without edge crossings. - **Plane representation:** An embedding of a planar graph on a plane. - **Theorem 5-3 (Fary's Theorem):** Any simple planar graph can be embedded in a plane with straight line segments for edges. - **Region (Face/Mesh):** Areas into which a plane representation divides the plane. - **Infinite region:** The unbounded region. - **Theorem 5-4:** A graph can be embedded on a sphere iff it can be embedded on a plane. - **Euler's Formula (5-6):** For a connected planar graph with $n$ vertices, $e$ edges, and $f$ regions, $f = e - n + 2$. - **Corollary:** In a simple, connected planar graph with $n \ge 3$ vertices, $e \le 3n-6$. (Necessary condition for planarity). #### Kuratowski's Graphs - **Kuratowski's First Graph ($K_5$):** Complete graph on 5 vertices (nonplanar). - **Kuratowski's Second Graph ($K_{3,3}$):** Complete bipartite graph with 3 vertices in each partition (nonplanar). - **Theorem 5-9 (Kuratowski's Theorem):** A graph is planar iff it does not contain a subgraph homeomorphic to $K_5$ or $K_{3,3}$. - **Homeomorphic graphs:** One can be obtained from the other by inserting/removing degree-two vertices. #### Dual Graphs - **Geometric dual $G^*$ of $G$:** Constructed by placing a vertex in each region of $G$ and connecting them if their regions share an edge. - **Properties of Duals:** - If $G$ has $n, e, f$ values, $G^*$ has $n^*=f, e^*=e, f^*=n$. - $G$ and $G^*$ are dual graphs. - **Theorem 5-7 (Whitney's Theorem):** The spherical embedding of every planar 3-connected graph is unique. - **Theorem 5-10:** All duals of a planar graph are 2-isomorphic. - **Combinatorial dual:** - **Theorem 5-11:** $G_1, G_2$ are duals iff there's a 1-to-1 correspondence between edges such that a set of edges in $G_1$ forms a circuit iff the corresponding set in $G_2$ forms a cut-set. - **Theorem 5-12 (Whitney's Theorem):** A graph has a dual iff it is planar. - **Self-dual graph:** A graph isomorphic to its own dual. #### Planarity Criteria - **Theorem 5-13 (MacLane's Theorem):** A graph $G$ is planar iff there exists a complete set of basic circuits such that no edge appears in more than two of these circuits. #### Thickness and Crossings - **Thickness:** Minimum number of planar subgraphs whose union is $G$. - **Crossing number:** Minimum number of edge crossings in any plane drawing of $G$. ### 6. Vector Spaces of a Graph #### Algebraic Systems - **Semigroup:** Set with a closed, associative binary operation. - **Monoid:** Semigroup with an identity element. - **Group:** Monoid with an inverse for every element. - **Abelian (Commutative) Group:** Group with a commutative operation. - **Ring:** Abelian group with a second closed, associative, distributive operation. - **Field:** Commutative ring with unity where every non-zero element has a multiplicative inverse. - **Galois Field GF(m):** Set $\{0, 1, \dots, m-1\}$ with modulo $m$ arithmetic. It's a field iff $m$ is prime. - **GF(2):** Used for graph vector spaces (addition is XOR, multiplication is AND). #### Vector Spaces - **Vector space over a field F:** Set of k-tuples (vectors) from F, with vector addition and scalar multiplication satisfying axioms. #### Vector Space Associated with a Graph ($W_G$) - For a graph $G$ with $e$ edges, $W_G$ is an $e$-dimensional vector space over $GF(2)$. - Each vector is an $e$-tuple $(x_1, \dots, x_e)$ where $x_i=1$ if edge $e_i$ is in a subgraph, $x_i=0$ otherwise. - Vector addition corresponds to the ring sum of subgraphs. #### Basis Vectors - **Linearly independent vectors:** $c_1X_1 + \dots + c_rX_r = 0$ iff $c_i=0$. - **Basis:** A set of linearly independent vectors that spans the space. - The natural basis for $W_G$ consists of vectors representing single edges. #### Circuit and Cut-Set Subspaces - **Circuit vector:** Represents a circuit or union of edge-disjoint circuits. - **Circuit Subspace ($W_\Gamma$):** The set of all circuit vectors forms a subspace. - **Theorem 6-6:** Vectors corresponding to fundamental circuits form a basis for $W_\Gamma$. - **Dimension of $W_\Gamma$:** Nullity $\mu = e-n+k$. - **Cut-set vector:** Represents a cut-set or union of edge-disjoint cut-sets. - **Cut-set Subspace ($W_S$):** The set of all cut-set vectors forms a subspace. - **Theorem 6-7:** Vectors corresponding to fundamental cut-sets form a basis for $W_S$. - **Dimension of $W_S$:** Rank $r = n-k$. #### Orthogonal Vectors and Spaces - **Dot product (over GF(2)):** $X \cdot Y = \sum x_i y_i \pmod 2$. - **Orthogonal vectors:** Dot product is zero. - **Orthogonal subspaces:** Every vector in one is orthogonal to every vector in the other. - **Theorem 6-9:** The circuit subspace ($W_\Gamma$) and the cut-set subspace ($W_S$) are orthogonal to each other. - This is because a circuit and a cut-set always share an even number of edges. #### Intersection and Join of $W_\Gamma$ and $W_S$ - **Intersection ($W_\Gamma \cap W_S$):** Vectors common to both subspaces. - **Join ($W_\Gamma \lor W_S$):** Smallest subspace containing both $W_\Gamma$ and $W_S$. - $\dim(W_\Gamma \lor W_S) = \dim W_\Gamma + \dim W_S - \dim(W_\Gamma \cap W_S)$. - **Orthogonal complements:** Subspaces are orthogonal and their join is the entire space. - **Theorem 6-10:** $W_\Gamma$ and $W_S$ are orthogonal complements iff $W_\Gamma \cap W_S = \{0\}$. ### 7. Matrix Representation of Graphs #### Incidence Matrix ($A$) - **Definition:** $n \times e$ matrix where $a_{ij}=1$ if edge $j$ is incident on vertex $i$, $0$ otherwise. (For undirected graphs, over GF(2)). - **Properties:** - Each column has exactly two $1$s. - Row sum is vertex degree. - Isolated vertex $\implies$ row of $0$s. - Parallel edges $\implies$ identical columns. - Disconnected graph $\implies$ block-diagonal matrix. - **Theorem 7-1:** $G_1, G_2$ are isomorphic iff $A(G_1), A(G_2)$ differ by row/column permutations. - **Theorem 7-2:** For a connected graph with $n$ vertices, $\text{rank}(A) = n-1$. - **Reduced incidence matrix ($A_f$):** $A$ with one row (reference vertex) removed. Its rank is $n-1$. - **Theorem 7-3:** An $(n-1) \times (n-1)$ submatrix of $A(G)$ is nonsingular iff its columns represent a spanning tree. #### Circuit Matrix ($B$) - **Definition:** $q \times e$ matrix where $b_{ij}=1$ if edge $j$ is in circuit $i$, $0$ otherwise. (Over GF(2)). - **Properties:** - Each row is a circuit vector. - Self-loop $\implies$ row with single $1$. - Disconnected graph $\implies$ block-diagonal matrix. - **Theorem 7-4:** Every row of $B$ is orthogonal to every row of $A$ ($B A^T = 0 \pmod 2$). - **Fundamental circuit matrix ($B_f$):** Rows correspond to fundamental circuits. Can be partitioned as $[I_\mu | B_t]$, where $\mu = e-n+k$. - **Theorem 7-5:** For a connected graph, $\text{rank}(B) = \mu = e-n+1$. #### Cut-Set Matrix ($C$) - **Definition:** $k \times e$ matrix where $c_{ij}=1$ if edge $j$ is in cut-set $i$, $0$ otherwise. (Over GF(2)). - **Properties:** - Each row is a cut-set vector. - Column of $0$s $\implies$ self-loop. - Parallel edges $\implies$ identical columns. - For nonseparable graph, $C$ contains $A$. - **Theorem 7-6:** For a connected graph, $\text{rank}(C) = n-1$. - **Fundamental cut-set matrix ($C_f$):** Rows correspond to fundamental cut-sets. Can be partitioned as $[C_c | I_{n-1}]$. #### Relationships Among $A_f$, $B_f$, and $C_f$ - For a spanning tree: $B_f = [I_\mu | B_t]$ and $C_f = [C_c | I_{n-1}]$. - $B_t = C_c^T$ and $B_c = C_t^T$ (over GF(2)). - $A_f = [A_c | A_t]$. - $A_f \cdot B_f^T = 0 \pmod 2$. #### Path Matrix ($P(x,y)$) - **Definition:** Rows correspond to paths between $x$ and $y$, columns to edges. $p_{ij}=1$ if edge $j$ is in path $i$, $0$ otherwise. - **Theorem 7-7:** $A \cdot P(x,y)^T = M$, where $M$ has $1$s in rows $x, y$ and $0$s elsewhere. #### Adjacency Matrix ($X$) - **Definition:** $n \times n$ symmetric binary matrix for simple graphs. $x_{ij}=1$ if an edge exists between $i$ and $j$, $0$ otherwise. (Over integers). - **Properties:** - Diagonal entries are $0$ for no self-loops. - Does not represent parallel edges. - Row/column sum is vertex degree. - Isomorphism $\iff X(G_1) = R^{-1} X(G_2) R$ for permutation matrix $R$. - Disconnected graph $\implies$ block-diagonal matrix. - **Powers of $X$ ($X^r$):** - **Theorem 7-8:** The $ij$-th entry in $X^r$ is the number of different edge sequences of $r$ edges between $v_i$ and $v_j$. - **Corollary A:** Distance between $v_i, v_j$ is $k$ iff $k$ is smallest integer for which $ij$-th entry in $X^k$ is nonzero. - **Corollary B:** If $Y = \sum_{r=1}^{n-1} X^r$, $G$ is disconnected iff some entry in $Y$ is zero. ### 8. Coloring, Covering, and Partitioning #### Chromatic Number ($\kappa$) - **Proper coloring:** Assigning colors to vertices such that no two adjacent vertices have the same color. - **$\kappa$-chromatic graph:** A graph requiring $\kappa$ colors for proper coloring. - **Properties:** - Graph with $\ge 1$ edge is at least 2-chromatic. - Complete graph $K_n$ is $n$-chromatic. - Circuit $C_n$ is 2-chromatic if $n$ is even, 3-chromatic if $n$ is odd. - **Theorem 8-1:** Every tree with two or more vertices is 2-chromatic. - **Theorem 8-2 (König):** A graph with at least one edge is 2-chromatic iff it has no circuits of odd length. - **Theorem 8-3:** If $d_{max}$ is max degree, $\kappa \le 1 + d_{max}$. - **Bipartite graph:** Vertex set $V$ partitioned into $V_1, V_2$ such that edges only connect $V_1$ and $V_2$. (Equivalent to 2-chromatic for connected graphs). #### Chromatic Partitioning - **Independent set (Internally stable set):** A set of vertices where no two are adjacent. - **Maximal independent set:** An independent set to which no more vertices can be added. - **Independence number $\beta(G)$:** Number of vertices in the largest independent set. - **Dominating set (Externally stable set):** A set of vertices that dominates all other vertices (either in the set or adjacent to one in the set). - **Minimal dominating set:** A dominating set from which no vertex can be removed. - **Domination number $\alpha(G)$:** Number of vertices in the smallest minimal dominating set. - $\alpha(G) \le \beta(G)$. - Every maximal independent set is a dominating set. - **Uniquely colorable graph:** Has only one chromatic partition. #### Chromatic Polynomial ($P_n(\lambda)$) - $P_n(\lambda)$: Number of ways to properly color a graph with $\lambda$ or fewer colors. - **Theorem 8-4:** An $n$-vertex graph is a complete graph iff $P_n(\lambda) = \lambda(\lambda-1)\dots(\lambda-n+1)$. - **Theorem 8-5:** An $n$-vertex graph is a tree iff $P_n(\lambda) = \lambda(\lambda-1)^{n-1}$. - **Theorem 8-6:** If $a, b$ are nonadjacent, $P_n(\lambda)$ of $G = P_n(\lambda)$ of $G' + P_{n-1}(\lambda)$ of $G''$ (where $G'$ adds edge $(a,b)$, $G''$ fuses $a,b$). #### Matchings - **Matching:** A subset of edges where no two edges are adjacent. - **Maximal matching:** A matching to which no more edges can be added. - **Largest maximal matching:** Maximal matching with the most edges. - **Matching number:** Number of edges in a largest maximal matching. - **Complete matching:** In bipartite graph $V_1 \to V_2$, every vertex in $V_1$ is matched. - **Theorem 8-7:** Complete matching of $V_1 \to V_2$ exists iff every subset of $r$ vertices in $V_1$ is collectively adjacent to $\ge r$ vertices in $V_2$. - **Deficiency $\delta(G)$:** Max value of $r-q$ (where $q$ is number of adjacent vertices in $V_2$ for $r$ vertices in $V_1$). Complete matching exists iff $\delta(G) \le 0$. - **Theorem 8-9:** Max matched vertices in $V_1$ is $|V_1| - \delta(G)$. #### Coverings - **Edge covering (Covering):** A set of edges where every vertex is incident on at least one edge in the set. - **Minimal covering:** A covering from which no edge can be removed. - **Covering number:** Number of edges in the smallest minimal covering. - **Theorem 8-10:** A covering $g$ is minimal iff $g$ contains no paths of length three or more. - **Dimer covering (1-factor, Perfect matching):** A covering where every vertex is of degree one. #### Four-Color Problem - **Region coloring (Map coloring):** Proper coloring of regions in a planar graph. - **Four-color conjecture:** Every planar graph can be properly colored with four colors. (Still unproven, but verified by computer for a vast number of cases). - **Five-Color Theorem (8-11):** The vertices of every planar graph can be properly colored with five colors. ### 9. Directed Graphs #### Directed Graph (Digraph) - **Definition:** A graph where each edge has a direction (from initial to terminal vertex). - **Out-degree $d^+(v)$:** Number of edges leaving $v$. - **In-degree $d^-(v)$:** Number of edges entering $v$. - $\sum d^+(v) = \sum d^-(v) = |E|$. - **Isomorphic digraphs:** Corresponding undirected graphs are isomorphic, and edge directions agree. #### Types of Digraphs - **Simple digraph:** No self-loops or parallel edges. - **Asymmetric digraph:** At most one edge between a pair of vertices (can have self-loops). - **Symmetric digraph:** If $(u,v)$ is an edge, $(v,u)$ is also an edge. - **Complete symmetric digraph:** Simple, symmetric, every pair of vertices connected by two opposite edges. - **Complete asymmetric digraph (Tournament):** Asymmetric, exactly one edge between every pair of distinct vertices. - **Balanced digraph:** $d^+(v) = d^-(v)$ for all $v$. #### Digraphs and Binary Relations - A digraph represents a binary relation on its vertex set. - **Reflexive relation:** Self-loop at every vertex. - **Symmetric relation:** Symmetric digraph. - **Transitive relation:** If $(u,v)$ and $(v,w)$ are edges, then $(u,w)$ is an edge. - **Equivalence relation:** Reflexive, symmetric, transitive. Its graph is a union of complete symmetric digraphs with self-loops. - **Relation matrix:** Adjacency matrix of the corresponding digraph. #### Directed Paths and Connectedness - **Directed walk:** Edges oriented from preceding to following vertex. - **Semiwalk:** Walk in the corresponding undirected graph, but not directed. - **Strongly connected digraph:** A directed path exists from every vertex to every other vertex. - **Weakly connected digraph:** Its corresponding undirected graph is connected, but it's not strongly connected. - **Fragment:** A maximal strongly connected subgraph. - **Condensation $G_c$:** Digraph where each fragment of $G$ is a vertex, and edges represent directed connections between fragments. #### Euler Digraphs - **Directed Euler line:** A closed directed walk traversing every edge exactly once. - **Euler digraph:** Contains a directed Euler line. - **Theorem 9-1:** A digraph $G$ is an Euler digraph iff $G$ is connected and balanced. - **Teleprinter's Problem:** Construct longest circular sequence of 0s and 1s such that no r-bit subsequence appears more than once. Solved using Euler digraphs. #### Trees with Directed Edges - **Arborescence:** A digraph where: 1. No circuits (directed or semi). 2. Exactly one vertex $v$ has $d^-(v)=0$ (the root). - **Theorem 9-2:** An arborescence is a tree where every non-root vertex has $d^-(v)=1$. - **Theorem 9-3:** In an arborescence, there's a directed path from the root to every other vertex. - **Polish Notation:** Represented by arborescences for arithmetic expressions. - **Spanning arborescence:** A spanning tree that is an arborescence. - **Theorem 9-4:** An Euler line in a balanced digraph can be used to construct a spanning arborescence. - **Theorem 9-5:** Provides rules to construct an Euler line from a spanning in-tree. #### Fundamental Circuits in Digraphs - Chords still create fundamental circuits (can be directed or semi). - The ring sum of directed circuits is not necessarily a directed circuit. #### Matrices $A$, $B$, and $C$ of Digraphs - **Incidence Matrix ($A$):** $n \times e$ matrix. $a_{ij}=1$ if edge $j$ leaves $i$, $-1$ if edge $j$ enters $i$, $0$ otherwise. (Over real numbers). - **Theorem 9-6:** For connected digraph, $\text{rank}(A) = n-1$. - **Theorem 9-7:** $A$ is **unimodular** (determinant of every square submatrix is $1, -1,$ or $0$). - **Circuit Matrix ($B$):** $q \times e$ matrix. $b_{ij}=1$ if edge $j$ is in circuit $i$ and directions coincide, $-1$ if opposite, $0$ otherwise. (Over real numbers). - **Theorem 9-8:** $A \cdot B^T = 0$. - $\text{rank}(B) = e-n+1$. - **Number of Spanning Trees (Theorem 9-9):** For connected digraph, $|A_f A_f^T|$. - **Fundamental Circuit Matrix ($B_f$):** Form $[I_\mu | B_t]$. #### Adjacency Matrix ($X$) of a Digraph - **Definition:** $n \times n$ matrix. $x_{ij}=1$ if edge $(i,j)$ exists, $0$ otherwise. - **Properties:** - Symmetric iff digraph is symmetric. - Diagonal entries are $1$ for self-loops. - Cannot represent parallel edges. - Row sum is $d^+(v)$, column sum is $d^-(v)$. - **Powers of $X$ ($X^r$):** - **Theorem 9-10:** The $ij$-th entry in $X^r$ is the number of different directed edge sequences of $r$ edges from $i$ to $j$. - **Number of Arborescences (Theorem 9-12):** The $(q,q)$ cofactor of the Kirchhoff matrix $K(G)$ equals the number of arborescences rooted at $v_q$. - **Number of Euler Lines (Theorem 9-13):** For Euler digraph, $\sigma \cdot \prod_{v_i \in V} (d^+(v_i)-1)!$. #### Paired Comparisons and Tournaments - **Tournament:** Complete asymmetric digraph. - **Theorem 9-14:** Every complete tournament has a directed Hamiltonian path. - **Ranking:** By score (out-degree) or Hamiltonian path. #### Acyclic Digraphs and Decyclization - **Acyclic digraph:** No directed circuits. - **Theorem 9-15:** Every acyclic digraph has at least one vertex with zero in-degree and one with zero out-degree. - **Theorem 9-16:** A digraph is acyclic iff its adjacency matrix can be made upper triangular by vertex ordering. - **Theorem 9-17:** Digraph $G$ is acyclic iff $\det(I-X) \ne 0$. - **Decyclization:** Removing minimum edges to make a digraph acyclic (minimum-feedback arc set). ### 10. Enumeration of Graphs #### Types of Enumeration - Counting different types of graphs (e.g., connected, simple graphs). - Counting subgraphs of a particular type in a given graph. - **Labeled graphs:** Vertices are distinguishable. - Number of simple labeled graphs with $n$ vertices is $2^{n(n-1)/2}$. - **Unlabeled graphs:** Vertices are indistinguishable (non-isomorphic). #### Counting Labeled Trees - **Cayley's Theorem (3-10):** There are $n^{n-2}$ labeled trees with $n$ vertices ($n \ge 2$). - **Theorem 10-2:** The number of different rooted, labeled trees with $n$ vertices is $n^{n-1}$. #### Counting Unlabeled Trees - Requires generating functions and partitions. - **Generating function:** A power series $f(x) = \sum a_k x^k$ where $a_k$ is the desired number. - **Partitions:** Ways to express an integer as a sum of positive integers. - **Rooted unlabeled trees:** $u_n$ is the number of such trees with $n$ vertices. Recurrence relations and counting series can be derived. - **Free unlabeled trees:** Counted using centroids and bicentroids, leading to Otter's formula. #### Pólya's Counting Theorem - **Permutation:** One-to-one mapping of a set onto itself. Represented by disjoint cycles (cyclic representation). - **Cycle structure:** Describes the number of cycles of various lengths in a permutation. - **Composition of permutations:** Applying one then another. - **Permutation group:** A set of permutations forming a group under composition. - **Cycle index $Z(P)$:** Average of cycle structures of all permutations in a group $P$. - **Pair group:** Permutations induced on pairs of vertices by permutations on vertices. - **Equivalence classes of functions:** Mappings from domain $D$ to range $R$ grouped by a permutation group $P$ on $D$. - **Figure-counting series $A(x)$:** Describes the distribution of "contents" (weights) of elements in the range $R$. - **Configuration-counting series $B(x)$:** Describes the distribution of "contents" of equivalence classes of functions. - **Theorem 10-3 (Pólya's Counting Theorem):** $B(x)$ is obtained by substituting $A(x^i)$ for each $y_i$ in $Z(P; y_1, \dots, y_k)$. - This theorem is powerful for counting distinct (unlabeled) objects under group action. #### Graph Enumeration with Pólya's Theorem - **Simple graphs:** - Domain $D$: Set of all unordered pairs of vertices. - Range $R$: $\{ \text{edge present, edge absent} \}$. $A(x) = 1+x$. - Permutation group $P$: Pair group $R_n$ induced by $S_n$ on $D$. - $B(x)$ gives the number of unlabeled simple graphs. - **Multigraphs:** Range $R$ can include multiple edges (e.g., $A(x) = 1+x+x^2$ for at most two parallel edges). - **Digraphs:** - Domain $D$: Set of all ordered pairs of vertices. - Permutation group $P$: Group $M_n$ induced by $S_n$ on ordered pairs. - $B(x)$ gives the number of unlabeled simple digraphs. ### 11. Graph-Theoretic Algorithms and Computer Programs #### Algorithms - **Algorithm:** A set of instructions to solve a problem in a finite number of steps. - **Efficiency:** Measured by memory and computation time (as function of graph size $n, e$). - **Polynomial-bounded algorithm:** Computation time $\propto n^k$ or $e^q$. #### Input: Computer Representation of a Graph - **Adjacency matrix:** $n \times n$ matrix, $n^2$ bits. Good for dense graphs. (Cannot represent parallel edges). - **Incidence matrix:** $n \times e$ matrix, $n \cdot e$ bits. Good for electrical networks. - **Edge listing:** List of $(u,v)$ pairs. $2e \cdot b$ bits ($b = \lceil \log_2 n \rceil$). Good for sparse graphs. - **Two linear arrays:** F (from vertices), H (to vertices). Similar to edge listing. - **Successor listing:** For each vertex, list its successors. $n(1+d_{av})$ words. Good for path-finding. #### Output - Varies by problem: adjacency matrix, specific numbers (e.g., distance), YES/NO, list of paths/vertices. #### Basic Algorithms - **Algorithm 1: Connectedness and Components** - Method: Iterative fusion of adjacent vertices (OR-ing rows/columns in adjacency matrix). - Time: $\propto n^2$. - **Algorithm 2: A Spanning Tree/Forest** - Method: Kruskal-like, examine edges, add if connecting new components or extending existing ones. - Time: $\propto e$. - **Minimal-Spanning-Tree Algorithms:** - Kruskal's: Sort edges, use Algorithm 2. - Prim's: Grow tree from a star, always adding closest vertex. Time $\propto n^2$. - **Algorithm 3: A Set of Fundamental Circuits** - Method: Paton's algorithm. Depth-first search, maintain predecessor & level arrays. When edge $(z,p)$ connects to $p \in T$, trace path from $z$ to $p$. - Time: $\propto n^\gamma$ ($1 \le \gamma ### 12. Graphs in Switching and Coding Theory #### Contact Networks - **Contact:** A two-terminal device (switch) with open (0) or closed (1) states. - **Contact network:** A network of interconnected contacts, represented as an undirected graph where edges are contacts and vertices are terminals. - **Boolean Algebra:** Used for switching functions (binary variables, operations +, $\cdot$, complement). - **Analysis:** Given network, find conditions for electrical conduction between terminals. - **Path product:** Boolean product of variables for edges in a path. - **Transmission:** Boolean sum of all path products between two terminals. - **Primitive connection matrix $Q$:** $Q_{ii}=1$, $Q_{ij}$ is Boolean sum of variables for edges between $i,j$. - **Theorem 12-1:** Transmission matrix $T = Q^{n-1}$ (Boolean matrix power). - **Theorem 12-2:** Switching function $F_{ij}$ between $i,j$ equals $Q_{ij}$ (minor of $Q$). - **Synthesis:** Design network for given switching functions. - **Single-contact (SC) network:** Each variable associated with only one edge. - **SC function:** Realizable by an SC network. - **Realization Procedure for SC function:** 1. Get path matrix $P(a,b)$. 2. Add column of $1$s for "variable $x_0$" to $P(a,b)$ to get circuit matrix $B$. 3. Reduce $B$ to fundamental circuit matrix $B_f$. 4. Obtain fundamental cut-set matrix $C_f$ from $B_f$. 5. Obtain reduced incidence matrix $A_f$ from $C_f$ by row operations to have $\le 2$ $1$s per column. 6. Construct graph from $A_f$, then remove $x_0$. - **Realizability (Tutte's Theorem 12-3):** Conditions for a $(0,1)$-matrix to be a cut-set matrix (no $L$ or $L^T$ submatrix, no circuit matrix of $K_5$ or $K_{3,3}$ homeomorphic subgraphs). #### Sequential Switching Networks (Sequential Machines) - **Definition:** Mathematical system with states $V$, inputs $X$, outputs $Z$, transition function, and output function. Output depends on past history (memory). - **State table:** Tabular form of machine. - **State graph:** Weighted, directed graph representation. Vertices are states, edges are transitions (labeled with input/output pairs). - **Properties of State Graphs:** - $d^+(v) = |X|$ for all $v$. - Can have self-loops and parallel edges (with different labels). - Can be rooted (starting state). - **Persistent state:** Cannot be left. - **Strongly connected:** If state graph is strongly connected. - **Problems:** Analysis, synthesis, state equivalence/reduction, state assignment. #### Unit Cube and Its Graph - **$m$-cube ($Q_m$):** Graph with $2^m$ vertices, each labeled with a distinct $m$-bit binary sequence. Two vertices are adjacent iff their labels differ in exactly one bit. - Regular graph of degree $m$. - Distance between vertices is Hamming distance. - **Minterms:** Boolean products of $m$ variables. One-to-one correspondence with vertices of $Q_m$. - **Switching Functions on $Q_m$:** A function partitions $Q_m$ vertices into "true" (function=1) and "false" (function=0). #### Graphs in Coding Theory - **Gray codes (Reflected binary code, Cyclic code):** $m$-bit binary sequences where adjacent words differ in only one bit. Corresponds to a Hamiltonian circuit in $Q_m$. - **Snake-in-the-Box (SIB) codes:** A circuit in $Q_m$ where no two non-successive vertices are adjacent. (Error-checking property). - **Huffman Graph-Theoretic Codes:** Binary group codes derived from the cut-set (or circuit) subspace of a graph over GF(2). ### 13. Electrical Network Analysis by Graph Theory #### What is an Electrical Network? - A collection of interconnected electrical elements. - Represented as a connected directed graph $G$. - Each edge $e_k$ has edge voltage $v_k(t)$ (cross variable) and edge current $i_k(t)$ (through variable). - Edge orientation is arbitrary. #### Kirchhoff's Current and Voltage Laws - **Kirchhoff's Current Law (KCL):** Net sum of currents leaving any node is zero. - $A \cdot i(t) = 0$, where $A$ is the incidence matrix. - **Kirchhoff's Voltage Law (KVL):** Net sum of voltages around any loop is zero. - $B \cdot v(t) = 0$, where $B$ is the circuit matrix. #### Loop Currents and Node Voltages - **Loop currents ($i_L(t)$):** Currents in the $\mu$ independent circuits (determined by fundamental circuit matrix $B_f$). - $i(t) = B_f^T \cdot i_L(t)$. - **Node voltages ($v_N(t)$):** Voltages at $n-1$ independent nodes (determined by reduced incidence matrix $A_f$). - $v(t) = A_f^T \cdot v_N(t)$. #### RLC Networks with Independent Sources: Nodal Analysis - **Edge admittance matrix $Y(s)$:** Diagonal matrix for RLC elements (no mutual coupling). $I(s) = Y(s)V(s)$. - **Node admittance matrix $Y_N(s)$:** $(n-1) \times (n-1)$ matrix. - $Y_N(s) = A_f Y(s) A_f^T$. - $Y_N(s) V_N(s) = J(s)$ (node equations). - **Determinant of $Y_N(s)$ ($\Delta_N$):** - **Maxwell's Formula:** $\Delta_N = \sum_{\text{all spanning trees } T} \left( \prod_{e_k \in T} Y_k(s) \right)$. (Sum of tree admittance products). - **Cofactors of $Y_N(s)$ ($\Delta_{ij}$):** - $\Delta_{ii} = \sum_{\text{2-trees } (i,r) \text{ of } G} \left( \prod_{e_k \in \text{2-tree}} Y_k(s) \right)$. (Sum of 2-tree admittance products, separating $i$ from reference $r$). - $\Delta_{ij}$ is more complex, involves 2-trees separating $i,j$ from $r$. #### RLC Networks with Independent Sources: Loop Analysis - **Edge impedance matrix $Z(s)$:** Diagonal matrix for RLC elements. $V(s) = Z(s)I(s)$. - **Loop impedance matrix $Z_L(s)$:** $\mu \times \mu$ matrix. - $Z_L(s) = B_f Z(s) B_f^T$. - $Z_L(s) I_L(s) = E(s)$ (loop equations). - **Determinant of $Z_L(s)$ ($\Delta_L$):** - $\Delta_L = \sum_{\text{all chord sets } C \text{ of } G} \left( \prod_{e_k \in C} Z_k(s) \right)$. (Sum of chord impedance products). #### General Lumped, Linear, Fixed Networks - **Non-diagonal $Y(s)$ (mutual coupling):** For elements like transformers, transistors. - $\Delta_N = \sum_{\text{all pairs of spanning trees } (\alpha, \beta)} \epsilon_{\alpha \beta} \det[Y(s)]_{\alpha \beta}$. - Sum over pairs of spanning trees. $\epsilon_{\alpha \beta}$ is product of signs. - Requires selecting pairs of spanning trees for which $\det[Y(s)]_{\alpha \beta} \ne 0$. ### 14. Graph Theory in Operations Research #### Transport Networks - **Transport (Flow) network:** Weighted digraph where edge weights are capacities $c_{ij} \ge 0$. - **Flow ($f_{ij}$):** Nonnegative number assigned to each edge. - $0 \le f_{ij} \le c_{ij}$. - **Source $s$:** Net flow out is $w$. - **Sink $t$:** Net flow in is $w$. - **Intermediate vertices:** Flow is conserved. - **Maximal flow pattern:** Flow maximizing $w$. - **Cut (separating $s$ from $t$):** A cut-set that separates $s$ and $t$. - **Capacity of a cut $c(P, \bar{P})$:** Sum of capacities of edges directed from $P$ to $\bar{P}$ (where $s \in P, t \in \bar{P}$). - **Max-Flow Min-Cut Theorem (14-2):** The maximum value of a flow from $s$ to $t$ equals the minimum capacity of all cuts separating $s$ from $t$. #### Extensions of Max-Flow Min-Cut Theorem - **Multiple Sources and Sinks:** Add a supersource and supersink with infinite capacity edges. - **Vertices with Specified Capacity:** Replace vertex $v$ with $v', v''$ and edge $(v',v'')$ with capacity $c(v)$. - **Undirected Edges:** Replace each undirected edge $(p,q)$ with directed edges $(p,q)$ and $(q,p)$, each with original capacity. - **Lower Bound on Edge Flows ($b_{ij}$):** $b_{ij} \le f_{ij} \le c_{ij}$. More complex to find feasible flow. - **Lossy Networks:** Edges have efficiency $\lambda_{ij}$ ($f'_{ij} = \lambda_{ij} f_{ij}$). #### Minimal-Cost Flows - Each edge $(i,j)$ has a cost $d_{ij}$ per unit flow. - Goal: Find a flow pattern of specified value $w$ that minimizes total flow cost $\sum f_{ij} d_{ij}$. - **Theorem 14-3:** If $f$ is a minimal-cost flow of value $w$, then $f'$ (obtained by adding $\delta$ to a minimal-cost unsaturated path) is a minimal-cost flow of value $w+\delta$. #### Multicommodity Flow - Multiple distinct commodities flow simultaneously, each with its own source and sink. - All flows share edge capacities. - No general theorem like Max-Flow Min-Cut. #### Additional Applications (Flow Problems) - **Matching/Assignment Problem:** Formulate as a flow network with unit capacities on source/sink edges and infinite capacities on man-job edges. Max flow gives optimal assignment. #### Activity Networks in Project Planning (CPM/PERT) - **Activity network:** A weighted, acyclic digraph representing a project. - Edges = activities (weight = duration). - Vertices = events (milestones). - **Dummy activity:** Edge representing precedence, not a job (duration 0). - **Properties:** Connected, weighted, simple, acyclic, one start vertex ($d^-=0$), one stop vertex ($d^+=0$). - **Topological Sorting:** Relabeling vertices $1, \dots, n$ such that for any edge $(i,j)$, $i ### 15. Survey of Other Applications #### Signal-Flow Graphs - **Purpose:** Analyzing linear systems by solving simultaneous linear algebraic equations. - **Construction:** Digraph where vertices are variables, edges represent dependencies, edge weights are coefficients. - **Properties:** - $d^-(v)=0$ for independent variables. - Connected. - **Theorem 15-1:** Weight matrix $W$ of signal-flow graph for $Cx=y$ is $W = I - C^T$. - **Reduction:** Elimination of intermediate vertices. - **Mason's Gain Formula:** - **Path gain:** Product of edge weights along a directed path. - **Cycle gain:** Product of edge weights along a directed circuit. - **Theorem 15-2 (Determinant):** $\Delta = 1 - \sum t_1 + \sum t_2 - \sum t_3 + \dots$ (where $t_k$ is sum of products of cycle gains of $k$ vertex-disjoint circuits). - **Theorem 15-3 (Cofactor):** $C_{ij} = \sum_k P_k \Delta_k$ (where $P_k$ is path gain of $k$-th directed path from $i$ to $j$, $\Delta_k$ is $\Delta$ for subgraph with no vertices in common with $P_k$). - Gain $x_j/y_i = C_{ij}/\Delta$. #### Graphs in Markov Processes - **Markov process:** Random process where current state depends only on previous state. - **Transition probabilities $p_{ij}$:** Probability of moving from state $i$ to state $j$. $\sum_j p_{ij} = 1$. - **Transition matrix $P$:** $P = [p_{ij}]$. A **stochastic matrix** (nonnegative, row sums are 1). - **Stochastic graph (Transition graph):** Digraph where vertices are states, edges $(s_i, s_j)$ have weight $p_{ij}$. - **Multistep Transition Probabilities (Theorem 15-4):** $k$-step transition probability $\phi_{ij}(k)$ is the $ij$-th entry in $P^k$. - **Classification of States:** - **Closed set:** No state outside the set can be reached. - **Absorbing state:** A single state with a self-loop of weight 1. - **Ergodic (Irreducible) process:** Transition graph is strongly connected. - **Regular Markov process:** For some $k$, every entry in $P^k$ is positive. - **Theorem 15-5:** A strongly connected stochastic digraph represents a regular Markov process iff the GCD of lengths of its minimal strongly connected subdigraphs is 1. - **Periodic Markov process:** States entered at periodic intervals. - **Markov Processes with Transient States:** Transition graph is weakly connected. States can be partitioned into transient sets and irreducible sets. - **Asymptotic Behavior (Theorem 15-6):** For a regular Markov process, $P^k \to \Phi$ (a stochastic matrix with identical rows) as $k \to \infty$. Each row $w$ of $\Phi$ is the steady-state probability vector. - $w P = w$ and $\sum w_i = 1$. - **Transient Analysis:** Using z-transforms and signal-flow graphs to find $P^k$ as a function of $k$. #### Graphs in Computer Programming - **Program digraph:** Vertices = program blocks, edges = possible control transfers. - **Properties:** Connected, one start vertex ($d^-=0$), one stop vertex ($d^+=0$), start can reach all, stop reachable from all. - **Detection of Programming Errors:** Tracing paths in digraph to find unreachable code or dead ends. - **Estimation of Program Running Time:** Assign execution time to vertices. Add edge $(v_n, v_1)$ (stop to start) to make balanced. Edge weights $f_i$ (flow) represent number of traversals. - KCL holds at every vertex. $e-n+1$ independent flows. - **Theorem 15-7:** Conditions for a weighted digraph to be a program digraph (KCL obeyed, specific start/stop degrees, weights = 1). - **Program Segmentation:** Partitioning program digraph into subdigraphs for memory management. Difficult due to loops (directed circuits). Stochastic analysis helps estimate loop frequencies. #### Graphs in Chemistry - **Structural graph:** Atoms as vertices, bonds as edges. Hydrogen atoms often omitted. - **Canonical Representation:** Unique coding for molecules. - Aliphatic compounds (trees): Use centroid as root to generate unique linear code. - Cyclic compounds (graphs with circuits): More complex, use n-sided polygon and remaining edges. - **Matching of Chemical Structure:** Isomorphism problem for graphs with labeled vertices. Sussenguth's algorithm uses properties (labels, degrees) to match vertex subsets. - **Computerized Chemical Identification:** Generating all possible isomers, comparing against analytical data. (DENDRAL project). #### Miscellaneous Applications - **Information Retrieval:** Similarity graphs (vertices=index terms, edges=related terms). - **Analysis of Lumped Physical Systems:** System graphs for general physical systems. - **Matrix Inversion:** Graph-theoretic methods for sparse matrix inversion. - **Graphs of Groups (Cayley diagram):** Vertices=group elements, edges=generators. - **Linguistics:** Parsing diagrams, sentence structure. - **Sociological Structures:** Sociograms (vertices=individuals, edges=relationships). - Other fields: Economics, logistics, cybernetics, AI, pattern recognition, genetics, reliability, fault diagnosis.