Directed graphs

1. How many objects guarantee two in the same box with 6 boxes?
   Stuck? Peek at 0.2.4 Pigeonhole principle

   • n + 1 objects in n boxes ⇒ some box has ≥ 2.
   • N objects in k boxes ⇒ some box has ≥ ⌈N/k⌉. To force m in a box: (m−1)k + 1 objects.
   • Machine with n modes, input length ≥ n ⇒ some mode repeats ⇒ a loop in the input.

   Read lesson 0.2.4

2. Why is “If Q then P” not equivalent to “If P then Q”?
   Stuck? Peek at 0.2.3 Proof techniques

   • P ⇒ Q false only when P true, Q false. Contrapositive ¬Q ⇒ ¬P ≡ original. Converse/inverse are NOT.
   • Contradiction: assume ¬S, derive the impossible. Used for “no machine can…” proofs.
   • Induction: base S(n₀) + step S(k) ⇒ S(k+1). Strong induction assumes all S(≤k).
   • One counterexample kills a “for all”. Examples never prove it.

   Read lesson 0.2.3

3. If |A| = 3, |B| = 4, what is |A × B|?
   Stuck? Peek at 0.2.1 Sets

   • x ∈ A (element) vs X ⊆ A (subset). ∅ ⊆ every set. A = B ⇔ A ⊆ B and B ⊆ A.
   • A ∪ B, A ∩ B, A − B = A ∩ B̅, A̅ = U − A. De Morgan: (A∪B)̅ = A̅∩B̅, (A∩B)̅ = A̅∪B̅.
   • |A ∪ B| = |A| + |B| − |A ∩ B|. |A × B| = |A|·|B|. |P(A)| = 2^|A|.
   • |∅| = 0, |{∅}| = 1, P(∅) = {∅}.

   Read lesson 0.2.1

A city map with one-way streets. Can you drive from the station to the stadium? Is there a route that brings you back to where you started? A machine diagram is exactly such a map: dots are modes, one-way arrows are moves labelled by the symbol read. Asking “is there any input this machine says yes to?” becomes “can you drive from the start to a yes-dot?”.

In a map with 5 junctions, if a route visits 6 junctions (counting repeats), must it pass through some junction twice?

Prediction check

Answer: yes — pigeonhole: 6 visits, 5 junctions. A route that repeats a junction contains a cycle.

Directed graph

• Self-loop: an edge (u, u).
• Out-degree of u: number of edges leaving u. In-degree: number entering.
• Labelled graph: each edge carries a label (like a symbol a). Machine diagrams are labelled directed graphs.

Paths and cycles

• A path is a sequence of nodes v₀, v₁, …, vₖ with an edge from each to the next; its length is k (number of edges).
• A cycle is a path of length ≥ 1 that starts and ends at the same node. A self-loop is a cycle of length 1.
• In a labelled graph, a path spells a word: follow arrows a, b, b → the path spells “abb”.

Reachability

Node v is reachable from u if there is a path from u to v (u is always reachable from itself by the length-0 path).

To find everything reachable from u: start with {u}; repeatedly add any node that has an edge from a node already found; stop when nothing new is added. (This is breadth-first search.) It always finishes because there are finitely many nodes.

Fact: if v is reachable from u in a graph with n nodes, there is a path of length ≤ n − 1 (drop any cycle from a longer path).

Cycles and “infinitely many routes”

If a cycle is reachable from u and the cycle can reach v, then there are routes from u to v of unboundedly many lengths (go around the cycle as often as you like). If no cycle lies on any u→v route, there are only finitely many routes. Later, “does this machine accept infinitely many inputs?” will become exactly this question.

Putting it together

• A directed graph is nodes plus one-way edges; labelled paths spell words.
• Reachable set: grow from the start until nothing new appears.
• Infinitely many paths from u to v exactly when a cycle lies on some route between them.

        a           b
   ┌──► 1 ──────► 2 ─────┐        edges: (0,1) (1,2) (2,3) (3,1) (2,2) (0,4)
   │              │ ▲    ▼        2 has a self-loop labelled c
   0              └─┘c   3        cycle: 1 → 2 → 3 → 1
   │                     │        reachable from 0: {0,1,2,3,4}
   └──► 4         1 ◄────┘ d      reachable from 4: {4}  (no edges out)
      e
 path 0→1→2→2→3 spells "a b c b"

Math toolkit done: sets, functions, equivalence classes, proofs, pigeonhole, graphs. Next we build the raw material machines read: symbols and strings.

1. MCQ

   In a directed graph with 6 nodes, if v is reachable from u, there is always a path from u to v of length at most:

   1. 3
   2. 5
   3. 6
   4. 36
2. MSQ

   Graph: edges (1,2), (2,3), (3,2), (3,4). Which are true?

   1. 4 is reachable from 1
   2. 1 is reachable from 4
   3. There is a cycle
   4. There are infinitely many paths from 1 to 4
3. NAT

   A directed graph on 3 nodes may have any subset of the 9 possible edges (self-loops allowed). How many such graphs are there?

   Write your answer before opening the key.

4. MCQ

   A path in a labelled graph follows edges labelled 0, 1, 1, 0. What word does it spell and what is its length?

   1. 0110, length 4
   2. 0110, length 5
   3. 01, length 2
   4. 0110, length 3

• directed graph, node, edge
• self-loop
• in-degree, out-degree
• labelled edge
• path, path length
• cycle
• reachability (BFS)
• dead end (no outgoing edges)

1. When are there infinitely many paths from u to v?
   Reveal answer

   When some cycle lies on a route from u to v.
2. Longest shortest path in an n-node graph?
   Reveal answer

   n − 1 edges.
3. Path length counts…?
   Reveal answer

   Edges.