Запрещенный подграф

Материал из WEGA
Версия от 16:30, 20 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Запрещенный подграф''' (''Forbidden subgraph'') - Говорят, что ''уграф'' содержит запрещ...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Запрещенный подграф (Forbidden subgraph) - Говорят, что уграф содержит запрещенный подграф, если в нем существуют различные вершины [math]\displaystyle{ p_1 }[/math], [math]\displaystyle{ p_2 }[/math] и [math]\displaystyle{ p_3 }[/math], что найдутся непересекающиеся по внутренним вершинам простые пути [math]\displaystyle{ P_{0,1} }[/math], [math]\displaystyle{ P_{1,2} }[/math], [math]\displaystyle{ P_{1,3} }[/math], [math]\displaystyle{ P_{2,3} }[/math], [math]\displaystyle{ P_{3,2} }[/math], где [math]\displaystyle{ P_{i,j} }[/math] обозначает путь от вершины [math]\displaystyle{ p_i }[/math] до [math]\displaystyle{ p_j }[/math]. Отсутствие в уграфе запрещенного подграфа равносильно регуляризуемости уграфа.

См. также Аранжируемый граф, Одновходовый граф, Разборный граф, Сводимый управляющий граф.

Литература

[Касьянов/88],

[Евстигнеев-Касьянов/94]}