阿狗工具

“相遇就是缘分吧。”

第一次学习图论（graph theory) ，当然是在离散数学这门课中，还记得当时教我们的数学老师很年轻漂亮。总是怀念以前的日子。

1. 图

图由节点和边组成。
图可以表示：交通、社交网络、互联网、工作安排、脑区活动、程序状态执行（如自动机、编译器）。

2. 图的分类

• 无向图（Undirected Graph) ：人际关系
  有向图（Directed Graph) ：自动机（边表示一个事件转移到另一个事件，这种转移是有方向的）
  无向图可以看作一种特殊的有向图。
• 无权图（Unweighted Graph)
  有权图（Weighted Graph) ：交通运输图

3. 图的连通性

4. 简单图（Simple Graph)

简单图是没有自环边和平行边的图。
自环边(self-loop)
平行边(parallel edges)
平行边和自环边会加大问题的复杂性。