图
图的概念
图的定义
略
图的节点度
- 每个图中，结点度数的总和等于边数的两倍
- 每条边连接两个结点
- 每个图中，度数为奇数的结点必然是偶数个
- 在任何有向图中，入度=出度
图的同构
图的运算
- 子图：子图\(G_1\)中的结点和边为图\(G\)的子集
- 真子图：子图\(G_1\)中的结点和边为图\(G\)的真子集
- 生成子图：子图且拥有相同的结点
- 补图：无向简单图\(G\)相对于完全图\(K_n\)的补图
路与连通
路
\(u、v\)是任意图G中的结点
- \(u-v\)链：有限结点和边交替序列
- 链的长度：链中出现的边数
- 链的端点：链的内部点
- 开的链：两个端点不同的链
- 迹：边互不相同的链
- 路：内部点不互相同的链
- 回：两端点相同的迹（闭迹）
- 圈（回路）：闭路
- k回：长度为k的回
- 有向回：有向闭迹
- 有向圈：有向闭路
连通图
- 连通：无向图\(G\)中存在连接结点\(x\)和\(y\)的路
- 连通图：每一对结点之间都有路
- 可达
连通度
