|
|
| (22 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| Graphs are mathematical objects consisting of nodes and edges. The original inventor of graph theory was Leonhard Euler, who used it to solve the Seven Bridges of Königsberg problem. | | Graphs are mathematical objects consisting of vertices and edges. |
| | |
| | The original inventor of graph theory was (arguably) Leonhard Euler, who used it to solve the Seven Bridges of Königsberg problem. |
|
| |
|
| =Notes= | | =Notes= |
|
| |
|
| ==Diestel - Graph Theory== | | ==Goodrich - Data Structures - Chapter 12== |
| | |
| Link: http://www.cs.unibo.it/babaoglu/courses/cas00-01/tutorials/GraphTheory.pdf
| |
|
| |
|
| ===Chapter 1: Basics===
| | The Goodrich book is less extensive, less mathematical, and more practical. The focus is on graph implementations, not on graph theory. |
|
| |
|
| Outline:
| | ===Data Structures=== |
| * Definitions (graph, degree, path, cycle, connectivity, tree, forest, k-partite, contraction, Euler tours)
| |
|
| |
|
| ====Graph definitions====
| | Goodrich begins Chapter 12 by covering data structures common in storing graphs: [[Graphs/Data Structures]] |
| | * Edge list (two linked lists, one for vertices, one for edges) |
| | * Adjacency list (one linked list for vertices, storing references to edges) |
| | * Adjacency map (map that stores vertices as keys, other vertices and the edge that links them to the key vertex as values) |
| | * Adjacency matrix (N x N matrix, where N is number of vertices, with entry (i,j) indicating an edge connecting vertex i to vertex j) |
|
| |
|
| A '''graph''' G consist of a set of nodes (vertices) V and edges E, denoted <math>G(V,E)</math>
| | ===Graph Traversals=== |
|
| |
|
| '''Vertex set''' on graph G is denoted <math>V(G)</math>
| | {{Main|Graphs/Traversal}} |
|
| |
|
| '''Edge set''' on graph G is denoted <math>E(G)</math>
| | This is arguably the most important graph algorithm, as many, many graph algorithms are based on the traversal procedure. |
|
| |
|
| Number of vertices in a graph is called the '''order''' and is denoted <math>|G|</math>
| | Depth first search and traversals on graphs: [[Graphs/Depth First Traversal]] |
|
| |
|
| Number of edges in a graph is denoted <math>||G||</math>
| | Breadth first search and traversals on graphs: [[Graphs/Breadth First Traversal]] |
|
| |
|
| Vertex <math>v \in V</math> and edge <math>e \in E</math> are '''incident''' if the edge connects to the vertex.
| | Euler tours on graphs: [[Graphs/Euler Tour]] |
|
| |
|
| Set of all edges at a particular vertex v is denoted <math>E(v)</math>
| | ===Transitive Closure=== |
|
| |
|
| Two vertices x, y are '''adjacent''' on a graph if there is an edge with endpoints x and y
| | Transitive closure graphs: [[Graphs/Transitive Closure]] |
|
| |
|
| If all vertices are pairwise adjacent, the graph is '''complete'''
| | Floyd Warshall algorithm: [[Graphs/Floyd Warshall]] |
|
| |
|
| For two graphs <math>G = (V,E)</math> and <math>G' = (V',E')</math>, the graphs are isomorphic if there exists a biijection from G to G'.
| | ===Directed Acyclic Graphs=== |
|
| |
|
| If we have two graphs G and G', we say that G' is a subgraph of G if all V' subset of V and all E' subset of E
| | Directed acyclic graphs are graphs that are both directed and that do not contain cycle. |
|
| |
|
| A subgraph G' is a '''spanning subgraph''' of G if all V' span all of G (if V' = V)
| | Detecting cycles: [[Graphs/Cycles]] |
|
| |
|
| ====Degree definitions====
| | Directed acyclic graphs: [[Graphs/DAGs]] |
|
| |
|
| Set of neighbors of a vertex v is denoted <math>N(v)</math>
| | Topographical sort of directed acyclic graphs: [[Graphs/Topological Sort]] |
|
| |
|
| Degree of a vertex v is denoted <math>d(v)</math> and is equal to the number of edges <math>|E(v)|</math> at v
| | ===Shortest Paths=== |
|
| |
|
| Vertex of degree 0 is '''isolated'''
| | Dijkstra's algorithm: |
|
| |
|
| The vertex on the graph with the smallest degree <math>\delta(G) = \min \left( d(v) | v \in V \right)</math> is the '''minimum degree of G'''
| | ===Minimum Spanning Trees=== |
|
| |
|
| The vertex on the graph with the largest degree <math>\Delta(G) = \max \left( d(v) | v \in V \right)</math> is the '''maximum degree of G'''
| | Minimum spanning trees: |
|
| |
|
| The average degree of G is given by the expression <math>d(G) = \dfrac{1}{|V|} \sum_{v \in V} d(v)</math>
| | ==Diestel - Graph Theory== |
|
| |
|
| Ratio of edges to vertices on a graph is <math>\epsilon(G) = \dfrac{|E|}{|V|}</math>
| | Link to book: http://www.cs.unibo.it/babaoglu/courses/cas00-01/tutorials/GraphTheory.pdf |
|
| |
|
| If we define edges as having two endpoints, then adding up the degrees of all vertices will lead to twice the number of edges. Mathematically: <math>|E| = \dfrac{1}{2} \sum_{v \in V} d(v) = \dfrac{1}{2} d(G) |V|</math>
| | ===Chapter 1: Basics=== |
| | |
| This leads to the identity <math> \epsilon(G) = \dfrac{1}{2} d(G)</math> and the theorem that the number of vertices of odd degree in a graph must always be even. Contrawise proof: if the number of vertices of odd degree is odd, the number of edges is not be an integer.
| |
| | |
| ====Path and Cycle Definitions====
| |
| | |
| A path P on a graph G is a non-empty graph that contains vertices and edges that are in G: <math>V = \{ x_1, x_2, \dots, x_k\}</math> and <math>E = \{ x_0 x_1, x_1 x_2, \dots, x_{k-1} x_k \}</math>
| |
| | |
| A path is usually referred to by the sequence of vertices it visits, or as a path "from/between x1 to xk"
| |
| | |
| '''Independent paths''' are paths containing no common (internal) vertices. Independent paths may share endpoints though.
| |
| | |
| We can denote parts of a path using special notation: if a path <math>P = x_0 \dots x_{k}</math>, then the following notation is used to denote only a part of that path:
| |
| | |
| <math>
| |
| \begin{align}
| |
| P x_i = x_0 \dots x_i \qquad 0 \leq i \leq k \\
| |
| x_i P = x_i \dots x_k \\
| |
| x_i P x_j = x_i \dots x_j
| |
| \end{align}
| |
| </math>
| |
| | |
| We can also connect paths using unions, or by using more shorthand:
| |
| | |
| <math>
| |
| P x \bigcup x Q y \bigcup y R = P x Q y R
| |
| </math>
| |
| | |
| A '''cycle C''' consists of a path whose final edge connects the last node to the first node. Given a path <math>P = x_0 \dots x_{k-1}</math> the cycle is then <math>C = P + x_{k-1} x_0</math>
| |
| | |
| A k-cycle is denoted <math>C^k</math> and is a cycle of length k.
| |
| | |
| The girth of a cycle is the number of edges or vertices in a cycle in a graph G. The circumference of a graph is the maximum length of a cycle in a graph G.
| |
| | |
| The distance of two vertices x and y is the length of the shortest path from x to y <math>d_G(x,y)</math>.
| |
| | |
| A vertex is '''central''' if greatest distance from any other vertex is as small as possible. This minimum distance is the radius of the graph G. Formally:
| |
| | |
| <math>
| |
| rad(G) = \min_{x \in V(G)} \max_{y \in V(G)} d_G(x,y)
| |
| </math>
| |
| | |
| Note that the radius of a graph is different from the minimum/average degree.
| |
| | |
| ====Connectivity====
| |
| | |
| A graph is '''connected''' if any two arbitrary vertices are connected.
| |
| | |
| If the graph is directed, a connected graph means that for any two arbitrary vertices u and v, there is an edge connecting u to v or v to u. A '''strongly connected''' graph means that for any two arbitrary nodes u and v, there is an edge connecting u to v and another edge connecting v to u.
| |
| | |
| Suppose we have two sets of vertices A and B, and a third set of vertices X. Further suppose that any path that connects a vertex from A to a vertex from B contains a vertex from X. Then we say that X '''separates''' the vertex sets A and B.
| |
| | |
| A subgraph of G that is maximally connected (contains every vertex in G) is a '''component''' of G. If a component is connected, it is always non empty.
| |
| | |
| Vertex connectivity: A graph G is '''k-connected''' if it has more than k vertices and if no two vertices of G are separated by fewer than k vertices. The maximum value of k such that G is k-connected is the '''connectivity''' of G and is denoted <math>\kappa(G)</math>.
| |
| | |
| Edge connectivity: A graph G is '''l-edge-connected''' if every vertex is connected with fewer than l edges (this is a bit unclear). The edge connectivity is denoted <math>\lambda(G)</math>.
| |
| | |
| Theorem due to Mader 1972: Every graph of average degree at least 4k has a k-connected subgraph. (Can prove inductively.)
| |
| | |
| ====Trees and Forests====
| |
| | |
| Acyclic graphs are called forests. Connected forests are called trees.
| |
| | |
| A connected graph with n vertices is a tree if and only if it has n-1 edges.
| |
| | |
| We can (but don't have to) pick a particular node to be special - the root of the tree. In that case it is a rooted tree. When we pick a root, this imposes an ordering (assuming vertices can be compared). Given two nodes x and y, we say that <Math>x \leq y \mbox{ if } x \in rTy</math>.
| |
| | |
| A rooted tree T is called normal if any two vertices that are adjacent in the graph are comparable. Every graph has a normal spanning tree.
| |
| | |
| ====Bipartite Graphs====
| |
| | |
| A '''k-partite''' graph is a graph where the set of vertices V can be partitioned into k classes, such that every edge that starts in one partition will end in a different partition.
| |
| | |
| If we can select any two vertices from two different classes and they are connected, the k-partite graph is '''complete'''.
| |
| | |
| Bipartite graphs cannot contain cycles of odd lengths. This is always true, so that we can identify bipartite graphs using this property: a graph is bipartite iff it contains no odd cycle.
| |
| | |
| ====Edge Contraction====
| |
| | |
| Given a graph G with vertex set V and edge set E. Let e be an edge connecting vertex x to vertex y. Then <math>G/e</math> denotes the graph obtained by contracting the edge into a new vertex, which is now adjacent to all former neighbors of x and y.
| |
| | |
| ====Euler Tours====
| |
| | |
| An Euler tour is a closed walk on a graph that traverses each edge of the graph exactly once. Some graphs have an Euler tour (and are called Eulerian), other graphs are not.
| |
| | |
| A connected graph is Eulerian if and only if every vertex has even degree. This is because any vertex appearing k times in an Euler tour must have degree 2k.
| |
| | |
| ====Other Definitions====
| |
| | |
| A hypergraph is a pair of disjoint sets (V,E) where the elements of the edge sets are non-empty subsets of V. (That is, a given edge e in the set E can connect multiple vertices.)
| |
|
| |
|
| A directed graph is a pair of disjoint sets (V,E) along with two maps: the init map from V to E (denoting the initialization or origin of the directed edge) and the term map from V to E (denoting the termination of the directed edge).
| | {{Main|Graphs/Definitions}} |
|
| |
|
| A multigraph is a pair of disjoint sets (V,E) together with a map from E to V or to V^2. In other words, it is a graph in which we can have edges that begin and end at the same vertex.
| | Chapter 1 is a litany of definitions, concepts, and theorems important to laying the groundwork for discussing graph theory. |
|
| |
|
| ===Chapter 2: Matching=== | | ===Chapter 2: Matching=== |
|
| |
|
| Bipartite graph matching
| | {{Main|Graphs/Matching}} |
| | |
| k-partite graph matching
| |
| | |
| ===Chapter 3: Connectivity===
| |
| | |
| 2-connected graphs
| |
| | |
| 3-connected graphs
| |
| | |
| Menger's Theorem
| |
| | |
| Mader's Theorem
| |
| | |
| Spanning trees (and edge-disjoint spanning trees)
| |
| | |
| ===Chapter 4: Planar Graphs===
| |
| | |
| Topology
| |
| | |
| Plane graphs
| |
| | |
| Algebraic criteria
| |
| | |
| ===Chapter 5: Coloring===
| |
| | |
| Coloring vertices
| |
| | |
| Coloring edges
| |
| | |
| ===Chapter 6: Flows===
| |
| | |
| Circulations
| |
| | |
| Flows in networks
| |
| | |
| k-flows
| |
| | |
| Flow coloring
| |
| | |
| Tutte's flow conjectures
| |
|
| |
|
| ===Chapter 7 and 8: Substructures===
| | Chapter 2 introduces wave after wave of new terms and notation, and is a bit hard to follow. It covers the concept of finding a set of edges that can connect all vertices between two subsets of vertices on a graph. |
| | |
| Subgraphs
| |
| | |
| Regularity lemma
| |
| | |
| Hadwigen's theorem
| |
| | |
| ===Chapter 9: Ramsey Theory===
| |
| | |
| ===Chapter 10: Hamilton Cycles===
| |
| | |
| | |
| | |
| <!--
| |
| ==Wallis - Beginner's Guide to Graph Theory==
| |
| | |
| ===Chapter 1: Graphs===
| |
| | |
| ===Chapter 2: Walks, Paths, Cycles===
| |
|
| |
|
| ===Chapter 3: Connectivity=== | | ===Chapter 3: Connectivity=== |
|
| |
|
| ===Chapter 4: Trees===
| | {{Main|Graphs/Connectivity}} |
| | |
| ===Chapter 5: Linear Spaces===
| |
| | |
| ===Chapter 6: Factorizations===
| |
| | |
| ===Chapter 7: Coloring===
| |
| | |
| ===Chapter 8: Planarity===
| |
| | |
| ===Chapter 10: Ramsey Theory===
| |
| | |
| ===Chapter 13: Network flows===
| |
| -->
| |
| | |
|
| |
|
| | Chapter 3 covers k-connectedness on graphs. Being k-connected means any two of its vertices can be joined by k independent paths. |
|
| |
|
| | ===Remaining Chapters=== |
|
| |
|
| | Reading this book is like trying to eat cardboard. No real insight or learning here. |
|
| |
|
| | =Flags= |
|
| |
|
| [[Category:CS]]
| | {{GraphsFlag}} |
| [[Category:Math]]
| |
| [[Category:Graphs]]
| |
