Chapter 3

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

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