Theoretische Informatik II - Lecture 01: Graphen Grundlagen

Recap of Landau Notation and Intervals

• Landau Symbols (Big-O Notation): Let f, g : N_{>0} \rightarrow R_{>0}.

  • Upper Bound ($O$): $f ∈ O(g)$ means $f$ grows at most as fast as $g$. Formally: ∃c > 0 ∃n_0 ≥ 0 ∀n ≥ n_0: f(n) ≤ c ⋅ g(n).

  • Lower Bound ($Ω$): $f ∈ Ω(g)$ means $f$ grows at least as fast as $g$. Formally: $f ∈ Ω(g) ⇔ g ∈ O(f)$.

  • Tight Bound ($Θ$): $f ∈ Θ(g)$ means $f$ grows exactly as fast as $g$. Formally: $f ∈ Θ(g) ⇔ f ∈ O(g) ∧ f ∈ Ω(g)$.

• Interval Notation:

  • For two numbers $x, y ∈ N$, define $[x, y] := \{x, x + 1, . . . , y - 1, y\}$.

  • Define $[x] := [1, x]$.

Fundamentals of Undirected Graphs

• Definition: An undirected graph $G$ is a pair $(V, E)$ consisting of:

  • A set $V$ of nodes (vertices).

  • A set $E ⊆ \{\{u, v\} | u ≠ v ∈ V\}$ of edges.

• Conventions:

  • Unless specified otherwise, graphs are assumed to be undirected by default.

  • Size notation: Typically, $n := |V|$ and $m := |E|$.

  • Edge notation: The notation $(u, v) ∈ E$ is commonly used for both undirected and directed edges.

• Example Setup:

  • $V = \{v_1, v_2, v_3, v_4, v_5, v_6\}$.

  • $E = \{\{v_1, v_5\}, \{v_1, v_6\}, \{v_2, v_4\}, \{v_2, v_5\}, \{v_2, v_6\}, \{v_3, v_6\}, \{v_4, v_5\}\}$.

Fundamentals of Directed Graphs (Digraphs)

• Definition: A directed graph (digraph) $G$ is a pair $(V, E)$ consisting of:

  • A set $V$ of nodes (vertices).

  • A set $E ⊆ \{(u, v) | u, v ∈ V\}$ of edges (sometimes called arcs).

• Self-Loops: In directed graphs, loops of the form $(v, v)$ are typically allowed, unlike in simple undirected graphs.

• Example Setup:

  • $V = \{v_1, v_2, v_3, v_4, v_5, v_6\}$.

  • $E = \{(v_1, v_2), (v_1, v_6), (v_2, v_5), (v_2, v_6), (v_4, v_5), (v_5, v_5), (v_6, v_1)\}$.

Essential Graph Terminology and Definitions

• Adjacency: A node $v ∈ V$ is adjacent (neighboring) to $u ∈ V$ if an edge exists between them (e.g., $\{u, v\} ∈ E$ for undirected graphs).

• Neighborhood ($N(v)$): The set of all nodes adjacent to $v$. Formally: $N_G(v) = \{u ∈ V | \{u, v\} ∈ E\}$.

• Degree ($deg_G(v)$): The size of a node's neighborhood. Formally: $deg_G(v) := |N(v)|$.

• Incidence: An edge $e = \{u, v\}$ is incident to its endpoints $u$ and $v$. This is denoted as $v, u ∈ e$.

• Path ($P$): A sequence of distinct, consecutive adjacent nodes. $P = (v_1, . . ., v_k)$ is a tuple such that:

  • For all $i ≠ j ∈ [k] : v_i ≠ v_j$.

  • For all $i ∈ [k - 1] : \{v_i, v_{i+1}\} ∈ E$.

  • This is called a $v_1$-$v_k$ path.

• Path Length: The number of edges in the path. A path $P = (v_1, . . ., v_k)$ has a length of $k - 1$.

• Cycle: A path with an additional edge connecting the last node back to the first node. Formally: $(v_1, . . ., v_k)$ where for all $i ∈ [k - 1] : \{v_i, v_{i+1}\} ∈ E$ and additionally $\{v_1, v_k\} ∈ E$.

• Reachability: A node $u ∈ V$ is reachable from $v ∈ V$ if there exists a $u$-$v$ path.

• Distance ($dist(u, v)$): The length of the shortest path between $u$ and $v$. If no path exists, $dist(u, v) = ∞$.

• Connectivity: A graph is connected if every node is reachable from every other node.

• Tree: A connected graph that contains no cycles.

Graph Representation: Adjacency Lists

• Structure: Consists of an array $A$ of size $n = |V|$. Each element $A[v]$ is a (doubly) linked list.

• Contents: For every node $v ∈ V$, the list $A[v]$ contains all nodes in its neighborhood $N(v)$.

