Если два графа изоморфны, то будут ли их определители равными?

Aug 18 2020

Графы с 10 вершинами G1 и G2

Я решаю упражнения из главы 2 из Теории графов с алгоритмами и их приложениями. Пока что для изоморфизма я просто пишу все ребра и пытаюсь найти закономерности, чего для небольших графов достаточно. Для этих двух 10-вершинных и 30-реберных графов, думаю, мне нужно что-то более масштабируемое. Я пробовал «перевести» оба графика в единую структуру, но, конечно, если одна вершина изменит имя, граф также будет выглядеть по-другому. Я написал матрицу смежности, пытаясь найти шаблон, и есть столбец, который заставляет меня подозревать, что эти два могут быть не изоморфными. Тем не менее, я всегда мог изменить имя вершины, чтобы столбцы выглядели более похожими. В любом случае, я обнаружил, что два графа (A, B) изоморфны, если A = PBP (t), где 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)

Могут ли две матрицы смежности иметь один и тот же определитель и не быть изоморфными? или равенство в определителе является достаточным условием (и гораздо более масштабируемым) для изоморфизма?

Лучший,

Серджио

Ответы

9 BenGrossmann Aug 17 2020 at 22:47

Действительно, матрица смежности изоморфных графов будет иметь один и тот же определитель. Действительно, если$A = PBP^T$ для матрицы перестановок $P$, тогда $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ На самом деле можно сказать больше: потому что $A$ и $B$похожи матрицы, они будут иметь одинаковые собственные значения. Обратите внимание: если две матрицы имеют одинаковые собственные значения, они автоматически имеют одинаковый определитель.

Обратное неверно: если $A,B$ матрицы смежности двух графов, и мы имеем $\det(A) = \det(B)$, не обязательно, что графы изоморфны. Фактически, даже если$A$ и $B$имеют одинаковые собственные значения, графы не обязательно изоморфны. Примеры этого явления называются изоспектральными (или коспектральными) парами графов.

1 JCAA Aug 17 2020 at 23:04

Нет. Путь длины 2 (2 ребра, 3 вершины) имеет det 0, а граф с 3 вершинами и без ребер также имеет det 0.