Version: 0.3.38

Graphs

This module focuses on graphs: Webs of nodes connected by links. Graph is a versatile concept that surfaces is every application domain, from transportation to Biology: Social networks, food webs, digital circuits, transportation maps, etc. We sill look at how to represent graphs in memory, how to traverse them, and more.

See also

Here we only scratched the surface, from the Computer Science angle. Graph is such a common construct that it has its dedicated bra of mathematics! There are many resources available to go further:

• Erciyes, E. (2018). Guide to Graph algorithms. 1st edition, Springer.

• Wilson, R. J. (1996). Introduction to graph theory. 4th edition, Addison-Wesley.

Contents

• 1. Graph Theory
  • 1.1. Graphs in Real-life
  • 1.2. Graphs Species
    • 1.2.1. Simple Graphs
    • 1.2.2. Directed Graphs
    • 1.2.3. Weighted Graphs
    • 1.2.4. Other Graph Species
  • 1.3. The Graph Jargon
  • 1.4. Alternative Representations
    • 1.4.1. Adjacency Matrix
    • 1.4.2. Incidence Matrix
  • 1.5. Graph Problems
  • 1.6. Graphs as Data Structures
    • 1.6.1. Graph ADT
    • 1.6.2. Graph Representations
    • 1.6.3. Graph Traversals
  • 1.7. Appendix
    • 1.7.1. Edge List Pattern in Ruby
    • 1.7.2. Adjacency List in JavaScript
    • 1.7.3. Adjacency Matrix in C
• 2. Reachability & Shortest Paths
• 3. Minimum Spanning Trees