Graph Theory

import numpy as np
from collections import defaultdict

# Adjacency Matrix
class AdjMatrixGraph:
    def __init__(self, n):
        self.n = n
        self.matrix = np.zeros((n, n), dtype=int)

    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        self.matrix[v][u] = weight  # undirected

    def has_edge(self, u, v):
        return self.matrix[u][v] != 0

    def degree(self, v):
        return int(self.matrix[v].sum())

# Adjacency List
class AdjListGraph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v, weight=1):
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))

    def neighbors(self, v):
        return self.graph[v]

    def degree(self, v):
        return len(self.graph[v])

# Example usage
g = AdjListGraph()
edges = [(0,1), (0,2), (1,2), (2,3), (3,4)]
for u, v in edges:
    g.add_edge(u, v)

print(f"Degree of node 2: {g.degree(2)}")
print(f"Neighbors of 2: {g.neighbors(2)}")

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)
        order = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return order

    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        order = [start]
        for neighbor in self.graph[start]:
            if neighbor not in visited:
                order.extend(self.dfs(neighbor, visited))
        return order

    def is_connected(self, n_vertices):
        visited = self.bfs(0)
        return len(visited) == n_vertices

g = Graph()
for u, v in [(0,1), (0,2), (1,3), (2,3), (3,4)]:
    g.add_edge(u, v)

print("BFS:", g.bfs(0))
print("DFS:", g.dfs(0))
print("Connected:", g.is_connected(5))

def has_euler_path(graph, n_vertices):
    odd_degree = [v for v in range(n_vertices) if graph.degree(v) % 2 != 0]
    return len(odd_degree) == 0 or len(odd_degree) == 2

def euler_circuit_exists(graph, n_vertices):
    return all(graph.degree(v) % 2 == 0 for v in range(n_vertices))

def greedy_coloring(graph, n_vertices):
    result = [-1] * n_vertices
    result[0] = 0
    for u in range(1, n_vertices):
        available = set(range(n_vertices))
        for neighbor in graph[u]:
            if result[neighbor] != -1:
                available.discard(result[neighbor])
        result[u] = min(available)
    return result

def chromatic_number_upper_bound(n_vertices):
    return n_vertices  # Worst case: complete graph