Chapter 3

My notes on Chapter 3 readings

• Graphs are the coolest. A graph is a collection V of vertices and a collection E of edges such that each edge e∈E joins exactly two vertices in V.
• They can be used to model a lot of things:
  • transportation networks
  • communication networks
  • information networks
  • social networks
  • dependency networks
• A path is a(n order-dependent) sequence of vertices such that there are edges between every consecutive pair of vertices in the sequence and that sequence gets you from one vertex to another.
  • A cycle is a path from any vertex back to itself that contains at least two other vertices.
  • A graph is then connected if there is a path in that graph connecting any two vertices.
  • If the graph is directed, it's strongly connected if there's a path from any vertex u to any other vertex v, and vice versa.
• An undirected graph is a tree if it has no cycles.
  • Every n-node tree has exactly n-1 edges
• I love graphs, so this section was an easy read. 10/10.