• Storage Properties:

  • Nodes are typically named $V = \{1, 2, . . . , n\}$.

  • Total number of entries across all lists is $2|E|$ for undirected graphs because each edge appears twice (once in each endpoint's list).

  • The order of nodes within the linked lists is arbitrary.

Graph Representation: Adjacency Matrix

• Structure: Consists of a binary matrix $A ∈ \{0, 1\}^{|V| × |V|}$.

• Values: For all nodes $u, v ∈ V$:

  • $A[u, v] = 1$ if $\{u, v\} ∈ E$.

  • $A[u, v] = 0$ otherwise.

• Storage Complexity: An adjacency matrix always requires $Θ(|V|^2)$ memory space.

Comparison of Graph Representations

• Efficiency Criteria:

  • Adjacency Lists: Superior for sparse graphs where $|E|$ is significantly smaller than $|V|^2$. They are highly efficient for iterating through a node's neighbors.

  • Adjacency Matrix: Superior for dense graphs where $|E|$ approaches $|V|^2$. They allow for checking if an edge exists between two specific nodes $u, v$ in constant time ($O(1)$).

• Usage: Most algorithms discussed in this course utilize the Adjacency List representation.

Breadth-First Search (BFS)

• Objective: Given a graph $G = (V, E)$ and a source node $s ∈ V$, identify all nodes reachable from $s$ and determine the shortest distance $dist(s, v)$ for every node $v$.

• Search Logic: Nodes are visited incrementally by distance from the source (distance 1, then distance 2, etc.).

• Mechanism: Use an Discovery Queue ($Q$).

  • Visit the first node in the queue.

  • Add all previously undiscovered neighbors of that node to the end of the queue.

• Algorithm Pseudocode:

  • Initialize $d[v] ← ∞$ and $π[v] ← \text{NULL}$ for all $v ∈ V$.

  • Set $d[s] ← 0$.

  • Initialize Queue $Q ← (s)$.

  • while Q ist nicht leer do:

    • $v ←$ first node in $Q$ ($v$ is "visited").

    • Remove $v$ from $Q$.

    • for jeden u ∈ N(v) mit d[u] = ∞ do:

      • $d[u] = d[v] + 1$ and $π[u] = v$.

      • Append $u$ to the end of $Q$.

• Node States:

  • White: Undiscovered and unvisited.

  • Gray: Discovered (currently in the queue) but not yet visited.

  • Black: Fully visited (all neighbors processed).

• Correctness and Guarantees: At the algorithm's conclusion:

  • For nodes with d[v] < ∞: Node is reachable, $dist(s, v) = d[v]$, and $π[v]$ is the predecessor on a shortest $s$-$v$ path.

  • For nodes with $d[v] = ∞$: Node is not reachable from $s$.

• Runtime: On an adjacency list representation, BFS has a complexity of $O(|V| + |E|)$.

  • Each node enters and leaves the queue at most once.

  • For each node, neighbors are iterated via its adjacency list; thus, each edge is processed at most twice.

Depth-First Search (DFS)

• Logic: Instead of exploring the "breadth," the algorithm explores the "depth." It visits an undiscovered neighbor of the most recently visited node. If no such neighbor exists, it uses backtracking to return to the node from which the current node was discovered.

• Algorithm Pseudocode:

  • Initialize $π[v] ← \text{NULL}$ for all $v ∈ V$.

  • Call DFS-VISIT(s).

  • function DFS-VISIT(v):

    • for alle u ∈ N(v) do:

      • if π[u] = NULL ∧ u ≠ s then:

        • $π[u] = v$.

        • DFS-VISIT(u).

• Mechanism: Implemented via a Recursion Stack.

• Runtime: On an adjacency list representation, DFS has a complexity of $O(|V| + |E|)$.

Directed Acyclic Graphs (DAGs) and Topological Sorting

• Directed Graph Traversal: Both BFS and DFS work on directed graphs; when visiting a node, only outgoing edges to neighbors are explored.

• Directed Acyclic Graph (DAG): A directed graph that contains no cycles.

• Topological Sorting: A linear ordering of all nodes $v_1 ≺ v_2 ≺ ∙ ∙ ∙ ≺ v_{|V|}$ such that for every directed edge $(u, v) ∈ E$, it holds that $u ≺ v$.

• Existence and Calculation: A topological ordering exists for every DAG. It can be calculated using Depth-First Search with a runtime of $O(|V| + |E|)$.

Course Roadmap and Key Learning Objectives

• Current Goals:

  • Review basic graph terminology.

  • Master Breadth-First and Depth-First Search.

  • Understand Topological Sorting.

• Lecture Plan:

  • Part 1: Graph Algorithms: Graphs (VL 1), Shortest Paths (VL 2), Matching (VL 3), Flows (VL 4), Linear Programming (VL 5).

  • Part 2: Formal Languages: Automata & Regular Expressions (VL 6), Closure Properties & Myhill-Nerode (VL 7), Pumping Lemma & Grammars (VL 8), Decision Problems & Non-regular Languages (VL 9).

  • Part 3: Computational Hardness: Complexity Class NP (VL 10), NP-Hardness I & II (VL 11-12), Tractability Limits (VL 13), Approximation & ILP (VL 14).