Skip to Main Content
Think Complexity
book

Think Complexity

by Allen B. Downey
March 2012
Beginner content levelBeginner
160 pages
4h 6m
English
O'Reilly Media, Inc.
Content preview from Think Complexity

Chapter 2. Graphs

What’s a Graph?

To most people, a graph is a visual representation of a data set, like a bar chart or an EKG. That’s not what this chapter is about.

In this chapter, a graph is an abstraction used to model a system that contains discrete, interconnected elements. The elements are represented by nodes (also called vertices), and the interconnections are represented by edges.

For example, you could represent a road map with one node for each city and one edge for each road between cities; or you could represent a social network using one node for each person, with an edge between two people if they are “friends” and no edge otherwise.

In some graphs, edges have different lengths (sometimes called “weights” or “costs”). For example, in a road map, the length of an edge might represent the distance between two cities, the travel time, or the bus fare. In a social network, there might be different kinds of edges to represent different kinds of relationships: friends, business associates, and so on.

Edges may be undirected, if they represent a relationship that is symmetric, or directed. In a social network, friendship is usually symmetric: if A is friends with B, then B is friends with A. So you would probably represent friendship with an undirected edge. In a road map, you would probably represent a one-way street with a directed edge.

Graphs have interesting mathematical properties, and there is a branch of mathematics called graph theory that studies them.

Graphs are also ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Unikernels

Unikernels

Russell Pavlicek
Elemental Design Patterns

Elemental Design Patterns

Jason McColm Smith
LEGO® with Dad

LEGO® with Dad

Warren Nash

Publisher Resources

ISBN: 9781449331672Errata