Теорема Эрдёша — Поза

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

В теории графов теорема Эрдёша – Поза (Пал Эрдёш и Лайош Поза[англ.]) утверждает, что существует функция f(k), такая, что для любого натурального числа k любой граф либо содержит k разъединённых по вершинам циклов, либо он имеет разрезающее циклы множество из f(k) вершин, которое пересекает любой цикл. Более того, f(k) = O(k log k) в нотации O Большое. Ввиду этой теоремы, говорят, что циклы имеют свойство Эрдёша – Поза.

Теорема утверждает, что для любого конечного числа k существует некоторое (минимальное) значение f(k), для которого в любом графе, не имеющем k вершинно разъединённых циклов, все циклы могут быть покрыты f(k) вершинами. Это обобщает неопубликованный результат Болобаша[англ.], который утверждает, что f(2) = 3. Эрдёш и Поза[1] получили границы c1k log k < f(k) < c2k log k в общем случае. Этот результат предполагает, что хотя существует бесконечно много графов без k разъединённых циклов, они распадаются на конечное число просто описываемых классов. Для случая k = 2, Ловаш[2] дал полное описание. Восс[3] доказал, что f(3) = 6 и 9 ≤ f(4) ≤ 12.

Свойство Эрдёша–Поза

[править | править код]

Семейство F графов или гиперграфы по определению имеют свойство Эрдёша–Поза, если существует функция f: NN, такая, что для любого (гипер-)графа G и любого целого k одно из следующих утверждений верно:

  • G содержит k вершинно разъединённых подграфов, каждый из которых изоморфен графу из F
  • G содержит множество вершин C размера, не превосходящего f(k), такое, что GC не содержит подграфов, изоморфных одному из графов F.

Определение часто формулируется следующим образом. Если обозначить через ν(G) максимальное число вершин непересекающихся подграфов G, изоморфных графам из F и через τ(G) максимальное число вершин, удаление которых из G оставляет граф без графов, изоморфных графам из F, тогда ν(G) ≤ f(τ(G)), для некоторой функции f: NN, не зависящего от G.

Примечания

[править | править код]

Литература

[править | править код]
  • Paul Erdős, Lajos Pósa. On independent circuits contained in a graph (англ.) // Canad. Journ. Math. — 1965. — Vol. 17. — doi:10.4153/CJM-1965-035-8.
  • Voss Heinz-Jürgen. Eigenschaften von Graphen, die keine k+1 knotenfremde Kreise enthalten (англ.) // Mathematische Nachrichten. — 1969. — Vol. 40. — doi:10.1002/mana.19690400104.
  • László Lovász. On graphs not containing independent circuits (англ.) // Mat. Lapok. — 1965. — Iss. 16.