3、图的代数表示

1、图的邻接矩阵

邻接矩阵的性质



设$A$是某个图的邻接矩阵：
$$A_{ij}^2=\sum _{k=1}^n{A}_{ik}\times A_{kj}$$

• 邻接矩阵$A$中的元素都是用$0,1$来表示是否联通的，或者说，代表有没有方法从$i$走到$j$。那么，$A_{i,k}\times A_{kj}$就是表示从$i$走到$k$再走到$j$是否可行。可以发现，$A_2$就是取了一个$\Sigma$，其实就是统计用$2$步从$i$走到$j$的方法总数。
• 考虑累乘的效果，矩阵$A_m$所代表的意义就是从点与点之间走$m$步能够到达的方案总数。

2、图的关联矩阵

主要表示顶点跟边的连接情况

关联矩阵的性质

3、邻接谱

首先介绍一下特征多项式
1、线性代数基础
2、特征多项式







邻接谱的第一行是特征值，第二行是特征值对应的重数。

4、极图

1、$l$ 部图的概念与特征

• 很明显偶图就是2部图

2、完全$l$部图

• 完全$l$部图的总边数是各个部的边数两两相乘的和

3、$n$阶完全$l$几乎等部图

可以看到完全$l$几乎等部图一共有$l$个部，各个部的顶点数要么为$k$要么为$k+1$,即只相差$1$，几乎是相等的， 一共有$r$个顶点数为$k+1$的部，剩下的是顶点数为$k$的部。所以总顶点数为$（k+1）\ast r+k（l-r）=kl+r$如果每个部的顶点数都为$k$，那就不是完全$l$几乎等部图了，那就是完全$l$等部图。

• ps:若是要边数最多，则必定要是个完全l部图，完全 $l$ 几乎等部图意味着每个集合的元素个数接近相等，若每个集合里元素相等，则必定是完全 $l$ 几乎等部图。
• 全等符号代表同构。 一个$n$阶$l$部图，当它同构于完全$l$几乎等部图的时候，图中边数最多。
  
  托兰定理
  
• 如果有$G$中点到$H$中点的一一对应，且刚好$G$中的点的度小于等于对应的$H$中的点的度，则称$G$度弱于$H$，或$H$度优于$G$ 且$G$度弱于$H$，则$G$的边数一定小于等于$H$的边数
  
  

$ps$：先取出最大度的那个顶点$u$，再取出$u$的所有的邻接点的导出子图$G_1$。$G_1$要是含有$K_t$，则 $uV{G}_1$，就是$K_{t+1}$了。$V_2$应包含$u$点，则$G_{2}V{G}_1$的边数不少于$G$。




托兰定理的应用

5、交图与团图