XJTUSE-离散数学-图论
概述
图的定义
几个定义，不赘述
多重图：有平行边存在
简单图：无平行边 + 无自环
子图 and 补图
完全图的概念
结点的度
入度，出度
奇结点、偶结点
定理：对于无向图，奇结点的个数为偶数
图的同构
必要条件：
- 结点个数相等- 边数相等- 度数相同的结点个数相等## 路与圈
简单路：无重复边的路；
简单圈：无重复边的圈；
初级路：无重复点的路；
初级圈：无重复点的圈；
可达性
存在一条从u到v的路，则称u可达v
连通性
无向图，任意两个结点间可达，则图G是连通的。
极大连通子图：连通支
- 强连通：任意两点可达- 单向连通：任意两点，至少有一个结点可达另一个结点。- 弱连通：去掉边方向后，是连通的。
图的矩阵表示
邻接矩阵
1表示连接，0表示不连接
矩阵相乘，
表示为从i到j长度为m的路有几条。
可达矩阵
改为布尔运算即可
可达矩阵即为R
可达矩阵与连通性的关系
- 强连通：R全为1- 单向连通：
除对角线，全为1- 弱连通：
确定的R全为1- 有圈：R对角线上有1## 带权图的最短路径
太经典的问题了，Dij算法。
Euler图
Euler路：每条边一次且仅一次的路；
Euler圈：每条边一次且仅一次的圈；
Euler图：G中有Euler圈。
- G为无向连通图，其Euler图的充要条件为每个结点均为偶节点。- G为无向连通图，具有Euler路的充要条件为恰有两个奇结点，其余结点均为偶节点。- 若为有向连通图，其Euler图的充要条件为每个结点的入度等于出度。- 若为有向连通图，具有Euler路的充要条件为恰有两个点，一个入度比出度大1，一个出度比入度大1。### 相关问题
笔画问题：找到k对奇结点。
中国邮路问题
Hamilton图
Hamilton路：每条点一次且仅一次的路；
Hamilton圈：每条点一次且仅一次的圈；
充要条件尚未找到！
必要条件
H图 的 必要条件为 ：
对于结点集合V的任一非空子集S，均有
，其中W(G)为连通支数。
充分条件
H路的充分条件为 ： G为n个结点的简单无向图，
H圈的充分条件为 ： G为n个结点的简单无向图，
竞赛图
完全图的定向图为竞赛图
竞赛图必有一条H-路
相关问题
货郎担问题
二分图
G = (V,E)是简单无向图，存在V的一个划分，使得G中的每一条边的端点一个在V1,一个在V2，V1,V2称为互补结点子集。
完全二分图
二分图的充要条件 ： G中每个圈的长度都是偶数.
匹配问题
最大匹配，完美匹配
杆：简单可以理解为边
非匹配点 ： 无杆连接的点
交错路径和增广路径
交错路径顾名思义，就是相邻两条边性质不同。这里取非匹配边-匹配边-非匹配边……的路径为交错路径；
增广路径则是从一个非匹配点出发，走交错路径到另一个非匹配点(保证了两边的边为非匹配边)
求最大匹配使用匈牙利算法(dfs)
平面图
存在图G的一种图示，使得任意两条边不相交，则称G为平面图。
Euler公式
区域的概念：一个极小的初级圈所包围的部分
无穷区域：最大初级圈之外的部分。
G为连通的(n,m)平面图，区域数为r，有n-m+r = 2
每个区域都是三条边及以上构成的，有不等式：
每个区域都是四条边及以上构成的，有不等式：
Kuratowsti定理
G中无一子图或无一经过Kuratowsti技术之后的子图与K3或者K5,5同构。
树
数据结构学过了，略
树的定义，生成树，最小生成树，二叉树，m叉树