Midterm #2 Cheat Sheet - Nathan McNew PDF

Preview

Summary

Nathan McNew...

Description

If G is a connected graph and T is a connected subgraph of G with no cycles and the same vertices as G, then T is a spanning tree of G | Spanning Tree Theorem: If G is a connected graph, then it has a spanning tree | Kruskal’s Algorithm: Suppose we have a graph G with weighted edges. Construct T by including edges. Start by including the edge with smallest weight in T (pick one if there is a tie). Now repeatedly include the smallest edge in G that hasn’t already been included, so long as including that edge doesn’t create a cycle with already included edges | Prim’s Algorithm: Pick any vertex v. Now pick the edge with lowest weight connected to v. Repeatedly take the edge with lowest weight that connects the existing tree to a vertex not already connected to it. | Number of Spanning Trees Theorem: There are nn-2 spanning trees of Kn | Matrix Tree Theorem: Given a connected graph G, for the matrix A where a ii = deg(vi), aij = { -1 if vivj ϵ E(G), 0 otherwise }, the number of spanning trees of G is equal to the determinant of the matrix [Aij] where this is any cofactor of the matrix obtained by removing row i and column j | Determinant: For a 3 × 3 matrix A = [a1 a2 a3; b1 b2 b3; c1 c2 c3], det(A) = a1b2c3 - a1b3c2 - a2b1c3 + a2b1c2 - a3b2c1 | A vertex v in a connected graph G is a cut-vertex id G-v is no longer connected | Bridge Cut-Vertex Theorem 1: If a graph G has a bridge e, then one of its ends is a cut-vertex v if and only if its degree is at least 2 | Bridge Cut-Vertex Theorem 2: If a connected graph G has order at least 3 and contains a bridge, it contains a cut-vertex | Cut-Vertex Components Theorem: Suppose v is a cut-vertex in G and U & W are different components of G-v. Then v must lie on every U→W path in G | Cut-Vertex Path Theorem: v in G is a cut-vertex if and only if there exist vertices u & w distinct from v such that v lies on every u→w path | Furthest Vertex CutVertex Theorem: Let G be a connected graph and let u be any vertex in G. Let v be the furthest vertex from u in G. Then v is not a cut-vertex. | Furthest Vertex Cut-Vertex Corollary: Every nontrivial connected graph has at least 2 vertices that are not cut-vertices | A graph is non-separable if it contains no cut-vertices | Common Cycle Non-Separability Theorem: A graph of order at least 3 is non-separable if and only if every 2 vertices in G lie on a common cycle | A block in a graph is a maximal non-separable subgraph, or a non-separable subgraph that is not contained in any other non-separable subgraph | Edge Equivalence Relation Theorem: Let ~ be a relation on the edges of a connected graph G where for e, f ϵ E(G), we say e ~ f if: 1. e = f, 2. e and f lie on a common cycle of G. Then ~ is an equivalence relation | Block Corollary: If B1 and B2 are distinct blocks of G, then: 1. B1 and B2 have no edges in common, 2. They have at most one vertex in common, 3. If v ϵ B1 and v ϵ B2, then v is a cut-vertex | U ⊂ V(G) is a vertex cut if G-U is disconnected | A vertex cut is a minimum vertex cut if no smaller set of vertices is a vertex cut | The connectivity of a graph G is the size of a minimum vertex cut or the number of vertices that can be removed before the graph is trivial, denoted by К(G) | F ⊂ E(G) is an edge cut of G if G-F is disconnected | A minimum edge cut is an edge cut such that no edge cut of G has a smaller size | The edge connectivity of a graph G is the size of a minimum edge cut, denoted by λ(G) | Connectivity Inequality Theorem: К(G) ≤ λ(G) ≤ δ(G) | Cubic Connectivity Theorem: If G is a cubic graph (every vertex has degree 3), then К(G) = λ(G) | Given two points u and v in a graph, a uv-separating set S is a collection of vertices such that there is no path from u to v in G-S | A minimum uv-separating set is a uv-separating set of smallest possible size | A collection of paths from u to v is internally vertex disjoint if no two of them have a vertex in common besides u and v | Menger’s Theorem: For any graph G and any two vertices u and v, the maximum number of internally vertex disjoint uv paths is equal to the size of a minimum uvseparating set | A multigraph is a collection of vertices and edges between vertices where multiple edges are allowed between two vertices | An euler/eulerian trail in a graph is a trail where every edge in the graph is used once | An eulerian circuit is a circuit in a graph that uses every edge once | A graph G is eulerian if it has an eulerian circuit | Eulerian Theorem: A graph G is eulerian if and only if it is connected and every vertex has even degree | Eulerian Trail Theorem: A graph G has an eulerian trail that is not a circuit if and only if the graph is connected and has exactly two vertices with odd degree | A path in a graph G that visits every vertex exactly once is a Hamiltonian path | A Hamiltonian cycle is a cycle that uses every vertex exactly once | A graph is Hamiltonian is it contains a Hamiltonian cycle | Hamiltonian Theorem: If G is Hamiltonian and S is a subset of the vertices of G, then K(G-S) (number of connected components) ≤ |S| (size of S) | Ore’s Criterion: If G is a graph such that any two nonadjacent vertices u and v satisfy deg(u) + deg(v) ≥ n, then G is Hamiltonian | A directed graph is a set of vertices along with directed edges from one vertex to another in which each possible directed edge occurs at most once | A directed walk in a digraph is a walk in which each edge used goes in the direction of the edge | The in-degree of a vertex v is the number of directed edges that end at v, denoted by id(v) | The out-degree of a vertex v is the number of directed edges that start at v, denoted by od(v) | Directed distance is the length of the shortest directed walk between two vertices, denoted by

