В теории графов теорема Эрдёша – Поза (Пал Эрдёш и ) утверждает, что существует функция , такая, что для любого натурального числа любой граф либо содержит разъединённых по вершинам циклов, либо он имеет разрезающее циклы множество из вершин, которое пересекает любой цикл. Более того, в нотации O Большое. Ввиду этой теоремы, говорят, что циклы имеют свойство Эрдёша – Поза.
Теорема утверждает, что для любого конечного числа существует некоторое (минимальное) значение , для которого в любом графе, не имеющем вершинно разъединённых циклов, все циклы могут быть покрыты вершинами. Это обобщает неопубликованный результат , который утверждает, что . Эрдёш и Поза получили границы в общем случае. Этот результат предполагает, что хотя существует бесконечно много графов без разъединённых циклов, они распадаются на конечное число просто описываемых классов. Для случая , Ловаш дал полное описание. Восс доказал, что и .
Свойство Эрдёша–Поза Семейство графов или гиперграфы по определению имеют свойство Эрдёша–Поза, если существует функция , такая, что для любого (гипер-)графа и любого целого одно из следующих утверждений верно:
содержит вершинно разъединённых подграфов, каждый из которых изоморфен графу из содержит множество вершин размера, не превосходящего , такое, что не содержит подграфов, изоморфных одному из графов .
Определение часто формулируется следующим образом. Если обозначить через максимальное число вершин непересекающихся подграфов , изоморфных графам из и через максимальное число вершин, удаление которых из оставляет граф без графов, изоморфных графам из , тогда , для некоторой функции , не зависящего от .
Примечания
Литература
Категория:Теоремы теории графов