图论(Graph Theory)是离散数学的分支。
============================
目录：
一、用图论解题
二、哥尼斯堡七桥问题
三、棋子布局问题
四、相邻矩阵
============================
一、用图论解题
1、10名学生中，有些学生是朋友，有些则不是。有没有可能没有两个学生拥有相同数量的朋友？
解答：不可能。
画一个10个顶点的图，两点相连则表示两点是朋友，每个顶点的度数就是该同学的朋友数量。因此度数的范围就是10个{0,1,..,9}。如果没有两个同学拥有相同数量的朋友，那么10个顶点的度数各不相同。但是不可能存在一个同学有9个朋友，一个同学0个朋友的情况。
2、7名学生中参加聚会，是否可能他们每个人都与另外3个人握手？
解答：不可能。
在任何图中，顶点的度数之和等于边的数量的两倍，所以是个偶数。那么奇数度的顶点数量也只能是偶数。7个同学看作7个顶点，握三次手就是每个顶点度数都是3这个奇数，那么奇数度的顶点个数就不是偶数而是7。这是不可能的。
============================
二、哥尼斯堡七桥问题
1、问题：从家里出发，七座桥每座桥恰通过一次，再回到家里，是否可能？
解答：Euler 对七桥问题的回答是‘否’：如果家在 D 点处，图 (b) 中 D 点处有三条桥，游人通过其中之一离家出游，不久又经另一桥回到家，因为要求每桥恰过一次，所以他不得不经第三条与 D 相连的桥离家远行，这时他已无法过桥回家了，因为三条与他家相通的桥他已都各走过一次；对于家在别处的情形道理是相似的。
结论：对于每个顶点的度数，如果不是所有顶点的度数为偶数，就不可能存在这样一条路径，使得每条边（桥）只经过一次并回到起点。
2、Euler图和Hamilton图
A walk is a sequence of vertices where each vertex is joined by an edge to the next vertex.The length of a walk is the number of steps , i.e. one less than the number of vertices listed in it.
A path is a walk consisting of distinct vertices.
============================
三、棋子布局问题
1、问题：能否在3x3的棋盘上将左图中的黑马和白马的位置交换到右图中的位置。马的行进路径为L形(马走日)。
解答:无法移动到右图的位置。
左图上a1, c3是黑色棋子，c1和a3是白色棋子。 然后把每个棋子可以到达的位置相连，就形成了一个环，如右图所示。无论c1和a3在环上如何移动，a1和c3都肯定在c1和a3中间。
原图链接：
https://math.stackexchange.com/questions/2232563/knight-shift-on-3%c3%973-chess-board
============================
四、相邻矩阵
邻接矩阵（Adjacency Matrix）是表示图的一种方式，其中每个元素表示两个顶点之间是否存在边。计算长度为N的路径数（walks），就是计算邻接矩阵的N次幂。
The(i j) entry in the kth power of the adjacency matrix gives the number of walks of length k between Vi and Vj.
