Меню
Главная
Случайная статья
Настройки
|
В теории графов теорема Эрдёша – Поза (Пал Эрдёш и Лайош Поза[англ.]) утверждает, что существует функция f(k), такая, что для любого натурального числа
Теорема утверждает, что для любого конечного числа
Свойство Эрдёша–Поза
Семейство F графов или гиперграфы по определению имеют свойство Эрдёша–Поза, если существует функция f: N N, такая, что для любого (гипер-)графа G и любого целого k одно из следующих утверждений верно:
- G содержит k вершинно разъединённых подграфов, каждый из которых изоморфен графу из F
- G содержит множество вершин C размера, не превосходящего f(k), такое, что G C не содержит подграфов, изоморфных одному из графов F.
Определение часто формулируется следующим образом. Если обозначить через (G) максимальное число вершин непересекающихся подграфов G, изоморфных графам из F и через (G) максимальное число вершин, удаление которых из G оставляет граф без графов, изоморфных графам из F, тогда (G) f((G)), для некоторой функции f: N N, не зависящего от G.
Примечания
- Erds, Psa, 1965.
- Lovsz, 1965.
- Voss, 1969.
Литература- Paul Erds, Lajos Psa. On independent circuits contained in a graph (англ.) // Canad. Journ. Math. — 1965. — Vol. 17. — doi:10.4153/CJM-1965-035-8.
- Voss Heinz-Jrgen. Eigenschaften von Graphen, die keine k+1 knotenfremde Kreise enthalten (англ.) // Mathematische Nachrichten. — 1969. — Vol. 40. — doi:10.1002/mana.19690400104.
- Lszl Lovsz. On graphs not containing independent circuits (англ.) // Mat. Lapok. — 1965. — Iss. 16.
|
|