离散数学 --- 图论基础 --- 图的同构，通路与回路，可达性与最短通路

同一个图（这里的图是抽象的数学定义）可以有不同的图形表示方法

1.重数：两点之间的平行边的个数

1.得到 n! 的过程，一个图中的一个结点在另一个图中对应的结点有n种可能（黄框中定义的图来讨论），这个对应好后下一个结点有 n - 1 种可能，再下一个有n-2种，直到最后一个为1，所有可能的结果就等于 n * (n - 1) *(n - 2)*....*1 = n! 

2.虽然说找对应结点很困难，但不是没有规律可循的。比如1.两个相互对应的结点的度数要相同；2.两个相互对应的结点的邻接点的度数也要相同（和结点A具有边关系的结点都是结点AA的邻接点）

1.如果两个图之间不满足上面这三个条件中的任意一个，则这两个图不同构，但是即使满足了这三个条件也不一定同构

第二部分 --- 通路与回路

 确定了边之后自然就能跟确定边两端的端点了

1.注意这里的A的m次幂表示的是通过矩阵乘法一步步乘过来的新矩阵，然后(aij（m）)表示的是计算完A的m次幂后得到的新矩阵的第 i 行 j 列的元素

 上面那个是无向图，下面这个是有向图

1.（bij）n*n表示的是矩阵Bm的第 i 行 j 列的元素

2.矩阵之间的加法只有在两个矩阵的行数和列数都相同的时候才能够进行，然后相加的方式是对应元素相加后得到新矩阵对应位置的元素值

第三部分 --- 可达性

在实际情况中，我们往往不关系两点之间有多少通路，我们一般只关心两点：

1.两点之间有没有通路？ --- 可达性

2.两点之间如果有通路的话，最短通路是那条？--- 最短通路                  

1.上面这种穷举法只是举个例子，实际上我们判断是否可达采用的是下面这个原理

1.如果从长度1到长度为 n-1（n为结点数）都找不到一条通路的话，则这两点之间是不可达，如果找到了，那这两点之间就是可达的

2.根据下面的证明我们可以得知，两点之间任意一条长度大于 n - 1 的通路（如果存在的话）都等价于一条长度小于等于 n - 1 的通路

（由结点数限制可证：长度为K，代表你有K条边，这就有K+1个结点，如果K+1个结点大于n个结点（总结点数），则证明这条通路上必定会出现重复的结点，此时的通路等价于将重复的结点之间的路径省掉的新通路，这样不停的省下去，最终一定能使得K小于等于n-1）

所以可知如果我们没有在 长度 <= n-1的范围内找到通路的话，则就再也找不到了

回路的判断同理

（不过有一个区别，就是回路的边数等于回路的结点数，通路的边数等于通路的结点数 减 1）

1.对于无向图而言，i 结点能够到达 j 结点，则j结点一定能够到达 i 结点，反应到可达性矩阵就是：

Pij = Pji

2.对于有向图则不是如此，如果 i 结点能作为始点，j 结点能作为终点形成通路，并不意味着 j 结点作为始点 ，i 结点作为终点能够形成通路：

反应到可达性矩阵就是： Pij 不一定等于 Pji

 由于可达性矩阵只需要知道通还是不通，所以我们可以对可达性矩阵的求解进行简化：

1.将原本的A的1次幂到A的n次幂的矩阵乘法计算转变为矩阵的布尔乘法（n为结点数）计算

2.将得到的次幂从1到n的布尔矩阵取并集，取完并集后得到的新的矩阵就是我们的可达性矩阵

原本的计算方法：

1.计算矩阵A从1次幂到n次幂（n为结点数）的矩阵

2.将得到的所有矩阵求和得到新矩阵B

3.如果B矩阵的 Bij 元素不等于0，则可达性矩阵中对应位置的元素的值为1，如果等于0，则对应位置的元素也为0

第四部分 --- 最短通路

1.上面的最后一点为什么有向图不行呢？ --- 这是因为定义中只给定了 从 i 到 j 结点是通路，并没有说从 j 到 i 结点是不是通路（对于无向图而言是的），既然连 j 到 i 结点是不是通路都不知道，自然也就没有对应的短程线了，连短程线都没有的话哪来的相等性质呢

2.规定任何的结点自身到自身的距离为0