Introduction to graph theory

Basically, a graph is a data structure that's able to represent relations in a collection of objects. Under this paradigm, the objects are the graph's nodes and the relations are the graph's links (or edges). The graph is directed if the links have an orientation (conceptually, they're like the one-way streets of a city); otherwise, the graph is undirected. In the following table, examples of well-known graphs are provided:

Graph example	Type	Nodes	Edges
Internet network	Directed	Web pages	Links
Facebook	Undirected	People	Friendship
Twitter	Directed	People	Follower
IP network	Undirected	Hosts	Wires/connections
Navigation systems	Directed	Places/addresses	Streets
Wikipedia	Directed	Pages	Anchor links
Scientific literature	Directed	Papers	Citations
Markov chains	Directed	Status	Emission probability

All the preceding examples can be expressed as relations between nodes like in a traditional RDBMS, such as MySQL or Postgres. Now...