形式陈述

无向图是二元组 $G=(V,E)$$G=(V,E)$，其中 $V$$V$ 是顶点集合，$E\subseteq\{\{u,v\}:u,v\in V, u\ne v\}$$E\subseteq \{\{u,v\}:u,v\in V,u\ne v\}$ 是边集合。允许方向、重边或自环时得到相应的图变体。

直觉

图只保留“对象之间是否连接”，舍弃对象的内部细节，因此能统一表示网络、依赖和状态转换。

例子与边界

社交网络可把用户作为顶点、好友关系作为边。简单无向图不含自环和重边；有向图中的边是有序对，不能直接套用无向图结论。

推论与应用

路径、连通性、树、匹配、网络流和图着色都建立在图的定义上。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., §1.1.
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Chapter 1.