Latest revision as of 11:11, 9 September 2017

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

Main article: Graphs/Traversal

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

Main article: Graphs/Definitions

Chapter 1 is a litany of definitions, concepts, and theorems important to laying the groundwork for discussing graph theory.

Chapter 2: Matching

Main article: Graphs/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

Main article: Graphs/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

@@ 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=
-==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)
-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]]
-===Chapter 2: Matching===
+Directed acyclic graphs: [[Graphs/DAGs]]
-Bipartite graph matching
+Topographical sort of directed acyclic graphs: [[Graphs/Topological Sort]]
-k-partite graph matching
+===Shortest Paths===
-===Chapter 3: Connectivity===
+Dijkstra's algorithm:
--connected graphs
+===Minimum Spanning Trees===
--connected graphs
+Minimum spanning trees:
-Menger's Theorem
+==Diestel - Graph Theory==
-Mader's Theorem
+Link to book: http://www.cs.unibo.it/babaoglu/courses/cas00-01/tutorials/GraphTheory.pdf
-Spanning trees (and edge-disjoint spanning trees)
+===Chapter 1: Basics===
-===Chapter 4: Planar Graphs===
+{{Main|Graphs/Definitions}}
-Topology
+Chapter 1 is a litany of definitions, concepts, and theorems important to laying the groundwork for discussing graph theory.
-Plane graphs
+===Chapter 2: Matching===
-Algebraic criteria
-===Chapter 5: Coloring===
-Coloring vertices
+{{Main|Graphs/Matching}}
-Coloring edges
+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 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 10: Hamilton Cycles===
-==Wallis - Beginner's Guide to Graph Theory==
-===Chapter 1: Graphs===
-===Chapter 2: Walks, Paths, Cycles===
 ===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: Difference between revisions

From charlesreid1