说明
清华大学出版社 第六版
笔记内容 主要集中在 5、6、7章关于 树 图 的基本概念里
正文
5.1 无向图及有向图
无向图 是一个 二元组 其中 叫做顶点集， 称为边集
在图中 点 和 边 都可以说是相邻的
握手定理
每条边都有两个断点，所有顶点的的度数之和等于他们作为端点的次数之和，因此恰好等于边数的 2 倍
推论：
任何图中，度数为奇数的顶点个数是 偶数个
5.2 通路、回路和图的连通性
设 是一个有向图, 如果略去 中有向边方向后，所得无向图是连通图 则 叫做 弱连通图
若 中任意两个顶点至少一个可达另一个，则称 是 单向连通图
5. 4 最短路径、关键路径和着色
项目网络图 将 有向图 上的边带上权值，用来描述一个项目； 边表示活动，边的全是该活动的完成时间。
项目的开始和结束、活动的开始和结束称作事项。顶点用来表示事项
特点：
- 项目网络图只有一个始点 和 终点，始点的入度为 0，表示项目开始；终点的出度为 0，表示项目结束。
- 图上任意两点间只允许有一条边。如果一定要用两条 边连接同一个顶点，则需要引入虚活动，虚活动的完成时间是0。
- 图中没有回路
- 每条边始点的编号小于终点的编号
关键路径：