====== Chapter 3 ======

===== Chapter 3.1 (Basic Definitions and Applications of Graphs) =====

__Definition - Graphs__
  * Graph = way of encoding pairwise relationships among a set of objects
    * Consists of a collection of both nodes and edges
    * Nodes
      * Often called a vertex as well
    * Edges
      * Written as a set of nodes - ex. (u, v)
  * Directed Graphs - represent asymmetric relationships
    * Where the edge points is the head of the edge
    * Where the edge points from is the tail of the edge

__Examples - Graphs__
  * Transportation network - nodes are airports while edges are possible flights
  * Communication network - nodes are computers while edges are direct links or within signal reach
  * Social network - nodes are people while edges are relationships (friendships, romantic, financial, etc.)
  * Dependency network - nodes are college courses while directed edges signify prerequisites.

__Paths and Connectivity__
  * Two types of paths - simple and cycle
    * Simple - sequence of connected distinct nodes
    * Cycle - sequence of connected nodes "cycles" back through itself repeatedly
  * Two types of connectivity - connected and disconnected
    * Connected - for every pair of nodes there is a path between them
      * Directed graphs are strongly connected if there is both a path from node u to node v and from node v to node u (possible to go from one to the other and back again).
    * Disconnected - one or more nodes have no edges joining them to the rest of the nodes in the graph
  * Distance - minimum number of edges between two nodes

__Trees__
  * Definition = undirected graph that is connected and does not contain a cycle
    * Root = from what the rest of the tree "hangs off of".
    * Parent = node with children beneath it (closer to root than children)
    * Child = node connected to a parent (farther from root than parent)
    * Leaf = node with no children
  * Every n-node tree has exactly n-1 edges

===== Chapter 3.2 (Graph Connectivity and Graph Traversal) =====

__Maze-Solving Problem__
  * S-T connectivity problem (if you have a node s and a node t, is there a path between the two)
  * Two algorithms to solve this problem are Breadth-First Search (BFS) and Depth-First Search (DFS)

__Breadth-First Search__
  * Algorithm ( O(n + m) )
    * Start with node s
    * Add nodes one layer at a time (everything that s is connected to)
    * Continue to add all additional nodes that are connected by an edge to any of the nodes in the first layer
    * Repeat until no new nodes can be found.
  * Whatever layer node t is in can determine the minimum distance between it and node s
  * Breadth-First Search creates a tree with the root at node s

__Depth-First Search__
  * Algorithm ( O(n + m) )
    * Start with node s
    * For each node adjacent to node s:
      * If unexplored:
        * Run algorithm recursively on said node
  *