XJTUSE-离散数学-图论

概述

图的定义

几个定义，不赘述

多重图：有平行边存在

简单图：无平行边 + 无自环

子图 and 补图

完全图的概念

结点的度

入度，出度

奇结点、偶结点

定理：对于无向图，奇结点的个数为偶数

图的同构

必要条件：

1. 结点个数相等
2. 边数相等
3. 度数相同的结点个数相等

路与圈

简单路：无重复边的路；

简单圈：无重复边的圈；

初级路：无重复点的路；

初级圈：无重复点的圈；

可达性

存在一条从u到v的路，则称u可达v

连通性

无向图，任意两个结点间可达，则图G是连通的。

极大连通子图：连通支

1. 强连通：任意两点可达
2. 单向连通：任意两点，至少有一个结点可达另一个结点。
3. 弱连通：去掉边方向后，是连通的。

图的矩阵表示

邻接矩阵

1表示连接，0表示不连接

矩阵相乘，表示为从i到j长度为m的路有几条。

可达矩阵

改为布尔运算即可

可达矩阵即为R

可达矩阵与连通性的关系

1. 强连通：R全为1
2. 单向连通：除对角线，全为1
3. 弱连通：确定的R全为1
4. 有圈：R对角线上有1

带权图的最短路径

太经典的问题了，Dij算法。

Euler图

Euler路：每条边一次且仅一次的路；

Euler圈：每条边一次且仅一次的圈；

Euler图：G中有Euler圈。

1. G为无向连通图，其Euler图的充要条件为每个结点均为偶节点。
2. G为无向连通图，具有Euler路的充要条件为恰有两个奇结点，其余结点均为偶节点。
3. 若为有向连通图，其Euler图的充要条件为每个结点的入度等于出度。
4. 若为有向连通图，具有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叉树