编辑“︁随机化图算法”︁（章节）

== 经典算法示例 ==  

=== 1. 随机化最小割（Karger's Algorithm） ===  
用于求解无向图的最小割问题，通过随机收缩边来减少图的规模。  

==== 算法步骤 ====  
1. 随机选择一条边。  
2. 收缩该边，合并其两个端点。  
3. 重复直到只剩两个顶点，剩余的边即为候选最小割。  

==== 代码示例 ====  
<syntaxhighlight lang="python">  
import random  

def karger_min_cut(graph):  
    while len(graph) > 2:  
        u = random.choice(list(graph.keys()))  
        v = random.choice(graph[u])  
        # 合并节点u和v  
        for node in graph[v]:  
            if node != u:  
                graph[u].append(node)  
                graph[node].append(u)  
            graph[node].remove(v)  
        del graph[v]  
    # 返回剩余边数  
    return len(graph[list(graph.keys())[0]])  

# 示例输入：邻接表表示的图  
graph = {  
    'A': ['B', 'C'],  
    'B': ['A', 'C', 'D'],  
    'C': ['A', 'B', 'D'],  
    'D': ['B', 'C']  
}  
print("候选最小割边数:", karger_min_cut(graph))  
</syntaxhighlight>  

==== 输出示例 ====  
<pre>  
候选最小割边数: 2  
</pre>  

=== 2. 随机游走（PageRank） ===  
Google的网页排名算法基于随机游走，将网页视为图中的节点，链接视为边。  

<mermaid>  
graph LR  
    A --> B  
    A --> C  
    B --> C  
    C --> A  
    D --> B  
</mermaid>  

==== 数学描述 ====  
PageRank值 <math>PR(v)</math> 的计算公式：  
<math>  
PR(v) = \frac{1-d}{N} + d \sum_{u \in M(v)} \frac{PR(u)}{L(u)}  
</math>  
其中：  
* <math>N</math> 是总网页数，  
* <math>d</math> 是阻尼系数（通常0.85），  
* <math>L(u)</math> 是网页 <math>u</math> 的出链数。