Инвариант Колен де Вердьера

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Инвариант Колен де Вердьера — характеристика графа \mu(G), определённая для любого графа G, введённая Ивом Колен де Вердьером (фр.) в 1990 году в процессе исследования мультиплетности (англ.) второго собственного значения некоторых операторов Шрёдингера.[1]

Определение[править | править исходный текст]

Пусть G=(V,E) — простой (не содержащий петель и кратных рёбер) ациклический граф. Без потери общности поименуем множество вершин следующим образом: V=\{1,\dots,n\}. Тогда \mu(G) — наибольший коранг любой такой матрицы M=(M_{i,j})\in\mathbb{R}^{(n)}, что:

  • (M1) для любых i,j, где i\neq j: M_{i,j}<0, если i и j смежны, и M_{i,j}=0 , если i и j в противном случае
  • (M2) M имеет ровно одно собственное значение мультиплетности 1;
  • (M3) не существует такой ненулевой матрицы X=(X_{i,j})\in\mathbb{R}^{(n)}, что MX=0, и что X_{i,j}=0, независимо от того, i=j, или M_{i,j}\neq 0.[2][1]

Классификация известных групп графов[править | править исходный текст]

С точки зрения инварианта Колен де Вердьера, некоторые хорошо известные семейства графов обладают характерными особенностями:

  • μ ≤ 0 тогда и только тогда, когда у G нет рёбер;[1][2]
  • μ ≤ 1 тогда и только тогда, когда G является линейным лесом (лесом, в котором каждый компонент является путём, то есть инцидентность любой вершины не больше 2);[1][3]
  • μ ≤ 2 тогда и только тогда, когда G является внешнепланарным графом (англ.) (все вершины лежат на одной грани);[1][2]
  • μ ≤ 3 тогда и только тогда, когда G является планарным графом;[1][2]
  • μ ≤ 4 тогда и только тогда, когда G является бессвязно встраиваемым (англ.), то есть не существует двух циклов в G, для которых при отображении на евклидово пространство (коэффициент зацепления) равен нулю.[1][4]

Эти же группы графов проявляют свои отличительные черты и при анализе связи между инвариантом графа и дополнением этого графа:

  • Если дополнение графа с n вершинами является линейным лесом, то μ ≥ n − 3;[1][5]
  • Если дополнение графа с n вершинами является внешнепланарным графом, тоμ ≥ n − 4;[1][5]
  • Если дополнение графа с n вершинами является планарным графом, то μ ≥ n − 5.[1][5]

Миноры графов[править | править исходный текст]

Минором (англ.) графа G называют граф H, полученный из G последовательным удалением вершин, удалением рёбер и сжатием рёбер. Инвариант Колена де Вердьера монотонен относительно операции взятия минора в том смысле, что минорирование графа не может увеличить его инвариант:

Если H является минором G, то \mu(H)\leq\mu(G).[2]

По теореме Робертсона — Сеймура (англ.), для любого k существует H, конечное множество графов такое, что для любого графа с инвариантом не более k графы из H не могут быть минорами. В работе (Colin de Verdière 1990) перечисляются множества таких недопустимых миноров (англ.) для k ≤ 3; для k = 4 множество недопустимых миноров состоит из семи графов семейства Петерсена (англ.) по определению бессвязно встраиваемого графа как графа с μ ≤ 4 и без графов Петерсена в качестве миноров.[4]

Связь с хроматическим числом[править | править исходный текст]

(Colin de Verdière 1990) предположил, что любой граф с инвариантом де Вердьера μ может быть раскрашен с использованием не более чем μ + 1 цветов. Например, у линейных лесов (компоненты которых являются двудольными графами) инвариант равняется 1; у внешнепланарных графов инвариант равняется 2, и они могут быть раскрашены тремя цветами; у планарных графов инвариант — 3, и они могут быть раскрашены четырьмя цветами.

Для графов с инвариантом де Вердьера не более четырёх предположение истинно; они все являются бессвязно встраиваемыми, и тот факт, что они раскрашиваются пятью цветами, является следствием доказательства гипотезы Хадвигера для графов без миноров типа K6 в работе (Robertson, Seymour & Thomas 1993).

Другие свойства[править | править исходный текст]

Если число пересечений (англ.) графа равно k, то инвариант де Вердьера для него будет не более k + 3. Например, графы Куратовского K5 и K3,3 могут быть изображены с одним пересечением, и инвариант для них будет не более четырёх.[2]

Примечания[править | править исходный текст]

  1. 1 2 3 4 5 6 7 8 9 10 (van der Holst, Lovász & Schrijver 1999).
  2. 1 2 3 4 5 6 (Colin de Verdière 1990).
  3. В работе (Colin de Verdière 1990) этот случай явным образом не рассмотрен, но он явным образом вытекает из результатов анализа графов, не имеющих миноров вида «треугольник» и «клешня».
  4. 1 2 (Lovász & Schrijver 1998).
  5. 1 2 3 (Kotlov, Lovász & Vempala 1997).

Ссылки[править | править исходный текст]