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