离散数学 --- 图论基础 --- 子图和补图，握手定理

第一部分 --- 子图和补图

1.生成子图：点集合不变，边集合是原图的边集合的子集

2.导出子图：点集合是原图点集合的非空子集V，然后再在原图的边集合中找到两个端点均在点集合V中的边元素，并将这些边元素称成一个新的边集合，得到的这个边集合就是导出子图的边集合

（点集合V和得到的新的边集合组成的新图是原图G的子图，被称为V导出的原图的子图，简称为V的导出子图）

1.一个图G可以是自身的子图，生成子图和导出子图

2.判断一个原图的子图是否是导出子图的方法：将子图中缺少的点在原图中删去，然后再将由于删去了点后少掉了一个端点的线给去掉，如果子图和这个修改后的原图相等的话，则这个子图就是原图的导出子图，否则就不是

3.一个集合的子集可以是自身，一个图的真子集除了不能是自身外盒子集没区别

完全图就是图中的任意两个结点之间都有边相连

1.简单图是无环非多重图（无环：没有自己和自己连环状线，非多重图：两个结点间没有平行边（也可以没有边））

补充：简单图的邻接矩阵的主对角线（矩阵的左上角和右下角连线）上的元素都为0，因为简单图是没有结点自己和自己连接环状线的，所以根据定义对应位置上的元素为0

2.对于有序图而言两个端点之间没有平行边意味着一个方向上只有一条边 --- 比如A，B结点之间没有平行边意味着A指向B只有一条边，B指向A也只有一条边

3.对于无序图而言没有平行边意味着两个端点之间只有一条边

1.一个图的补图的点集合和原图一样，且边集合与原图的边集合并起来后等价于以原图的点集合为基础得到的完全图的边集合，也就是说完全图的边集合 - 原图的边集合 = 原图的补图的边集合（三个图的点集合都一样）

上面红色的就是补图

注意原图的补图的点集合是和原图的点集合一样的，在画补图的时候，千万不要漏画点了

---

第二部分 --- 握手定理

1.对于有向图而言边的端点分为两种：一种是始点，一种是终点。结点作为一次始点时算作一次端点，作为一次终点时算作一次端点

而对于无向图而言边的端点就是占据边的两个边缘的点（两个边缘可以同时别一个点占据（环状线），此时这个点做了两次端点） --- 结点作为占据一次边的边缘时算作一次端点

2.注意悬挂结点要求的是总度数为1，而不只是出度或入度单独为1

 

 

1.在无向图中，如果结点和结点自己以环状线相连的话，则这个结点同时占据了一个边的两个边缘，所以这个结点作为端点的次数要算两次

握手定理：图中所有结点的度数和等于图中所有边的边数的两倍

 

1. 偶数 + 奇数 = 奇数 ； 奇数 * 偶数 = 偶数  ； 偶数 * 偶数 = 偶数 ； 奇数 * 奇数 = 奇数 ---> 这些关系就是上面那个推论的基础

 注意是有向图中所有结点的出度和 = 所有结点的入度和 = 有向图的边数