46:"/_next/static/chunks/33yus346z0l_n.js" 47:"/_next/static/chunks/1r8ezocsukqp8.js" 48:"/_next/static/chunks/0iv56yrji_20j.js" 49:"/_next/static/chunks/0wa9m1-tphf9u.js" 4a:"/_next/static/chunks/08cuqqn_f60pp.js" 4b:"/_next/static/chunks/3zdsl3f9b0--r.js" 4c:"/_next/static/chunks/2j22cxchii_xx.js" 4d:"/_next/static/chunks/3bgoyiso1rhn7.js" 4e:"/_next/static/chunks/01a-3hvnqu8wl.js" 4f:"/_next/static/chunks/3m1xjj5kw5fie.js" 50:"/_next/static/chunks/0om3fkgfnicab.js" 51:"/_next/static/chunks/0gafyzg9j9yqj.js" 52:"/_next/static/chunks/20w4eaqlekefm.js" 53:"/_next/static/chunks/449--h5z1s6nq.js" 54:"/_next/static/chunks/3k2gyg36fnag_.js" 55:"/_next/static/chunks/18ggtgz2yf759.js" 56:"/_next/static/chunks/0hlb44ca7-4a2.js" 57:"/_next/static/chunks/253gnmj0-cj17.js" 58:"/_next/static/chunks/09nq57stwzkgf.js" 59:"/_next/static/chunks/082jo-0ajazgr.js" 5a:"/_next/static/chunks/2ozcrjb_hh74t.js" 5b:"/_next/static/chunks/05i8en-x14ibi.js" 5c:"/_next/static/chunks/32izpn90gvm22.js" 5d:"/_next/static/chunks/0jbzid2v9xv3h.js" 5e:"/_next/static/chunks/0i3-eynrkvqi7.js" 5f:"/_next/static/chunks/1tn-0fivsxsv1.js" 60:"/_next/static/chunks/34h36hyf_ggow.js" 61:"/_next/static/chunks/20329i6m_04t6.js" 62:"/_next/static/chunks/161uxd62cjny2.js" 63:"/_next/static/chunks/2k8pepwc4pxns.js" 64:I[593304,["$2b","$2c","$2d","$2e","$2f","$30","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61","$62","$63"],"OwnedHydration"] 65:T428,The study of Eulerian paths begins with one of the most celebrated problems in the history of mathematics: the **Seven Bridges of Königsberg**. **The Setting (1736):** Königsberg (now Kaliningrad, Russia) was built on the Pregel River, which contained two islands. The islands were connected to each other and the mainland by seven bridges. Citizens of Königsberg posed a recreational question: *Could one walk through the city, crossing each bridge exactly once, and return to the starting point?* **Euler's Revolutionary Insight:** Leonhard Euler approached this problem not by attempting various routes, but by abstracting it into what we now call a **graph**. He represented: - Each landmass (two banks and two islands) as a **vertex** (node) - Each bridge as an **edge** connecting two vertices This abstraction transformed a geographic puzzle into a purely mathematical question about graph structure. More importantly, Euler proved that the specific route doesn't matter—only the **structure** of connections determines whether such a walk exists.66:T52c, Königsberg Graph Representation ========================================= The city layout: The abstracted graph: North Bank A (North Bank) / | \ /|\ [1] [2] [3] / | \ / | \ e1 e2 e3 Island C ---- Island D / | \ \ [7] / C----e7---D [4] [5] \ | / \ [6] / e4 e6 e5 \ | / \ | / South Bank B (South Bank) Vertices: A (North), B (South), C (Island), D (Island) Edges: 7 bridges connecting the landmasses Degree of each vertex: - A (North Bank): 3 bridges → degree 3 - B (South Bank): 3 bridges → degree 3 - C (Island): 3 bridges → degree 3 - D (Island): 3 bridges → degree 3 All vertices have ODD degree!67:T4c8, Consider this graph: A ------- B |\ /| | \ / | | \ / | | \ / | | X | | / \ | | / \ | | / \ | |/ \| D ------- C Edges: A-B, A-C, A-D, B-C, B-D, C-D (6 edges = K4, complete graph on 4 vertices) EULERIAN CIRCUIT (traverse each edge once, return to start): -------------------------------------------------------- A → B → C → D → A → C → B → D → A Wait, this visits edges: A-B, B-C, C-D, D-A, A-C, C-B, B-D, D-A But we have duplicates! Let's try again... A → B → C → A → D → B → C → D → A ❌ Still not right Actually, K4 has 6 edges. Each vertex has degree 3 (odd). By Euler's theorem: NO Eulerian circuit exists in K4! HAMILTONIAN CYCLE (visit each vertex once, return to start): ----------------------------------------------------------- A → B → C → D → A ✓ This visits each vertex exactly once and returns to start. K4 definitely has Hamiltonian cycles! KEY INSIGHT: A graph can have Hamiltonian cycles without Eulerian circuits!68:Td4b,interface Graph { vertices: number; // Number of vertices (0 to V-1) adjacencyList: number[][]; // adjacencyList[v] = list of neighbors } enum EulerianType { NOT_EULERIAN = "No Eulerian path or circuit exists", EULERIAN_PATH = "Eulerian path exists (but not circuit)", EULERIAN_CIRCUIT = "Eulerian circuit exists" } /** * Determines if a graph has an Eulerian path, circuit, or neither. * Time Complexity: O(V + E) - we traverse the adjacency list once * Space Complexity: O(1) - only storing counts */ function classifyEulerian(graph: Graph): EulerianType { // Step 1: Check connectivity (required for both path and circuit) if (!isConnected(graph)) { // Exception: isolated vertices (degree 0) don't affect Eulerian properties // A more precise check would ignore isolated vertices return EulerianType.NOT_EULERIAN; } // Step 2: Count vertices with odd degree let oddDegreeCount = 0; for (let v = 0; v < graph.vertices; v++) { const degree = graph.adjacencyList[v].length; if (degree % 2 !== 0) { oddDegreeCount++; } } // Step 3: Apply Euler's theorem if (oddDegreeCount === 0) { // All vertices have even degree → Eulerian circuit exists return EulerianType.EULERIAN_CIRCUIT; } else if (oddDegreeCount === 2) { // Exactly two vertices have odd degree → Eulerian path exists return EulerianType.EULERIAN_PATH; } else { // More than two odd-degree vertices → impossible return EulerianType.NOT_EULERIAN; } } /** * Check if graph is connected using DFS * Ignores isolated vertices (vertices with degree 0) */ function isConnected(graph: Graph): boolean { // Find a vertex with non-zero degree to start let startVertex = -1; let nonIsolatedCount = 0; for (let v = 0; v < graph.vertices; v++) { if (graph.adjacencyList[v].length > 0) { nonIsolatedCount++; if (startVertex === -1) { startVertex = v; } } } // If no edges exist, trivially "connected" (or empty) if (startVertex === -1) { return true; } // DFS to count reachable non-isolated vertices const visited = new Set(); const stack = [startVertex]; while (stack.length > 0) { const current = stack.pop()!; if (visited.has(current)) continue; visited.add(current); for (const neighbor of graph.adjacencyList[current]) { if (!visited.has(neighbor)) { stack.push(neighbor); } } } // Check if all non-isolated vertices were reached return visited.size === nonIsolatedCount; } // Example usage with the Königsberg bridge graph const konigsbergGraph: Graph = { vertices: 4, // A=0 (North), B=1 (South), C=2 (Island1), D=3 (Island2) adjacencyList: [ [2, 2, 3], // A connects to C (2 bridges) and D (1 bridge) [2, 2, 3], // B connects to C (2 bridges) and D (1 bridge) [0, 0, 1, 1, 3], // C connects to A (2), B (2), D (1) [0, 1, 2] // D connects to A (1), B (1), C (1) ] }; console.log(classifyEulerian(konigsbergGraph)); // Output: "No Eulerian path or circuit exists" // All 4 vertices have odd degree (3, 3, 5, 3)69:T11d0,/** * Hierholzer's Algorithm for finding an Eulerian Circuit * * Precondition: Graph must have an Eulerian circuit * (connected, all vertices have even degree) * * Time Complexity: O(E) - each edge is visited exactly once * Space Complexity: O(E) - for the result path and stack */ function findEulerianCircuit( numVertices: number, edges: [number, number][] // List of edges as [u, v] pairs ): number[] { // Build adjacency list with edge indices for efficient removal // Using a Map to track remaining edges at each vertex const adj: Map[] = Array.from( { length: numVertices }, () => new Map() ); // For undirected graph, each edge appears in both directions // We use an index to track which edges have been used const edgeUsed: boolean[] = new Array(edges.length).fill(false); for (let i = 0; i < edges.length; i++) { const [u, v] = edges[i]; // Store edge index at both endpoints if (!adj[u].has(v)) adj[u].set(v, []); if (!adj[v].has(u)) adj[v].set(u, []); adj[u].get(v)!.push(i); adj[v].get(u)!.push(i); } const circuit: number[] = []; const stack: number[] = [0]; // Start from vertex 0 // Track current position in each vertex's neighbor list const pointers: Map[] = adj.map( neighbors => new Map([...neighbors.keys()].map(k => [k, 0])) ); while (stack.length > 0) { const current = stack[stack.length - 1]; // Find an unused edge from current vertex let foundEdge = false; for (const [neighbor, edgeIndices] of adj[current]) { // Try to find an unused edge to this neighbor while (pointers[current].get(neighbor)! < edgeIndices.length) { const edgeIdx = edgeIndices[pointers[current].get(neighbor)!]; pointers[current].set(neighbor, pointers[current].get(neighbor)! + 1); if (!edgeUsed[edgeIdx]) { edgeUsed[edgeIdx] = true; stack.push(neighbor); foundEdge = true; break; } } if (foundEdge) break; } if (!foundEdge) { // No more unused edges from this vertex // Add it to the circuit (in reverse order) circuit.push(stack.pop()!); } } // Circuit is built in reverse circuit.reverse(); return circuit; } // Simplified version using adjacency list with degree tracking function findEulerianCircuitSimple(adjacencyList: number[][]): number[] { // Clone the adjacency list since we'll modify it const adj = adjacencyList.map(neighbors => [...neighbors]); const circuit: number[] = []; const stack: number[] = [0]; while (stack.length > 0) { const current = stack[stack.length - 1]; if (adj[current].length > 0) { // Take an edge from current to a neighbor const next = adj[current].pop()!; // Remove the reverse edge (for undirected graph) const reverseIdx = adj[next].indexOf(current); if (reverseIdx !== -1) { adj[next].splice(reverseIdx, 1); } stack.push(next); } else { // No more edges from this vertex circuit.push(stack.pop()!); } } return circuit.reverse(); } // Example: Find Eulerian circuit in a house-shaped graph // 0 // /|\ // 1-+-2 // | X | // |/ \| // 3---4 const houseGraph = [ [1, 2], // 0 connects to 1, 2 [0, 2, 3, 4], // 1 connects to 0, 2, 3, 4 [0, 1, 3, 4], // 2 connects to 0, 1, 3, 4 [1, 2, 4], // 3 connects to 1, 2, 4 [1, 2, 3] // 4 connects to 1, 2, 3 ]; // Wait - let's verify: degrees are 2, 4, 4, 3, 3 // Vertices 3 and 4 have odd degree! This has Eulerian PATH, not circuit. // Correct example - add edge between 3 and 4 to make all even: const eulerianGraph = [ [1, 2], // Degree 2 (even) [0, 2, 3, 4], // Degree 4 (even) [0, 1, 3, 4], // Degree 4 (even) [1, 2, 4, 4], // Degree 4 (even) - two edges to 4 [1, 2, 3, 3] // Degree 4 (even) - two edges to 3 ]; console.log(findEulerianCircuitSimple(eulerianGraph)); // Possible output: [0, 1, 3, 4, 3, 2, 4, 1, 2, 0]6a:T106c,/** * Backtracking algorithm to find a Hamiltonian cycle * * Time Complexity: O(n!) worst case - exponential * Space Complexity: O(n) for the path and recursion stack * * This demonstrates the computational difficulty of Hamiltonian problems. */ function findHamiltonianCycle(adjacencyList: number[][]): number[] | null { const n = adjacencyList.length; if (n < 3) return null; // Need at least 3 vertices for a cycle const path: number[] = new Array(n).fill(-1); const visited: boolean[] = new Array(n).fill(false); // Start from vertex 0 path[0] = 0; visited[0] = true; function backtrack(pos: number): boolean { // Base case: all vertices are in the path if (pos === n) { // Check if there's an edge from last vertex back to first const lastVertex = path[n - 1]; const firstVertex = path[0]; return adjacencyList[lastVertex].includes(firstVertex); } // Try each vertex as the next in the path for (const nextVertex of adjacencyList[path[pos - 1]]) { if (!visited[nextVertex]) { // Choose path[pos] = nextVertex; visited[nextVertex] = true; // Explore if (backtrack(pos + 1)) { return true; } // Unchoose (backtrack) visited[nextVertex] = false; path[pos] = -1; } } return false; } if (backtrack(1)) { return path; } return null; } // Optimized version with pruning function findHamiltonianCycleOptimized(adjacencyList: number[][]): number[] | null { const n = adjacencyList.length; if (n < 3) return null; // Precompute for pruning: if any vertex becomes unreachable, abort const path: number[] = [0]; const visited: boolean[] = new Array(n).fill(false); visited[0] = true; function canComplete(path: number[]): boolean { // Early pruning: check if remaining vertices are still reachable const remaining = n - path.length; if (remaining === 0) return true; // Check if every unvisited vertex has at least one unvisited neighbor // (or is connected to path endpoint) for (let v = 0; v < n; v++) { if (!visited[v]) { let hasConnection = false; for (const neighbor of adjacencyList[v]) { if (!visited[neighbor] || neighbor === path[path.length - 1]) { hasConnection = true; break; } } if (!hasConnection && remaining > 1) return false; } } return true; } function backtrack(): boolean { if (path.length === n) { return adjacencyList[path[n - 1]].includes(0); } const current = path[path.length - 1]; // Sort neighbors by degree (choose most constrained first - heuristic) const neighbors = [...adjacencyList[current]] .filter(v => !visited[v]) .sort((a, b) => { const degA = adjacencyList[a].filter(x => !visited[x]).length; const degB = adjacencyList[b].filter(x => !visited[x]).length; return degA - degB; // Most constrained first }); for (const next of neighbors) { path.push(next); visited[next] = true; if (canComplete(path) && backtrack()) { return true; } visited[next] = false; path.pop(); } return false; } if (backtrack()) { return path; } return null; } // Example: Pentagon graph (cycle of 5) const pentagon = [ [1, 4], // 0 [0, 2], // 1 [1, 3], // 2 [2, 4], // 3 [3, 0] // 4 ]; console.log(findHamiltonianCycle(pentagon)); // Output: [0, 1, 2, 3, 4] - trivially Hamiltonian since it's a cycle6b:Tcad,/** * Find Eulerian path in directed graph * Used in DNA fragment assembly via de Bruijn graphs * * The de Bruijn graph approach: * 1. Break DNA reads into k-mers (length k substrings) * 2. Create vertices for (k-1)-mers * 3. Create edges for k-mers connecting their prefix to suffix * 4. Find Eulerian path to reconstruct the original sequence */ interface DirectedGraph { vertices: number; adjacencyList: number[][]; // outgoing edges only } function findEulerianPathDirected(graph: DirectedGraph): number[] | null { const { vertices, adjacencyList } = graph; // Calculate in-degree and out-degree for each vertex const inDegree: number[] = new Array(vertices).fill(0); const outDegree: number[] = new Array(vertices).fill(0); for (let v = 0; v < vertices; v++) { outDegree[v] = adjacencyList[v].length; for (const neighbor of adjacencyList[v]) { inDegree[neighbor]++; } } // Find start and end vertices let startVertex = -1; let endVertex = -1; let extraOutgoing = 0; let extraIncoming = 0; for (let v = 0; v < vertices; v++) { const diff = outDegree[v] - inDegree[v]; if (diff === 1) { extraOutgoing++; startVertex = v; } else if (diff === -1) { extraIncoming++; endVertex = v; } else if (diff !== 0) { return null; // Invalid for Eulerian path } } // Validate: either circuit (0 imbalanced) or path (exactly 2 imbalanced) if (!(extraOutgoing === 0 && extraIncoming === 0) && !(extraOutgoing === 1 && extraIncoming === 1)) { return null; } // For Eulerian circuit, start anywhere; for path, start at startVertex const start = startVertex === -1 ? 0 : startVertex; // Clone adjacency list for modification const adj = adjacencyList.map(neighbors => [...neighbors]); // Hierholzer's algorithm for directed graphs const path: number[] = []; const stack: number[] = [start]; while (stack.length > 0) { const current = stack[stack.length - 1]; if (adj[current].length > 0) { const next = adj[current].pop()!; stack.push(next); } else { path.push(stack.pop()!); } } path.reverse(); // Verify we used all edges const totalEdges = adjacencyList.reduce((sum, n) => sum + n.length, 0); if (path.length !== totalEdges + 1) { return null; // Graph not connected enough } return path; } // Example: Simple directed graph with Eulerian path // 0 → 1 → 2 → 3 // 0 → 2 const directedGraph: DirectedGraph = { vertices: 4, adjacencyList: [ [1, 2], // 0 → 1, 0 → 2 [2], // 1 → 2 [3], // 2 → 3 [] // 3 has no outgoing ] }; console.log(findEulerianPathDirected(directedGraph)); // Output: [0, 1, 2, 3] or [0, 2, 3] + more edges... // Actually: [0, 2, 3] misses edge 0→1, 1→2 // Correct path visits all 4 edges: 0→1→2→3 and 0→2 // One valid path: [0, 1, 2, 3] but misses 0→2 // Need to reconsider... The graph has 4 edges.6c:T41d,The comparison between Eulerian and Hamiltonian problems illustrates one of the deepest themes in computer science: the boundary between tractable and intractable problems. **What Makes Eulerian Problems Tractable:** 1. **Local characterization:** The condition (even degrees) can be checked at each vertex independently. 2. **No global dependencies:** Using an edge at one part of the graph doesn't affect what's possible elsewhere. 3. **Constructive proof:** The same reasoning that proves existence also constructs a solution. 4. **Invariant preservation:** The algorithm maintains the invariant that remaining edges form a valid structure. **What Makes Hamiltonian Problems Intractable:** 1. **Global constraints:** Visiting vertex X early may prevent reaching vertex Y later. 2. **Complex dependencies:** The effect of a choice propagates throughout the entire graph. 3. **No simple characterization:** We can't check existence without essentially searching. 4. **NP-completeness:** Any efficient algorithm would solve all NP-complete problems.45:["$","$L64",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792317404453,"state":{"data":{"json":{"id":"seed_04f8a3129d345e6bc7e8336bd33a82a0","slug":"advanced-graph-patterns","category":"Data Structures & Algorithms","topic":"Advanced Graph Patterns","title":"Advanced Graph Patterns: Classical Problems & Computational Boundaries","description":"Explore the boundaries of efficient graph algorithms through classical problems like Eulerian paths, Hamiltonian cycles, graph coloring, and the Traveling Salesman Problem. Understand what makes some problems tractable and others fundamentally intractable, and learn to recognize NP-hard problems in practice.","difficulty":"ADVANCED","estimatedMinutes":90,"pages":[{"id":"seed_0f6eb64dfed4eaee027ba195ff7bb187","title":"Eulerian and Hamiltonian Paths: Two Sides of Graph Traversal","order":0,"content":[{"id":"opening-traversal-problems","title":"The Two Fundamental Traversal Problems","content":[{"data":{"content":"Graph theory presents two seemingly similar questions that lie at the heart of discrete mathematics and computer science:\n\n**Question 1:** *Can we traverse every **edge** of a graph exactly once, returning to our starting point?*\n\n**Question 2:** *Can we visit every **vertex** of a graph exactly once, returning to our starting point?*\n\nThese questions appear nearly identical—one focuses on edges, the other on vertices. Yet their computational complexity differs dramatically. The first question can be answered in polynomial time with a simple characterization. The second is one of the most famous unsolved problems in computer science, belonging to the class of NP-complete problems.\n\nUnderstanding why these similar-sounding problems have such different complexities provides profound insight into the nature of computation itself."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Master","content":"By the end of this page, you will understand: (1) The precise definitions of Eulerian and Hamiltonian paths/circuits, (2) The elegant mathematical characterization that makes Eulerian problems tractable, (3) Why no such characterization exists for Hamiltonian problems, (4) Algorithms for finding Eulerian paths, and (5) The broader implications for recognizing tractable vs. intractable problems.","variant":"info"},"type":"callout"}]},{"id":"historical-origins","title":"Historical Origins: The Königsberg Bridge Problem","content":[{"data":{"content":"$65"},"type":"text"},{"data":{"code":"$66","title":"The Seven Bridges of Königsberg as a Graph","language":"plaintext"},"type":"code"},{"data":{"content":"**Euler's Theorem (1736):**\n\nEuler discovered that an Eulerian circuit (a closed walk traversing every edge exactly once) exists if and only if:\n1. The graph is connected (all vertices can reach all others)\n2. **Every vertex has even degree**\n\nSince all four vertices in the Königsberg graph have odd degree (3), no Eulerian circuit exists. Euler proved this impossible—not by exhaustive search, but by pure logical reasoning.\n\nThis 1736 paper is widely considered the birth of both **graph theory** and **topology**, making it one of the most important papers in the history of mathematics."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Power of Abstraction","content":"Euler's insight exemplifies the power of mathematical abstraction. By ignoring irrelevant details (bridge lengths, island shapes, walking speed) and focusing on structure (what connects to what), he transformed an impossible enumeration problem into a simple counting problem. This abstraction principle underlies all of computer science.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"formal-definitions","title":"Formal Definitions: Paths, Circuits, and Trails","content":[{"data":{"content":"Before diving deeper, we need precise definitions. Graph theory terminology can be confusing because different authors use terms differently. Here we establish rigorous definitions:\n\n**Basic Walk Terminology:**\n\n- **Walk:** A sequence of vertices where consecutive vertices are connected by edges. Vertices and edges may repeat.\n- **Trail:** A walk where **no edge repeats** (but vertices may repeat).\n- **Path:** A walk where **no vertex repeats** (and thus no edge repeats).\n- **Closed Walk/Circuit:** A walk that starts and ends at the same vertex.\n- **Cycle:** A closed path (no repeated vertices except start = end)."},"type":"text"},{"data":{"rows":[["Walk","Allowed","Allowed","May or may not"],["Trail","Not allowed","Allowed","May or may not"],["Path","Not allowed","Not allowed","No"],["Circuit","Allowed","Allowed","Yes (by definition)"],["Eulerian Trail","Not allowed (visits each once)","Allowed","No"],["Eulerian Circuit","Not allowed (visits each once)","Allowed","Yes"],["Hamiltonian Path","Not allowed","Not allowed (visits each once)","No"],["Hamiltonian Cycle","Not allowed","Not allowed (visits each once)","Yes"]],"caption":"Walk Types and Their Constraints","headers":["Type","Edge Repetition","Vertex Repetition","Returns to Start"]},"type":"table"},{"data":{"content":"**Eulerian Definitions:**\n\n- **Eulerian Trail (Eulerian Path):** A trail that visits **every edge** of the graph exactly once. Does not need to return to the starting vertex.\n\n- **Eulerian Circuit (Eulerian Cycle):** A trail that visits every edge exactly once **and returns to the starting vertex**. This is a closed Eulerian trail.\n\n- **Eulerian Graph:** A graph that contains an Eulerian circuit.\n\n- **Semi-Eulerian Graph:** A graph that contains an Eulerian trail but not an Eulerian circuit.\n\n**Hamiltonian Definitions:**\n\n- **Hamiltonian Path:** A path that visits **every vertex** of the graph exactly once.\n\n- **Hamiltonian Cycle:** A cycle that visits every vertex exactly once and returns to the starting vertex.\n\n- **Hamiltonian Graph:** A graph that contains a Hamiltonian cycle."},"type":"text"},{"data":{"icon":"AlertCircle","title":"Critical Distinction","content":"The key difference: Eulerian problems ask about traversing EDGES; Hamiltonian problems ask about visiting VERTICES. This seemingly small distinction creates an enormous gap in computational complexity. Always clarify which problem you're solving.","variant":"warning"},"type":"callout"},{"data":{"code":"$67","title":"Visual Comparison: Eulerian vs. Hamiltonian","language":"plaintext"},"type":"code"}],"titleType":"number","titleNumber":2},{"id":"euler-theorems","title":"Euler's Theorems: Complete Characterization","content":[{"data":{"content":"The beauty of Eulerian problems lies in their **complete characterization**. We can determine whether an Eulerian path or circuit exists by simply counting vertex degrees—no search required.\n\n**Theorem 1 (Eulerian Circuit):**\n\nA connected graph G has an **Eulerian circuit** if and only if **every vertex has even degree**.\n\n**Theorem 2 (Eulerian Trail):**\n\nA connected graph G has an **Eulerian trail** (but not an Eulerian circuit) if and only if it has **exactly two vertices of odd degree**. The trail must start at one odd-degree vertex and end at the other.\n\n**Theorem 3 (Impossibility):**\n\nIf a connected graph has more than two vertices of odd degree, **no Eulerian trail or circuit exists**."},"type":"text"},{"data":{"items":["**Even Degree Necessity:** When we traverse a vertex (neither starting nor ending), we enter via one edge and leave via another. Each traversal 'uses' two edges. For all edges to be used exactly once, we need an even number of edges at each vertex.","**Odd Vertices Must Be Endpoints:** At the start vertex, we leave (use one edge) before any entry. At the end vertex, we enter (use one edge) with no exit. These vertices use an odd number of edges. All other vertices must use an even number.","**Exactly Two or Zero:** Since every edge connects exactly two vertices, the sum of all degrees equals 2|E| (even). Thus, the number of odd-degree vertices must be even. Combined with the endpoint argument: either 0 (circuit) or 2 (trail) odd vertices.","**The Handshaking Lemma:** The sum of all vertex degrees equals 2 × (number of edges). This fundamental lemma underlies the entire theory."],"title":{"icon":"Info","text":"Why These Theorems Work","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"code":"$68","title":"Checking for Eulerian Path/Circuit Existence","language":"typescript"},"type":"code"},{"data":{"icon":"Sparkles","title":"The Elegance of Characterization","content":"Notice the profound simplicity: to solve the Eulerian problem, we don't search for paths at all. We count degrees. This O(V + E) degree-counting provides a complete answer to a question that might naively seem to require exponential enumeration. This is what a 'good characterization' means in complexity theory.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"hierholzer-algorithm","title":"Hierholzer's Algorithm: Finding Eulerian Circuits","content":[{"data":{"content":"Once we've determined that an Eulerian circuit exists, how do we actually **find** it? Hierholzer's algorithm (1873) provides an elegant O(E) solution.\n\n**The Core Insight:**\n\nIf we start at any vertex and follow edges (removing them as we go), we must eventually return to the start vertex—because every vertex has even degree. This creates a **circuit**, but not necessarily an Eulerian circuit (we might not have used all edges).\n\nHowever, if there are unused edges, they must be attached to some vertex on our current circuit (since the graph is connected). We can find such a vertex, construct another circuit from it, and **splice** it into our main circuit.\n\nRepeating this process until all edges are used gives us the complete Eulerian circuit."},"type":"text"},{"data":{"code":"$69","title":"Hierholzer's Algorithm for Eulerian Circuits","language":"typescript"},"type":"code"},{"data":{"content":"**Algorithm Walkthrough:**\n\n1. **Start anywhere** (for a circuit, any vertex works)\n2. **Traverse edges greedily**, marking each as used\n3. **When stuck** (no unused edges from current vertex), backtrack and **record the vertex**\n4. **Continue** until stack is empty\n5. **Reverse** the recorded sequence to get the Eulerian circuit\n\n**Why This Works:**\n\nThe key insight is that when we backtrack and record a vertex, all edges incident to that vertex have been used. When we reach the starting vertex with no remaining edges, we've completed the circuit. The reversal corrects the order since we record vertices when leaving them, not when entering."},"type":"text"},{"data":{"icon":"Info","title":"Handling Eulerian Paths","content":"For an Eulerian PATH (exactly two odd-degree vertices), simply start from one of the odd-degree vertices. The same algorithm will find the path, ending at the other odd-degree vertex. You can also add a temporary edge between the two odd vertices, find the circuit, and remove that edge from the result.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"hamiltonian-problems","title":"Hamiltonian Problems: A Fundamentally Different Beast","content":[{"data":{"content":"Now we turn to Hamiltonian paths and cycles—problems that look superficially similar to Eulerian problems but are fundamentally different.\n\n**The Hamiltonian Cycle Problem:**\n\n*Given a graph G, does there exist a cycle that visits every vertex exactly once?*\n\n**The Stark Contrast with Eulerian Problems:**\n\nFor Eulerian problems, we have a complete characterization: count vertex degrees, and you know the answer. For Hamiltonian problems, **no such simple characterization exists**. Despite centuries of effort by brilliant mathematicians and computer scientists, we cannot determine if a graph has a Hamiltonian cycle without, in the worst case, essentially trying all possibilities.\n\nThis isn't just because we haven't been clever enough—it's believed to be **fundamentally impossible** for polynomial-time algorithms."},"type":"text"},{"data":{"left":[{"data":{"items":["**Complete characterization** exists (degree parity)","**O(V + E)** to determine existence","**O(E)** to find the actual path/circuit","Simple necessary and sufficient conditions","No search required—just count","Solved elegantly in 1736 by Euler"],"title":{"icon":"CheckCircle","text":"Eulerian Problems","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"}],"right":[{"data":{"items":["**No known characterization** exists","**NP-complete** to determine existence","**Exponential time** required in worst case","Only sufficient conditions (not necessary)","May require exhaustive search","Unsolved for polynomial time since defined"],"title":{"icon":"XCircle","text":"Hamiltonian Problems","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**Why Is Hamiltonian So Much Harder?**\n\nThe fundamental difference stems from the **global** nature of the Hamiltonian constraint versus the **local** nature of the Eulerian constraint:\n\n- **Eulerian (local):** Each edge must be traversed once. This constraint is satisfied by ensuring local conditions at each vertex (even degree). There's no \"interaction\" between distant parts of the graph.\n\n- **Hamiltonian (global):** Each vertex must appear exactly once in the path. This creates complex dependencies: visiting vertex A early might block access to vertex B later, even if they're not directly connected. The constraint propagates through the entire graph structure.\n\nNo local characterization can capture these global dependencies. The only way to verify is to consider the entire path structure—and there are potentially V! orderings to check."},"type":"text"},{"data":{"code":" Consider finding a Hamiltonian path in a complete graph Kn:\n \n n = 5 vertices:\n - Possible orderings: 5! = 120\n - Easily checkable by computer\n \n n = 10 vertices:\n - Possible orderings: 10! = 3,628,800\n - Still manageable\n \n n = 20 vertices:\n - Possible orderings: 20! ≈ 2.4 × 10^18\n - Would take centuries for brute force\n \n n = 50 vertices:\n - Possible orderings: 50! ≈ 3 × 10^64\n - More than atoms in the observable universe\n \n Contrast with Eulerian:\n - For ANY n, just count degrees: O(n) operations\n - No explosion of possibilities\n \n This is the essence of the P vs NP distinction.","title":"The Explosion of Possibilities","language":"plaintext"},"type":"code"}],"titleType":"number","titleNumber":5},{"id":"sufficient-conditions","title":"Sufficient Conditions for Hamiltonian Cycles","content":[{"data":{"content":"While we lack necessary and sufficient conditions for Hamiltonicity, mathematicians have discovered several **sufficient conditions**—conditions that, if satisfied, guarantee a Hamiltonian cycle exists (though the graph might have one even if they're not satisfied).\n\n**Theorem (Dirac, 1952):**\n\nIf G is a simple graph with n ≥ 3 vertices and every vertex has degree ≥ n/2, then G has a Hamiltonian cycle.\n\n**Theorem (Ore, 1960):**\n\nIf G is a simple graph with n ≥ 3 vertices and for every pair of non-adjacent vertices u and v, degree(u) + degree(v) ≥ n, then G has a Hamiltonian cycle.\n\n**Special Cases:**\n\n- **Complete graphs Kn (n ≥ 3):** Always Hamiltonian\n- **Complete bipartite graphs Km,n (m = n):** Always Hamiltonian\n- **Hypercubes Qn:** Always Hamiltonian for n ≥ 2"},"type":"text"},{"data":{"icon":"AlertCircle","title":"Sufficient ≠ Necessary","content":"These conditions are NOT necessary! Many graphs with Hamiltonian cycles fail these conditions. A cycle graph Cn has degree 2 at every vertex, far below n/2, yet it's trivially Hamiltonian. Failing these tests proves nothing about non-existence.","variant":"warning"},"type":"callout"},{"data":{"code":"$6a","title":"Backtracking Algorithm for Hamiltonian Cycle","language":"typescript"},"type":"code"}],"titleType":"number","titleNumber":6},{"id":"directed-variations","title":"Directed Graphs and Variations","content":[{"data":{"content":"Both Eulerian and Hamiltonian concepts extend to **directed graphs** with modified conditions.\n\n**Eulerian Circuits in Directed Graphs:**\n\nA strongly connected directed graph has an Eulerian circuit if and only if:\n- Every vertex has **in-degree equal to out-degree**\n\nFor an Eulerian path (not circuit):\n- At most one vertex has out-degree = in-degree + 1 (start vertex)\n- At most one vertex has in-degree = out-degree + 1 (end vertex)\n- All other vertices have in-degree = out-degree\n\n**Common Applications:**"},"type":"text"},{"data":{"rows":[["DNA Fragment Assembly","Directed","Eulerian Path","De Bruijn graphs for genome sequencing"],["Chinese Postman Problem","Undirected/Directed","Eulerian Path","Minimum-distance route covering all streets"],["Traveling Salesman","Complete + Weights","Hamiltonian Cycle","Minimum-cost tour visiting all cities"],["Knight's Tour","Undirected","Hamiltonian Path","Chess knight visiting all squares once"],["Circuit Board Testing","Directed","Eulerian Path","Testing all connections with one probe run"],["Gray Code Generation","Hypercube","Hamiltonian Cycle","Binary counting with single-bit changes"]],"caption":"Real-World Applications of Eulerian and Hamiltonian Concepts","headers":["Problem","Graph Type","Concept","Application"]},"type":"table"},{"data":{"code":"$6b","title":"Eulerian Path in Directed Graph (for DNA Assembly)","language":"typescript"},"type":"code"},{"data":{"icon":"Lightbulb","title":"DNA Sequencing Application","content":"Modern DNA sequencers produce millions of short 'reads' (typically 100-300 base pairs). Finding how these overlap to reconstruct the original genome is essentially an Eulerian path problem on a de Bruijn graph. This application of graph theory revolutionized genomics in the 2000s.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary-insights","title":"Summary: The Dichotomy of Tractability","content":[{"data":{"content":"$6c"},"type":"text"},{"data":{"type":"ordered","items":["**Eulerian = Edges, Hamiltonian = Vertices:** This seemingly small difference creates a vast complexity gap.","**Euler's theorem provides a complete characterization:** Check vertex degrees in O(V + E) to know if an Eulerian path/circuit exists.","**Hierholzer's algorithm finds Eulerian circuits in O(E):** Efficient construction is possible once existence is confirmed.","**Hamiltonian is NP-complete:** No polynomial-time algorithm is known, and none likely exists.","**Sufficient conditions for Hamiltonicity exist (Dirac, Ore)** but are not necessary—many Hamiltonian graphs fail them.","**These problems appear in real applications:** DNA sequencing (Eulerian), traveling salesman (Hamiltonian), route optimization, and circuit design."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Looking Ahead:**\n\nThe contrast between Eulerian and Hamiltonian problems foreshadows our broader study of computational complexity. In the upcoming pages, we'll explore more problems at the boundary of tractability—graph coloring, the Traveling Salesman Problem, and how to recognize when you've encountered an intractable problem in practice.\n\nUnderstanding this dichotomy is crucial for any engineer. It tells us when to seek efficient algorithms and when to settle for approximations, heuristics, or restricted problem instances."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the fundamental distinction between Eulerian and Hamiltonian graph traversal problems. You can characterize Eulerian graphs, apply Hierholzer's algorithm, and recognize why Hamiltonian problems resist efficient solution. Next, we'll explore graph coloring—another classical problem with surprising computational depth.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_a1b23f1742587a46b86d344b9da9716b","title":"Graph Coloring: The Art of Conflict-Free Assignment","order":1,"content":null,"isLocked":true},{"id":"seed_d3839125e14ac1a20f8803dd74d7f380","title":"The Traveling Salesman Problem: Icon of Computational Complexity","order":2,"content":null,"isLocked":true},{"id":"seed_915c2634f2240784130407cbd11e3fad","title":"Recognizing Intractable Problems: The Limits of Efficient Computation","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792317404443,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"advanced-graph-patterns"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"advanced-graph-patterns\"},\"type\":\"query\"}]"},{"dehydratedAt":1792317404453,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792317404450,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_04f8a3129d345e6bc7e8336bd33a82a0"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_04f8a3129d345e6bc7e8336bd33a82a0\"},\"type\":\"query\"}]"},{"dehydratedAt":1792317404453,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792317404450,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_a1b23f1742587a46b86d344b9da9716b"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_a1b23f1742587a46b86d344b9da9716b\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792317404453,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792317404450,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_a1b23f1742587a46b86d344b9da9716b"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_a1b23f1742587a46b86d344b9da9716b\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792317404453,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792317404450,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_a1b23f1742587a46b86d344b9da9716b"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_a1b23f1742587a46b86d344b9da9716b\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792317404453,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_a1b23f1742587a46b86d344b9da9716b","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_a1b23f1742587a46b86d344b9da9716b\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@6d"}]},"children":"$L6e"}]