离散数学之图论
1.基本概念
图由结点和连接两个结点之间的连线组成。连线的长度和结点的位置是无关紧要的。
几乎每一门可以想象的学科里都有问题可以用图模型来解决。例如：可以用图来表示生态环境里不同物种的竞争；可以用图来表示在组织里谁影响谁，以及用图来表示比赛结果；旅行商问题；地图着色问题等。
一个简单的例子：大城市之间的高速公路系统建模：
可以把各个城市看成结点，城市之间存在高速公路，则认
为这两个城市之间有连线，这样可以构成一个简单的图
表示方法有：
2、图的表示法
三元组表示G=<V(G),E(G), φG>：V(G)-非空的结点集合；E(G)-边集合；φG-边集合E到结点无序偶（有序偶）集合上的函数。
3、图的一些基本概念
（1）无向边：与结点无序偶关联的边，用 (a,b)表示
有向边：与结点有序偶关联的边，用<a,b>表示；表明是从a到b的有向边
孤立结点：无邻接点的结点
（2）无向图：图中每一边都为无向边
有向图：图中每一边都为有向边
混合图：图中既有有向边，也有无向边
平凡图：仅由一个孤立结点构成的图
第一个是无向图，第二个是有向图，最后一个是混合图
（3）邻接点：由一条有向边或一条无向边相关联的两结点
邻接边：关联于同一结点的两条边
平行边：连接于同一对结点的多条边
自回路（环）：关联于同一结点的一条边（既可看作是有向边，也可作无向边）
（4）结点的度数
图G=<V，E〉中，与结点v关联的边数为度数，记为deg(v)。
一个环的度数为2。
（4）结点的度数
在有向图中，定义入度、出度的概念
入度： 射入一个结点的边的条数，记为deg-(v)；
出度： 由一个结点射出的边的条数，记为deg+(v)；
入度与出度之和为该结点的度数：deg(v)= deg+(v)+ deg-(v)
定理**????* 度数为奇数的结点必定是偶数个
定理： 有向图中所有结点的入度之和等于所有结点的出度之和
（5）多重图：含有平行边的图
简单图：不含有平行边和环的图
完全图：每一对结点之间都有边关联的简单图
有向完全图：完全图中每条边任意确定一个方向所得的图
G与G’同构的充要条件是：
a、结点一一对应
b、边一一对应
c、保持关联关系
2.路与回路
1、路的基本概念**：**
路： 图G=<V, E>，设 v0, v1, …,vn∊V, e1, e2, …, en∊E, 其中ei是关联于结点vi-1, vi的边，交替序列设** v0 e1 v1 e2 … en vn称为联结v0到vn的路；v0，vn分别称为路的起点和终点
定理： G=<V, E>具有n个结点，如果从结点vj到结点vk存在一条路**，**则此两结点间必存在一条边不多于n-1的路
2**、无向图的连通性：**
在无向图G中，若结点u和v之间存在一条路，则称u和v是连通的。
结点之间的连通性是结点集上的等价关系**。**
证明：自反性：v和v是连通的
对称性2、无向图的连通性：
传递性：u和v连通，v和w连通，则u和w中也存在路，是连通的
距离：u可达v，u和v间的最短路的长度，记为d<u,v>若u到v不可达，通常记d<u,v>=∞
图的直径：D=maxd<u,v>
（2）强分图：具有强连通性质的极大子图
单侧分图**：**具有单侧连通性质的极大子图
弱分图**：**具有弱连通性质的极大子图
3.图的矩阵表示
2**、置换等价：**
把n阶方阵A的列和行分别作置换，得到新的方阵A’，称A’与A置换等价。置换等价是n阶布尔矩阵集合上的等价关系
对于有向图，按照结点的不同次序写出的邻接矩阵是置换等价的。因此，可选取任意一个邻接矩阵作为该图的矩阵表示，通过此邻接矩阵来考虑图的一些特性
计算方法可以使用warshall算法，最多乘上几次就行了（节点个数）
一组路（结点边结点的交替序列，简单图中可简化为结点序列）的概念：路、回路、圈、通路、迹
无向图中：
结点之间的连通性（u和v之间有路）、连通分支、连通图；点割集、割点、点连通度k(G)；边割集、割边、边连通度λ(G)；k(G)≤ λ(G) ≤ δ(G)
有向图中：
结点之间的可达性（u到v有路）、距离（u到v所有路中的最短边数）、图的直径；强连通图、单侧连通图、弱连通图；强分图、单侧分图、弱分图
相关性质：
1）M(G)中每列中有且仅有两个1，对应每边关联的两个结点
2）每行中元素的和为对应结点的度数
3）元素全为0的行对应结点为孤立结点
4）平行边对应的列相同
5）结点/边编序不同，对应完全关联矩阵只有行序/列序的差别
定理： G为连通图，有r个结点，则其完全关联矩阵M(G)的秩为r-1，即rank M(G)=r-1
推论： G有r个结点，w个极大连通子图，则图G的完全关联矩阵的秩为r-w
4.欧拉图与汉米尔顿图
1、欧拉图
（1） 定义：给定无孤立结点图G，
欧拉路： 通过图中每边一次且仅一次的路
欧拉回路： 通过图中每边一次且仅一次的回路
半欧拉图：存在欧拉路的图
欧拉图： 具有欧拉回路的图
对于半欧拉图或者欧拉图，由于其经过每条边，必定会经过所有的点，因此必定是一个连通图，此外，关于图中的结点的度数，也有相关定理及推论
判断方法：
定理： 无向图G具有一条欧拉路**，**当且仅当G是连通的，且有零个或两个奇数度结点
推论：无向图G具有一条欧拉回路**，**当且仅当G是连通的，且所有结点的度数全为偶数
（3）一笔画问题：
1）从图G中某个结点出发，经过G中的每一边一次且仅一次到达另一个结点（半欧拉图）
2）从图G中某个结点出发，经过G中的每一边一次且仅一次回到该结点（欧拉图）
（4）G为有向图：
单向欧拉路**： **通过有向图G中每边一次且仅一次的单向路
单向欧拉回路： 通过有向图G中每边一次且仅一次的单向回路
定理：
有向图G具有一条单向欧拉回路，当且仅当G是连通的，且每个结点的入度等于出度
有向图G具有单向欧拉路，当且仅当G是连通的，且除两个结点外（一个结点的入度比出度大1，另一个结点的入度比出度小1），每个结点的入度等于出度
欧拉回路是边的遍历问题，而汉密尔顿回路则是点的遍历问题，即能否找到一条经过每个点一次且仅一次最终回到起点的回路。经典问题：十二面体问题
2、汉密尔顿图
（1）定义：给定图G**，**
汉密尔顿路： 经过图中每个结点恰好一次的路
汉密尔顿回路： 经过图中每个结点恰好一次的回路
半汉密尔顿图：具有汉密尔顿路的图
汉密尔顿图： 具有汉密尔顿回路的图
总结：即联通分支数目小于等于点割集个数。
（3）充分条件的判定**：**
1）定理： 简单图G具有n个结点，G中每一对结点度数之和大于等于n-1，则G中存在汉密尔顿路**。**
2、汉密尔顿图
（1）定义：给定图G**，**
汉密尔顿路： 经过图中每个结点恰好一次的路
汉密尔顿回路： 经过图中每个结点恰好一次的回路
半汉密尔顿图：具有汉密尔顿路的图
汉密尔顿图： 具有汉密尔顿回路的图
总结：即联通分支数目小于等于点割集个数。
（3）充分条件的判定**：**
1）定理： 简单图G具有n个结点，G中每一对结点度数之和大于等于n-1，则G中存在汉密尔顿路**。**
2）定理： 简单图G具有n个结点，如果G中每一对结点度数之和大于等于n，则G中存在一条汉密尔顿回路**。**