Graphs: Difference between revisions
From charlesreid1
| Line 37: | Line 37: | ||
Chapter 3 covers k-connectedness on graphs. Being k-connected means any two of its vertices can be joined by k independent paths. | 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= | =Flags= | ||
{{GraphsFlag}} | {{GraphsFlag}} | ||
Revision as of 01:05, 28 August 2017
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.
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.
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, so it's hard to follow. It essentially covers the concept of finding a set of edges that can connect all vertices between two subsets of vertices on a graph.
It starts with the (easier) bipartite graph case, where we wish to find the minimum or maximum set of edges that connect every vertex in vertex set A with every vertex in vertex set B.
Then it moves on to the k-partite graph case, covering several "useful" theorems. I've no idea how any of this is actually useful, since there's no discussion of practical consequences.
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