´d

(u,v) | First Theorem of Digraphs: The sum of the in-degrees of the vertices of G equals the sum of the out-

degrees of the vertices of G equals the number of edges in G | The underlying graph of a digraph is the graph obtained by connecting u and v if either the directed edge vu, uv, or both show up in the digraph | A digraph is strong if there exists a directed walk from ant vertex v to any other vertex w | Strong Theorem: A digraph is strong if and only if we can pick a vertex v and it is possible both to get to any vertex from v and to get from any vertex to v | Spanning Walk Strong Theorem: A digraph G is strong if and only if there exists a spanning walk in G (a directed walk that passes through all the vertices of G and returns to where it started) | A digraph is eulerian if there exists a directed circuit that passes through each directed edge exactly once | Eulerian Digraph Theorem: A digraph is eulerian if and only if it is strong and for every vertex v ϵ G, id(v) = od(v) | Orientation Theorem: A non-directed graph can be given a strong orientation if and only if it has no bridges | A tournament is an orientation of the complete graph Kn in which each edge is directed from the winning vertex to the losing vertex | Two tournaments S and T are isomorphic if they have the same order and there exists a function φ: T→S such that if v → w in T then φ(v) → φ(w) in S | A tournament is transitive if whenever u → v and v → w, then u → w | Directed Distance Theorem: If v is a vertex in any tournament with maximal out-degree, then

´d

(v,u) ≤ 2 | Hamiltonian Tournament Theorem 1: Every tournament contains a Hamiltonian path | Triangle Theorem: If T is a strong nontrivial tournament, then every vertex v ϵ T is part of a triangle | Hamiltonian Tournament Theorem 2: A tournament is Hamiltonian if and only if it is strong | Strong Tournament Theorem: If T is a strong tournament and has order n ≥ 4, then there exists a vertex v in T such that T-v is also strong | A random walk on a digraph is a walk obtained by starting at some vertex (predefined or randomly chosen) and every step after that is chosen by choosing one of the out-edges from the current position randomly | The transition matrix of a digraph is the matrix formed by creating an n × m matrix in which position ij contains the entry 1/od(i) if there is an edge from i to j and 0 otherwise | A digraph is ergodic if there exists an integer N such that for every n > N, there is a walk of length n between any two vertices of the digraph | Ergodic Theorem: If G is an ergodic digraph and T is the transition matrix for G, then as k goes to infinity, the entries in each column of Tk converge to the same number (the probability of being at that vertex)...