Advanced Graph Patterns: Classical Problems & Computational Boundaries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

                    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!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

    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!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

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<number>();
    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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

/**
 * 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<number, number[]>[] = 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<number, number>[] = 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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    Consider finding a Hamiltonian path in a complete graph Kn:
    
    n = 5 vertices:
    - Possible orderings: 5! = 120
    - Easily checkable by computer
    
    n = 10 vertices:
    - Possible orderings: 10! = 3,628,800
    - Still manageable
    
    n = 20 vertices:
    - Possible orderings: 20! ≈ 2.4 × 10^18
    - Would take centuries for brute force
    
    n = 50 vertices:
    - Possible orderings: 50! ≈ 3 × 10^64
    - More than atoms in the observable universe
    
    Contrast with Eulerian:
    - For ANY n, just count degrees: O(n) operations
    - No explosion of possibilities
    
    This is the essence of the P vs NP distinction.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

/**
 * 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 cycle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

/**
 * 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.