图论中的习题学习散记

**** 博客说图论大多侧重算法，很少涉及理论方面。作为一个优秀的图论学习者，习题的训练需要足够有效; 做题也是想进一步深入了解图论的捷径. 所以我在阅读论文同时花一些散的时间分析图论习题和经典的定理。以期达到加深功底和发散思维的效果.
本次习题来源我放在资源下载里面。

先做一道不等式题为引子：

注： $\alpha$α 是图的顶点独立数。即最大独立集的个数。
分析： 这道题我们充分利用$K_3$K3​ free 的性质，也就是不含三角形。那么图的任意顶点的邻点之间均不会连边，那么他们将构成了独立集。 考虑最大度的顶点，则得到一个大于等于最大度的独立集。那么依据独立数的定义可以得到我们的结论。

下面开始处理今天的习题。我们主要是处理West 教材的习题。West 本身是具有答案的，但是答案相当随意。我争取认真分析一遍。
容易题：

分析：完全二部图什么时候是完全图？ $k_{m,n}$km,n​ 只要有一部大于2,
那么必存在不相邻的两点！与完全图不符合。故 $m\leq1,n\leq1$m≤1,n≤1,情况顿时少了很多，容易得出我们想要的结果。

分析： 这题难度不大，不过前面说写出所有的邻接矩阵。意味着什么呢？意味着顶点顺序不同，矩阵不同，但是这些矩阵是通过行列互换这种初等变换得到的。这些图也是同构的。邻接矩阵索引行列都是顶点，关联矩阵行由顶点索引，列由边索引，当然这可以互换。

分析： 矩形分块的办法去表示完全二部图。这个在图谱理论涉及较多。分块处理往往更容易得到一些有效结论。

分析： 考察图同构的定义： 我们说的详细一点：
不妨设有一个同构映射 $f:V(G)→V(H)$f:V(G)→V(H). 因为 $G$G 和$H$H同构，则对于任意 $a,b∈G$a,b∈G，$ab∈E(G)$ab∈E(G) 当属且仅当 $f(a)f(b)∈E(H)$f(a)f(b)∈E(H)
因此 $ab$ab 不属于 $E(G)$E(G) 当且仅当 $f(a)f(b)$f(a)f(b) 不属于 $E(H)$E(H) .即 $ab$ab 属于 $E(G)$E(G) 补当且仅当 $f(a)f(b)$f(a)f(b) 属于 $E(H)$E(H) 补.即 $f$f 是 $G$G 补到 $H$H 补的同构.