有序对
- 无序对：
- 含有1个或2个元素的集合
，
- 有序对：
当且仅当 且 - 有序对的集合表示：
有向图和弧
：顶点集 ：弧集，一个有向对的集合。弧又称为有向边
- 一些术语
- 弧的尾
- 弧的头
- 环弧：头尾相同的弧
- 并行弧：具有相同头的相同尾的弧
- 简单有向图：无环弧，无并行弧
- 反向弧：简单有向图中头尾相反的弧
度和邻点
- 出度：
- 入度：
- 最小出度：
- 最小入度：
- 最大出度：
- 最大入度：
- 出邻点和入邻点
定理
对任何有向图
途径、迹、路、圈
- 有向途径
- 顶点和弧交替出现的序列
- 与弧的方向一致
- 有向迹：弧不重复出现
- 有向路：顶点不重复出现
- 有向圈：起点和终点相同
底图和定向
- 底图：有向图
无向图 - 定向：无向图
有向图 - 不唯一
- 竞赛图：完全图的定向
连通
- 弱连通：底图是连通的
- 强连通：任取顶点u和v，存在从u到v的有向路
- 强连通分支：极大强连通子图
- 强连通分支之间不存在公共顶点
- 强连通分支图不存在有向圈
强连通的充要条件
强连通定向
无向图
竞赛图
- 王
- 到其他任何顶点都有长度不超过2的有向路
- 不一定唯一
- 定理：竞赛图中出度最大的顶点一定是王
- 竞赛图中一个顶点
是唯一的王当且仅当 的出度是
