# Graph Theory, Trees, Recurrence Relations, Generating Functions & Automata

> Mathematical and algorithmic foundations for AI and computer science: graph search and spanning trees, asymptotic recurrences, generating functions, combinatorial structures, Boolean logic normal forms (CNF/DNF), and formal automata.

- **Canonical URL:** https://flashcards.world/flashcards/sets/399f5f90-68f8-4c10-a988-3e4c145fc3ef/
- **Markdown URL:** https://flashcards.world/flashcards/sets/399f5f90-68f8-4c10-a988-3e4c145fc3ef.md
- **Level:** advanced
- **Languages:** en → en
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | How is the Pumping Lemma for regular languages used to prove that L = {0ⁿ1ⁿ \| n ≥ 0} is not regular? | If L were regular with pumping length p, choose s = 0^p 1^p ∈ L. For any split s = xyz with \|xy\| ≤ p and \|y\| ≥ 1, y consists solely of 0s (y = 0^k, k ≥ 1). Pumping to xy²z = 0^{p+k}1^p yields unequal numbers of 0s and 1s, so xy²z ∉ L — a contradiction. |  |  |
| 2 | What is the Extended Binomial Series expansion for 1 / (1 − x)^k (k ≥ 1), and what is the coefficient of xⁿ? | 1 / (1 − x)^k = Σ_{n=0}^∞ C(n + k − 1, n) xⁿ, so the coefficient [xⁿ] is C(n + k − 1, k − 1). |  |  |
| 3 | What is the Ordinary Generating Function (OGF) of a sequence {aₙ}, and what sequence corresponds to G(x) = 1 / (1 − cx)? | G(x) = Σ_{n=0}^∞ aₙ xⁿ. For G(x) = 1 / (1 − cx) = Σ_{n=0}^∞ cⁿ xⁿ, the sequence is aₙ = cⁿ. |  |  |
| 4 | What is a bipartite graph, and what is König's characterization of bipartite graphs in terms of cycles? | A graph whose vertex set V can be partitioned into two disjoint independent sets V₁ and V₂ such that every edge connects a vertex in V₁ to one in V₂. A graph is bipartite if and only if it contains no cycles of odd length. |  |  |
| 5 | What is the minimum height of a binary tree with l leaves, and why does this imply the Ω(n log n) lower bound for comparison-based sorting? | A binary tree of height h has at most 2^h leaves, so h ≥ ⌈log₂ l⌉. A comparison decision tree sorting n elements must have at least n! leaves, requiring worst-case height ≥ log₂(n!) = Θ(n log n). |  |  |
| 6 | State Kleene's Theorem connecting regular expressions and finite automata. | A formal language L ⊆ Σ* is regular (recognized by some DFA/NFA) if and only if it can be described by a regular expression built from ∅, ε, alphabet symbols, union (∪), concatenation (·), and Kleene star (*). |  |  |
| 7 | How is a second-order linear homogeneous recurrence relation aₙ = c₁ a_{n−1} + c₂ a_{n−2} solved using its characteristic equation? | Solve r² − c₁ r − c₂ = 0: - If roots r₁ ≠ r₂ are distinct: aₙ = α r₁ⁿ + β r₂ⁿ. - If there is a repeated root r₀: aₙ = (α + β n) r₀ⁿ. |  |  |
| 8 | What does the k-th power A^k of the adjacency matrix A of a graph G represent? | The entry (A^k)_{ij} equals the exact number of walks of length k from vertex vᵢ to vertex vⱼ in G. |  |  |
| 9 | How does a Hamiltonian cycle differ from an Eulerian circuit, and what do Dirac's and Ore's Theorems guarantee? | A Hamiltonian cycle visits every vertex exactly once (deciding existence is NP-complete, unlike Eulerian circuits). For a simple graph on n ≥ 3 vertices, Ore's Theorem guarantees a Hamiltonian cycle if deg(u) + deg(v) ≥ n for every non-adjacent pair u ≠ v, and Dirac's Theorem guarantees one if deg(v) ≥ n/2 for every vertex v. |  |  |
| 10 | What are the axioms of a Boolean Algebra (B, +, ·, ', 0, 1)? | With distinct elements 0 ≠ 1: Associative laws, Commutative laws, Identity laws (x + 0 = x, x · 1 = x), Distributive laws (x · (y + z) = (x · y) + (x · z) and x + (y · z) = (x + y) · (x + z)), and Complement laws (x + x' = 1, x · x' = 0). |  |  |
| 11 | How does a Nondeterministic Finite Automaton (NFA) differ from a DFA, and why do they recognize the exact same class of languages? | An NFA allows transition function δ: Q × (Σ ∪ {ε}) → P(Q) (multiple or zero next states and ε-transitions). By the Subset (Powerset) Construction, any k-state NFA can be converted into an equivalent DFA with at most 2^k states. |  |  |
| 12 | How do Kruskal's and Prim's greedy algorithms construct a Minimum Spanning Tree (MST)? | Kruskal's algorithm sorts all edges by weight and repeatedly adds the lightest edge that does not create a cycle (using Union-Find). Prim's algorithm grows a single connected tree from a starting vertex by repeatedly adding the cheapest edge crossing the cut. |  |  |
| 13 | What is the formula for the n-th Catalan number Cₙ, and what classic combinatorial structures does it count? | Cₙ = (1 / (n + 1)) C(2n, n). It counts balanced parentheses strings of length 2n, full binary trees with n + 1 leaves, Dyck paths from (0,0) to (2n,0), and triangulations of a convex (n + 2)-gon. |  |  |
| 14 | What is the difference between Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF), and why is {NAND} functionally complete? | DNF is a disjunction (OR) of conjunctive terms (ANDs of literals; in full canonical DNF, a sum of minterms), whereas CNF is a conjunction (AND) of disjunctive clauses (ORs of literals; in full canonical CNF, a product of maxterms). {NAND} is functionally complete because NOT, AND, and OR can all be constructed using only NAND gates (e.g., ¬x = x NAND x). |  |  |
| 15 | State Hall's Marriage Theorem for bipartite graphs. | A bipartite graph G = (V₁, V₂, E) has a complete matching saturating every vertex of V₁ if and only if for every subset S ⊆ V₁, the neighborhood satisfies \|N(S)\| ≥ \|S\|. |  |  |
| 16 | What is graph isomorphism, and what are common graph invariants used to prove two graphs are NOT isomorphic? | Two graphs G₁ and G₂ are isomorphic if there is a bijection f: V(G₁) → V(G₂) preserving adjacency. Common invariants include vertex count, edge count, degree sequence, number of connected components, and lengths of simple cycles. |  |  |
| 17 | What is the recurrence relation and closed-form solution for the Tower of Hanoi puzzle with n disks? | Recurrence: Hₙ = 2H_{n−1} + 1 with H₁ = 1. Closed-form solution: Hₙ = 2ⁿ − 1 moves. |  |  |
| 18 | What are the four levels (Types 0, 1, 2, 3) of the Chomsky Hierarchy of formal grammars and their corresponding automata? | - Type 3: Regular Grammars ↔ Finite Automata (DFA/NFA) - Type 2: Context-Free Grammars ↔ Pushdown Automata (PDA) - Type 1: Context-Sensitive Grammars ↔ Linear Bounded Automata (LBA) - Type 0: Unrestricted Grammars ↔ Turing Machines. |  |  |
| 19 | State the Master Theorem for divide-and-conquer recurrences T(n) = a T(n/b) + Θ(n^d) (where a ≥ 1, b > 1, d ≥ 0). | Let c = log_b(a): 1. If d < c: T(n) = Θ(n^{log_b a}). 2. If d = c: T(n) = Θ(n^d log n). 3. If d > c: T(n) = Θ(n^d). |  |  |
| 20 | What is the chromatic number χ(G) of a graph, and what does the Four Color Theorem state? | χ(G) is the minimum number of colors needed to color the vertices of G so that no two adjacent vertices share the same color. The Four Color Theorem states that χ(G) ≤ 4 for every planar graph G. |  |  |
| 21 | Why are K₅ and K_{3,3} non-planar, and what does Kuratowski's Theorem state? | For K₅ (v = 5, e = 10), 3v − 6 = 9 < 10; for triangle-free K_{3,3} (v = 6, e = 9), 2v − 4 = 8 < 9. Kuratowski's Theorem states that a finite graph is planar if and only if it contains no subgraph homeomorphic to (a subdivision of) K₅ or K_{3,3}. |  |  |
| 22 | What are the necessary and sufficient conditions for an undirected multigraph (with at least one edge) to have an Eulerian circuit or an open Eulerian trail (path)? | Assuming all vertices of positive degree belong to a single connected component: - Eulerian circuit (closed trail visiting every edge exactly once): every vertex has even degree. - Open Eulerian trail (starts and ends at distinct vertices): exactly two vertices have odd degree. |  |  |
| 23 | State Euler's Formula for connected planar graphs and the resulting edge upper bounds. | For a connected planar drawing with v vertices, e edges, and f faces (regions), v − e + f = 2. For simple connected planar graphs with v ≥ 3, e ≤ 3v − 6 (and e ≤ 2v − 4 if the graph is triangle-free). |  |  |
| 24 | What are the four equivalent characterizations of an undirected tree T with n vertices? | 1. T is connected and acyclic. 2. T is connected and has n − 1 edges. 3. T is acyclic and has n − 1 edges. 4. There is a unique simple path between every pair of vertices in T. |  |  |
| 25 | What are Stirling numbers of the second kind S(n, k) and Bell numbers Bₙ? | S(n, k) counts the number of ways to partition an n-element set into k non-empty unlabeled subsets (satisfying S(n, k) = k S(n−1, k) + S(n−1, k−1)). The Bell number Bₙ = Σ_{k=0}^n S(n, k) is the total number of partitions of an n-element set. |  |  |
| 26 | How is a Deterministic Finite Automaton (DFA) formally defined as a 5-tuple? | M = (Q, Σ, δ, q₀, F), where Q is a finite set of states, Σ is a finite input alphabet, δ: Q × Σ → Q is the transition function, q₀ ∈ Q is the start state, and F ⊆ Q is the set of accepting (final) states. |  |  |
| 27 | How do weak connectivity and strong connectivity differ in a directed graph (digraph)? | A digraph is strongly connected if there is a directed path from u to v and from v to u for every pair of vertices; it is weakly connected if replacing all directed edges with undirected edges produces a connected graph. |  |  |
| 28 | In a full m-ary tree, if every internal vertex has exactly m children and there are i internal vertices, how many total vertices n and leaves l does the tree have? | Total vertices: n = m·i + 1. Leaves: l = (m − 1)i + 1. |  |  |
| 29 | State Cayley's Formula for the number of labeled trees on n vertices. | There are n^{n−2} distinct labeled trees on n ≥ 2 vertices (established via Prüfer sequences of length n − 2). |  |  |
| 30 | State the Handshaking Lemma for an undirected graph G = (V, E) and its consequence for odd-degree vertices. | The sum of the degrees of all vertices equals twice the number of edges: Σ_{v ∈ V} deg(v) = 2\|E\|. Consequently, every undirected graph has an even number of vertices of odd degree. |  |  |
| 31 | What is the recurrence relation and Binet's closed-form formula for the Fibonacci numbers Fₙ? | F₀ = 0, F₁ = 1, and Fₙ = F_{n−1} + F_{n−2} for n ≥ 2. Binet's formula is Fₙ = (φⁿ − ψⁿ) / √5, where φ = (1 + √5)/2 and ψ = (1 − √5)/2. |  |  |
| 32 | What are the numbers of vertices and edges in the complete graph Kₙ, complete bipartite graph K_{m,n}, and n-dimensional hypercube Qₙ? | - Kₙ: n vertices, n(n − 1)/2 edges. - K_{m,n}: m + n vertices, m · n edges. - Qₙ: 2ⁿ vertices, n · 2^{n−1} edges. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/399f5f90-68f8-4c10-a988-3e4c145fc3ef/).