What a Graph Is
Chapter Eighty-Seven
Syllabus topic Module 2, "Graph: Introduction"
Pages 276 to 278 of 411
In one line
A graph is a set of things together with a set of connections between them, and it is the most general structure in this paper because it assumes nothing about the shape of those connections.
The definition
A graph G is a pair (V, E) where V is a set of vertices (also called nodes) and E is a set of edges, each edge joining two vertices.
That is all. No root, no parent, no order, no limit on how many edges a vertex may have, and no requirement that everything be connected.
How it generalises everything before it
Every structure in this paper is a graph with a restriction added.
| Structure | The restriction |
|---|---|
| Linked list | each vertex has at most one edge out, and no cycles |
| Tree | connected, no cycles, one distinguished root |
| Binary tree | a tree where each vertex has at most two edges out |
| Graph | no restriction at all |
So a graph can express anything the earlier structures can, and more besides: cycles, several routes between two points, and vertices connected to nothing.
That generality is why graph problems are harder. A tree traversal cannot revisit a node, because there is no way back; a graph traversal can, and chapters 94 and 95 must therefore remember where they have been, which no tree algorithm in this book needed to do.
Things that are already graphs
A road map. Vertices are junctions, edges are roads. The question "what is the shortest route" is chapter 98.
A social network. Vertices are people, edges are friendships. "Are these two connected" is chapter 96.
The web. Vertices are pages, edges are links. These edges go one way, which is the directed case.
A railway network, an electrical circuit, a project's task dependencies, the call graph of a program, the states of a game. All graphs.
And the structures in this book. A tree is a graph. A linked list is a graph. Drawing them as graphs is what makes the common vocabulary of the next chapter useful.
Directed and undirected
The one distinction to fix immediately, because everything else depends on it.
Undirected. An edge joins two vertices symmetrically. If A is joined to B then B is joined to A. Friendship, a road with two-way traffic, a wire.
Directed (a digraph). An edge goes from one vertex to another. A to B does not imply B to A. A web link, a one-way street, "A must finish before B".
undirected = {
"Mumbai": {"Pune", "Nashik"},
"Pune": {"Mumbai", "Nashik"},
"Nashik": {"Mumbai", "Pune"},
"Goa": set(),
}
directed = {
"home": {"notes", "papers"},
"notes": {"chapter"},
"papers": {"chapter"},
"chapter": set(),
}
print("an UNDIRECTED graph: cities joined by roads")
for city, neighbours in sorted(undirected.items()):
print(" %-8s joined to %s" % (city, sorted(neighbours) or "nothing"))
print(" symmetric:", all(a in undirected[b]
for a, ns in undirected.items() for b in ns))
print(" Goa is in the graph with no edges at all:", undirected["Goa"] == set())
print()
print("a DIRECTED graph: pages linking to pages")
for page, links in sorted(directed.items()):
print(" %-8s links to %s" % (page, sorted(links) or "nothing"))
print(" symmetric:", all(a in directed[b]
for a, ls in directed.items() for b in ls))
print(" home links to notes, but notes does NOT link back to home:",
"notes" in directed["home"] and "home" not in directed["notes"])What a Graph Is
an UNDIRECTED graph: cities joined by roads
Goa joined to nothing
Mumbai joined to ['Nashik', 'Pune']
Nashik joined to ['Mumbai', 'Pune']
Pune joined to ['Mumbai', 'Nashik']
symmetric: True
Goa is in the graph with no edges at all: True
a DIRECTED graph: pages linking to pages
chapter links to nothing
home links to ['notes', 'papers']
notes links to ['chapter']
papers links to ['chapter']
symmetric: False
home links to notes, but notes does NOT link back to home: TrueTwo things in that run are worth noticing.
Goa is a vertex with no edges, and that is perfectly legal. A graph need not be connected, which no tree in this book was allowed to be.
The directed graph has two routes from home to chapter, through notes and through papers. A tree would have exactly one path between any two nodes (chapter 51); a graph may have none, one, or many.
Weighted graphs
An edge may carry a weight: a distance, a cost, a time, a capacity.
An unweighted graph answers "can I get there" and "how few steps". A weighted graph answers "how far" and "how cheaply", and those are different questions with different algorithms, which is exactly the difference between chapters 97 and 98.
The four kinds
| Unweighted | Weighted | |
|---|---|---|
| Undirected | friendships, two-way roads | road distances |
| Directed | web links, prerequisites | one-way roads with distances, network costs |
An examination question will say which it means, or the wording will imply it. "Roads between cities with distances" is undirected and weighted. "Which tasks must finish first" is directed and unweighted.
Quick revision
- A graph is a set of vertices and a set of edges joining them. Nothing else is assumed.
- Every structure in this paper is a graph with a restriction: a tree is a connected graph with no cycles
and a root; a list is a tree where each node has one child.
- A graph may have cycles, several paths between two vertices, or vertices with no edges at all.
- A graph traversal must remember where it has been; a tree traversal never had to.
- Undirected: edges are symmetric. Directed (a digraph): an edge goes one way.
- An edge may carry a weight, which turns "how few steps" into "how far".
- The four kinds are directed or undirected, crossed with weighted or unweighted.
What a Graph Is
Test yourself
1. Define a graph. A pair (V, E) where V is a set of vertices and E is a set of edges, each joining two vertices. Nothing else is assumed.
2. How is a tree a special case of a graph? A tree is a connected graph with no cycles and one distinguished root. A graph need be none of those things.
3. Why must a graph traversal remember where it has been, when a tree traversal need not? Because a graph may contain cycles and several paths to the same vertex, so a traversal can return to a vertex it has already visited and loop for ever. A tree has exactly one path to each node.
4. State the difference between a directed and an undirected graph, with an example of each. In an undirected graph an edge joins two vertices symmetrically, as a two-way road does. In a directed graph an edge goes from one vertex to another, as a web link does, and the reverse need not exist.
5. What does a weight on an edge represent, and what question does it change? A distance, cost, time or capacity. It changes the question from "how few steps" to "how far" or "how cheaply", which needs a different algorithm.
6. Is a vertex with no edges allowed? Is more than one path between two vertices allowed? Both are allowed. A graph need not be connected, and it may have many paths between two vertices, unlike a tree which has exactly one.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.