图理论基础 (Basics of Graph Theory)

定义 (Definition)

图 (Graph) 是由一组顶点 (Vertices) 和一组边 (Edges) 组成的数学结构，其中每条边连接两个顶点。

A graph is a mathematical structure consisting of a set of vertices (or nodes) and a set of edges, where each edge connects two vertices.

形式化定义 (Formal Definition)

一个图 $G$ 可以表示为一个二元组 $(V, E)$ ，其中：

$V$ 是顶点的集合
$E$ 是边的集合，每条边是顶点对 $(u, v)$ 的集合

A graph $G$ can be represented as an ordered pair $(V, E)$ , where:

$V$ is the set of vertices
$E$ is the set of edges, where each edge is a pair $(u, v)$ of vertices

分类 (Classification)

无向图 (Undirected Graph)

无向图中的边没有方向，即边 $(u, v)$ 与 $(v, u)$ 是相同的。

In an undirected graph, edges have no direction, meaning the edge $(u, v)$ is the same as $(v, u)$ .

有向图 (Directed Graph or Digraph)

有向图中的边有方向，即边 $(u, v)$ 和 $(v, u)$ 是不同的。

In a directed graph, edges have a direction, meaning the edge $(u, v)$ is different from $(v, u)$ .

简单图 (Simple Graph)

简单图中没有自环（即 $(u, u)$ 的边）和重边（即多条相同的边）。

A simple graph has no loops (edges of the form $(u, u)$ ) and no multiple edges (no more than one edge between any pair of vertices).

完全图 (Complete Graph)

完全图中的每一对不同顶点之间都有一条边。

In a complete graph, every pair of distinct vertices is connected by a unique edge.

连通图 (Connected Graph)

连通图中的任意两点之间至少存在一条路径。

In a connected graph, there is at least one path between any two vertices.

权重图 (Weighted Graph)

权重图的每条边都有一个权重（或代价）与之关联。

In a weighted graph, each edge has a weight (or cost) associated with it.

表示法 (Representation)

邻接矩阵 (Adjacency Matrix)

邻接矩阵是一个 $n \times n$ 的矩阵 $A$ ，其中 $n$ 是顶点的数量。如果顶点 $i$ 和顶点 $j$ 之间有边，则 $A_{ij}$ 为边的权重（无权图中为 1），否则为 0。

The adjacency matrix is an $n \times n$ matrix $A$ , where $n$ is the number of vertices. If there is an edge between vertex $i$ and vertex $j$ , then $A_{ij}$ is the weight of the edge (1 in an unweighted graph), otherwise it is 0.

邻接表 (Adjacency List)

邻接表为每个顶点存储一个列表，列表中包含该顶点相邻的所有顶点及边的权重（如果有的话）。

The adjacency list stores a list for each vertex, containing all adjacent vertices and the weights of the edges (if any).

代码示例 (Code Example)

以下是用 Python 表示图的一些代码示例：

Here are some code examples for representing graphs in Python:

# 使用邻接矩阵表示无向图
# Representing an undirected graph using an adjacency matrix
adj_matrix = [
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0]
]
 
# 使用邻接表表示无向图
# Representing an undirected graph using an adjacency list
adj_list = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2]
}

基本概念 (Basic Concepts)

路径 (Path)

路径是由一系列不同的顶点组成的序列，其中每对连续顶点之间都有边连接。

A path is a sequence of vertices where each pair of consecutive vertices is connected by an edge.

环 (Cycle)

环是起点和终点相同的路径。

A cycle is a path that starts and ends at the same vertex.

欧拉路径和欧拉回路 (Eulerian Path and Circuit)

欧拉路径是一条通过每条边且仅通过一次的路径；欧拉回路是一条通过每条边且仅通过一次并且起点和终点相同的路径。

An Eulerian path is a path that visits every edge exactly once; an Eulerian circuit is an Eulerian path that starts and ends at the same vertex.

哈密顿路径和哈密顿回路 (Hamiltonian Path and Circuit)

哈密顿路径是一条通过每个顶点且仅通过一次的路径；哈密顿回路是一条通过每个顶点且仅通过一次并且起点和终点相同的路径。

A Hamiltonian path is a path that visits every vertex exactly once; a Hamiltonian circuit is a Hamiltonian path that starts and ends at the same vertex.

重要算法 (Important Algorithms)

深度优先搜索 (Depth-First Search, DFS)

深度优先搜索是一种用于遍历或搜索图的算法。它沿着每个分支尽可能深地搜索，直到达到底端，然后回溯并继续搜索下一条分支。

Depth-First Search (DFS) is an algorithm for traversing or searching graph structures. It starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

def dfs(graph, start):
    visited = set()
    stack = [start]
 
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(set(graph[vertex]) - visited)
    return visited

广度优先搜索 (Breadth-First Search, BFS)

广度优先搜索是一种用于遍历或搜索图的算法。它从根节点开始，首先访问所有相邻节点，然后对每个相邻节点再访问它们的相邻节点，依此类推。

Breadth-First Search (BFS) is an algorithm for traversing or searching graph structures. It starts at the root node and explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

from collections import deque
 
def bfs(graph, start):
    visited = set()
    queue = deque([start])
 
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)
    return visited

最短路径算法 (Shortest Path Algorithms)

Dijkstra 算法

Dijkstra 算法用于查找图中从单个源顶点到所有其他顶点的最短路径，适用于非负权重的图。

Dijkstra’s algorithm finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative weights.

import heapq
 
def dijkstra(graph, start):
    pq = []
    heapq.heappush(pq, (0, start))
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
 
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
 
        if current_distance > distances[current_vertex]:
            continue
 
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
 
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
 
    return distances

最小生成树算法 (Minimum Spanning Tree Algorithms)

Kruskal 算法

Kruskal 算法用于查找图的最小生成树，适用于边集表示的图。

Kruskal’s algorithm finds the minimum spanning tree for a graph, which may represent, for example, a network of nodes.

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size
 
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]
 
    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
 
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1
 
def kruskal(graph):
    edges = sorted(graph['edges'], key=lambda x: x[2])
   
 
 uf = UnionFind(graph['vertices'])
    mst = []
 
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
 
    return mst

总结 (Summary)

图论是计算机科学和数学中的一个重要领域，涉及到许多基本概念和算法。这些概念和算法不仅在理论研究中具有重要意义，而且在实际应用中也有广泛的应用，如网络设计、路径规划和数据分析等。

Graph theory is a fundamental area in computer science and mathematics, encompassing many basic concepts and algorithms. These concepts and algorithms are crucial not only in theoretical research but also in practical applications such as network design, route planning, and data analysis.

Zephyr's Notes on ISCS & CBMS, UTokyo

Explorer