第10章 图的基本概念
10.1 图
1.图G的结点数称为G的阶，用n表示，G的边数用m表示。
2.将多重图和伪图中的平行边代之以一条边，去掉环，就可以得到一个简单图。
3.图G中结点u的度d(u)是G中与u关联的边的条数，每个环在计算度时算作两条边。最大的点度记为，最小的点度记为
。
4.握手定理：对于任何 (n, m) 图G = (V, E)有
5.在任何图中，奇数度的结点数必定是偶数。
6.在有向图G中，结点u的入度是与u关联的入边的数目，出度
是u的出边的数目。
7.对于任何(n, m) 有向图G=(G, V),
且
8.度为0的结点称为孤立结点。只由孤立结点构成的图G = (V,Ø) 称为零图。只由一个孤立结点构成的图称为平凡图。
9.各点度相等的图称为正则图。
10.任何两个结点皆相互邻接的简单图称为完全图。
11.每对结点u和v之间恰有一条边(u, v) 或 (v,u) 连接的简单有向图称为竞赛图。
12.二部图G = (G, V) 的结点集可以划分为两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中。如果X中每个结点和Y中的全部结点都邻接，则称G为完全二部图，记为Kn1,n2 。
13.设H = （V1, E1) 和 G = (V2 , E2) 是两个图，若满足V1V2且E1
E2，则称H是G的子图。特别地，当V1=V2时，称H是G地生成子图；当E1
E2或V1
V2时，称H是G的真子图；当V1=V2且E1=E2或E1=Ø时，称H是G的平凡子图。
14.从G中删除结点u及其关联的全部边后得到的图称为G的删点子图，记为 G-u。
15.从G中删除边e后得到的图称为G的删边子图，记为 G-e。
16.点诱导子图
17.边诱导子图
18.补图
19.同构。结点存在映射关系，边通过函数关系也可以一一映射。
20.带权图
10.2 通路与回路
1.道路 P=v1e1v2e2……ekvk
2.起点 终点 内部节点 长度= k
3.起点终点不同：开道路；闭道路
4.P的边互不相同称为简单道路。闭的简单道路称为回路。
5.P中结点互不相同称为基本道路。起点终点相同的基本道路称为圈。奇圈，偶圈。
10.3 图的连通性
1.连通性；有向连通，可达。
2.只有一个支的图称为连通图，支数大于1的图称为非连通图。
3.u和v的最短道路之长称为距离，记为d(u , v)。
4.删去后使连通图的支大于1的结点集合称为点割集；删去后仍为1的结点集合称为基本割集。割点
5.同理 边割集
6.图G点连通度是使由 G 产生一个非连通子图，或一个结点的子图需要删去的最少的结点数目。对于完全图
7.边连通度
8.对于任何图G，
9.对于简单有向图，有单向连通图，强连通图（任何两个结点之间都是相互可达），弱连通图（G的基图是连通的）
10.简单有向图的极大强连通子图称为G的强分图，极大单向连通子图称为单向分图，极大弱连通子图称为弱分图。（极大就是指结点不能再多了）
11.简单有向图中，每个结点位于且仅位于一个强分图中。
10.4 图的矩阵表示
1.邻接矩阵
2. 中的元素表示长度为k的有向道路的数目。
3.可达性矩阵（利用Warshall算法）
4.关联矩阵（边-结点）
网友评论