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 oneway streets of a city); otherwise, the graph is undirected. In the following table, examples of wellknown graphs are provided:
Graph example 
Type 
Nodes 
Edges 

Internet network 
Directed 
Web pages 
Links 

Undirected 
People 
Friendship 

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...