|
|
| (23 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
| | The Goodrich book is less extensive, less mathematical, and more practical. The focus is on graph implementations, not on graph theory. |
|
| |
|
| ===Chapter 1: Basics=== | | ===Data Structures=== |
|
| |
|
| Outline:
| | Goodrich begins Chapter 12 by covering data structures common in storing graphs: [[Graphs/Data Structures]] |
| * Definitions (graph, degree, path, cycle, connectivity, tree, forest, k-partite, contraction, Euler tours) | | * 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) |
|
| |
|
| ====Graph definitions====
| | ===Graph Traversals=== |
|
| |
|
| A '''graph''' G consist of a set of nodes (vertices) V and edges E, denoted <math>G(V,E)</math>
| | {{Main|Graphs/Traversal}} |
|
| |
|
| '''Vertex set''' on graph G is denoted <math>V(G)</math>
| | This is arguably the most important graph algorithm, as many, many graph algorithms are based on the traversal procedure. |
|
| |
|
| '''Edge set''' on graph G is denoted <math>E(G)</math>
| | Depth first search and traversals on graphs: [[Graphs/Depth First Traversal]] |
|
| |
|
| Number of vertices in a graph is called the '''order''' and is denoted <math>|G|</math>
| | Breadth first search and traversals on graphs: [[Graphs/Breadth First Traversal]] |
|
| |
|
| Number of edges in a graph is denoted <math>||G||</math>
| | Euler tours on graphs: [[Graphs/Euler Tour]] |
|
| |
|
| Vertex <math>v \in V</math> and edge <math>e \in E</math> are '''incident''' if the edge connects to the vertex.
| | ===Transitive Closure=== |
|
| |
|
| Set of all edges at a particular vertex v is denoted <math>E(v)</math>
| | Transitive closure graphs: [[Graphs/Transitive Closure]] |
|
| |
|
| Two vertices x, y are '''adjacent''' on a graph if there is an edge with endpoints x and y
| | Floyd Warshall algorithm: [[Graphs/Floyd Warshall]] |
|
| |
|
| If all vertices are pairwise adjacent, the graph is '''complete'''
| | ===Directed Acyclic Graphs=== |
|
| |
|
| 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 are graphs that are both directed and that do not contain cycle. |
|
| |
|
| 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
| | Detecting cycles: [[Graphs/Cycles]] |
|
| |
|
| A subgraph G' is a '''spanning subgraph''' of G if all V' span all of G (if V' = V)
| | Directed acyclic graphs: [[Graphs/DAGs]] |
|
| |
|
| ====Degree definitions====
| | Topographical sort of directed acyclic graphs: [[Graphs/Topological Sort]] |
|
| |
|
| Set of neighbors of a vertex v is denoted <math>N(v)</math>
| | ===Shortest Paths=== |
|
| |
|
| 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
| | Dijkstra's algorithm: |
|
| |
|
| Vertex of degree 0 is '''isolated'''
| | ===Minimum Spanning Trees=== |
|
| |
|
| 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'''
| | ==Diestel - Graph Theory== |
|
| |
|
| The average degree of G is given by the expression <math>d(G) = \dfrac{1}{|V|} \sum_{v \in V} d(v)</math>
| | Link to book: http://www.cs.unibo.it/babaoglu/courses/cas00-01/tutorials/GraphTheory.pdf |
|
| |
|
| Ratio of edges to vertices on a graph is <math>\epsilon(G) = \dfrac{|E|}{|V|}</math>
| | ===Chapter 1: Basics=== |
| | |
| 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>
| |
| | |
| 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.
| | {{Main|Graphs/Definitions}} |
|
| |
|
| ====Edge Contraction====
| | 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===
| |
| | |
| Subgraphs
| |
| | |
| Regularity lemma
| |
| | |
| Hadwigen's theorem
| |
|
| |
|
| ===Chapter 9: Ramsey Theory===
| | 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. |
| | |
| ===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]]
| |
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
Goodrich - Data Structures - Chapter 12
The Goodrich book is less extensive, less mathematical, and more practical. The focus is on graph implementations, not on graph theory.
Data Structures
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)
Graph Traversals
This is arguably the most important graph algorithm, as many, many graph algorithms are based on the traversal procedure.
Depth first search and traversals on graphs: Graphs/Depth First Traversal
Breadth first search and traversals on graphs: Graphs/Breadth First Traversal
Euler tours on graphs: Graphs/Euler Tour
Transitive Closure
Transitive closure graphs: Graphs/Transitive Closure
Floyd Warshall algorithm: Graphs/Floyd Warshall
Directed Acyclic Graphs
Directed acyclic graphs are graphs that are both directed and that do not contain cycle.
Detecting cycles: Graphs/Cycles
Directed acyclic graphs: Graphs/DAGs
Topographical sort of directed acyclic graphs: Graphs/Topological Sort
Shortest Paths
Dijkstra's algorithm:
Minimum Spanning Trees
Minimum spanning trees:
Diestel - Graph Theory
Link to book: http://www.cs.unibo.it/babaoglu/courses/cas00-01/tutorials/GraphTheory.pdf
Chapter 1: Basics
Chapter 1 is a litany of definitions, concepts, and theorems important to laying the groundwork for discussing graph theory.
Chapter 2: Matching
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.
Chapter 3: Connectivity
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
