2つのグラフが同型である場合、それらの行列式は等しくなりますか？
10個の頂点グラフG1とG2
アルゴリズムとその応用を用いたグラフ理論の第2章の演習を解いています。これまでのところ、同型写像の場合は、すべてのエッジを記述してパターンを見つけようとします。これは、小さなグラフの場合は十分です。これらの210頂点30エッジのグラフには、もっとスケーラブルなものが必要だと思います。両方のグラフを統一された構造に「変換」しようとしましたが、もちろん、1つの頂点の名前を変更すると、グラフの外観も異なります。パターンを見つけようとして隣接行列を作成しましたが、これら2つが同型ではないのではないかと疑う列があります。ただし、頂点の名前をいつでも変更して、列をもう少し似たものにすることができます。とにかく、A = PBP（t）の場合、2つのグラフ（A、B）は同型であることがわかりました。ここで、Pは置換行列であり、P（t）はその転置です。
det（P）= 1または-1 = det（P（t））およびdet（AB）= det（A）* det（B）であるため、AとBが同型である場合：
det（A）= 1 | -1 * det（B）* 1 | -1 det（A）= det（B）
2つの隣接行列が同じ行列式を持ち、同型ではない可能性がありますか？または、行列式の平等は同型写像の十分条件（そしてはるかにスケーラブル）ですか？
ベスト、
セルジオ
回答
同型グラフの隣接行列が同じ行列式を持つことは確かに真実です。確かに、$A = PBP^T$ 置換行列の場合 $P$、その後 $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ 実際、私たちはもっと言うことができます：なぜなら $A$ そして $B$は類似した行列であり、同じ固有値を持ちます。2つの行列が同じ固有値を持っている場合、それらは自動的に同じ行列式を持っていることに注意してください。
逆は成り立たない：if $A,B$ は2つのグラフの隣接行列であり、 $\det(A) = \det(B)$、グラフが同型であるとは限りません。実際、たとえ$A$ そして $B$固有値が同じである場合、グラフが同型であるとは限りません。この現象の例は、グラフの等スペクトル（または共スペクトル）ペアと呼ばれます。
長さ2（2つのエッジ、3つの頂点）のパスのdet 0があり、3つの頂点がありエッジのないグラフにもdet0があります。