Quartz 4

图论

4 min read

图论

核心观点：图是描述对象间关系的数学模型，是网络分析和社交网络的理论基础。

📊 图的基本概念

图的定义

概念定义表示
图顶点和边的集合G=(V,E)
有向图边有方向<u,v>
无向图边无方向{u,v}
加权图边有权重w(u,v)

图的表示

graph TB
    subgraph 图的表示
        A1["邻接矩阵<br/>A[i,j] = 1 若相邻"]
        A2["邻接表<br/>每个顶点的邻居"]
        A3["边列表<br/>所有边的集合"]
    end    
    A1 & A2 & A3
    
    style A1 fill:#ffebee

📈 特殊图

特殊图类型

类型定义性质
完全图所有顶点相连边数=n(n-1)/2
二分图顶点分为两组可2-染色
平面图可平面嵌入边不相交
树连通无环边数=n-1

树的性质

graph TB
    subgraph 树性质
        A1["连通<br/>任意两点可达"]
        A2["无环<br/>无回路"]
        A3["唯一路径<br/>两点间唯一"]
        A4["边数<br/>|E|=|V|-1"]
    end    
    A1 & A2 & A3 & A4
    
    style A1 fill:#ffebee

🔢 图的性质

度与路径

概念定义意义
度连接边数节点重要性
入度指向的边数有向图
出度发出的边数有向图
路径边的序列连通性

连通性

graph TB
    subgraph 连通性
        A1["连通图<br/>任意两点可达"]
        A2["强连通<br/>有向图双向可达"]
        A3["弱连通<br/>忽略方向连通"]
        A4["连通分量<br/>最大连通子图"]
    end    
    A1 & A2 & A3 & A4
    
    style A1 fill:#ffebee

🎯 图算法

遍历算法

算法原理应用
BFS广度优先最短路径
DFS深度优先拓扑排序

最短路径

算法复杂度特点
DijkstraO(V²)非负权
Bellman-FordO(VE)负权边
FloydO(V³)全源最短路径

最小生成树

graph TB
    subgraph 最小生成树
        A1["Kruskal<br/>边排序+并查集"]
        A2["Prim<br/>顶点扩展"]
    end    
    A1 & A2
    
    style A1 fill:#ffebee

🤖 机器学习应用

图神经网络

graph TB
    subgraph 图神经网络
        A1["图卷积<br/>邻居聚合"]
        A2["图注意力<br/>注意力加权"]
        A3["图池化<br/>层次化"]
    end    
    A1 & A2 & A3
    
    style A1 fill:#ffebee

社交网络分析

应用方法意义
社区发现图分割群组识别
中心性分析度/介数/接近中心性影响力排序
链接预测图特征关系预测

🎯 核心结论

图论核心概念

  1. 图：对象和关系的数学模型
  2. 度：节点连接数
  3. 路径：边的序列
  4. 连通性：可达性
  5. 算法：遍历、最短路径、最小生成树

学习路径

图论学习四步骤：
1. 基本概念：顶点、边、度
2. 特殊图：树、完全图、二分图
3. 图算法：遍历、最短路径
4. 应用：图神经网络、社交网络

📚 参考文献

  1. 《图论及其算法》- Bondy
  2. 《图论导引》- West
  3. 《离散数学》- 屈婉玲
  4. 《图神经网络》
  5. 《社交网络分析》
  6. 《网络科学》
  7. 《图论》- 王树禾
  8. 《算法导论》- 图算法部分

Graph View

Backlinks