对图同构证明的一个想法
首先将图写成邻接矩阵形式，然后有，
若两个图的表示矩阵的秩一致，那么他们同构，如果他们的秩不一致，那么他们不同构。
说明：
首先，两个图同构的充要条件是对于其顶点集合而言，其两个边集形成一个置换。对应在邻接矩阵上，即两个矩阵最多相差有限次的行（列）变换。这样，两个图同构的充要条件变为，他们的邻接矩阵最多相差有限次的行（列）变换。
然而，在线代中已有说明，即这样的行（列）变换，即初等变换是不改变方程根的，并且，
图论中的变换不可能包括初等变换中的另外两种变换，并且线代中也不存在不能表示成初等变换的合成的变换，且使方程的根不变，从而这种行列变换本身就是这里的方程的根不变的充要条件，因此我们有，
两个图同构的充要条件变为，矩阵代表的线性方程组的根不变。
但图的邻接矩阵的元素只有0，1两个值，换句话说，它所代表的线性方程组的根只有存在或者不存在两种情形，这样，显然用秩的概念就能完全解决这个问题。
然后自然就有以上结论。
放在这里，希望大家多多指正。
谢谢！！
| 论坛嘉宾: 萍踪浪迹 gauge 季候风 |
|
ET  发表文章数: 15
|
 THE DAY WITHOUT SCIENCE,
|
||
|
gauge  发表文章数: 596
|
1个字：错。
证明要一步一步地写下来才行。
|
||
|
ni_o  发表文章数: 33
|
首先，两个图同构的充要条件是对于其顶点集合而言，其两个边集形成一个置换。对应在邻接矩阵上，即两个矩阵最多相差有限次的行（列）变换。这样，两个图同构的充要条件变为，他们的邻接矩阵最多相差有限次的行（列）变换。
------------------------ 想法很好。但两个图同构的充要条件是一者的邻接矩阵可以通过换法的合同变换化为另一者的邻接矩阵。而不是“两个矩阵最多相差有限次的行（列）变换。”那么问题等价于：设A，B为对称的0—1矩阵，且A，B主对角元均为0，A中数字“1”的个数等于B中数字“1”的个数。则A可以通过换法的合同变换化为B的充要条件为rank(A)=rank(B).（感觉上不对，但反例未找到。对5阶以下的矩阵我验证过命题正确。） PS: 1，换法的合同变换是指对方阵做行交换的同时要做相应列的交换，如（2，3）A是指对A先做交换2，3行的变换，之后在对A做交换2，3列的变换。 2，设G为简单图，V（G）={v1,v2,...,vn},G在这中标号下的邻接矩阵记为A。设vp1,vp2,...,vpn为v1,v2,...,vn的一个置换，G在这中标号下的邻接矩阵记为B。则A可以通过换法的合同变换化为B。 命运取决于选择。
|
||
|
ni_o 发表文章数: 33
|
然而反例已找到：Ｋ３并Ｋ３的邻接矩阵与Ｃ６的邻接矩阵秩均为６，然而明显地Ｋ３并Ｋ３与Ｃ６不同构．
哎．．．这个问题的确是难难难的哦．．． 命运取决于选择。
|
||
|
kanex  发表文章数: 447
|
那么我问一个问题：在图的spectrum中看不出来的信息，具体包括哪些？
like a great ring of pure and endless light
|
||
|
ni_o 发表文章数: 33
|
国内对图的spectrum半径估计研究的较多。然而图的spectrum只是图的邻接矩阵的特征值及重数的序列，它提供的信息是可怜的少。通常地spectrum用于界定图的其他的参数，如χ，α，β，γ，ξ，κ，η，g其它方面的应用我知道的很少。根据我个人的认识从图的spectrum看不出图的连通性，更看不出图的Hamilton性，看不出图的独立集和团，更看不出图的完美性，看不出图的极大覆盖集和匹配，看不出图的圈空间的诸多性质，看不出图的。。。。
命运取决于选择。
|
||
|
kanex 发表文章数: 447
|
i mean the spectrum of adj. maxtrix & laplacian matrix.
like a great ring of pure and endless light
|
||
|
kanex 发表文章数: 447
|
And, how much information are there in the Ihara zeta function?
like a great ring of pure and endless light
|
||
|
ni_o 发表文章数: 33
|
kanex:
您说的问题是纯粹图论的吗？否则的话我无能为力了． 命运取决于选择。
|
||
|
kanex 发表文章数: 447
|
my questions are all spectral graph theory.
like a great ring of pure and endless light
|
||
|
ni_o 发表文章数: 33
|
恕我无知请问 laplacian matrix（拉普拉斯矩阵？）是什么意思？
命运取决于选择。
|
Re: 对图同构证明的一个想法