Запрещенный подграф: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Запрещенный подграф''' (''Forbidden subgraph'') - Говорят, что ''уграф'' содержит запрещ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Запрещенный подграф''' (''Forbidden subgraph'') - Говорят, что | '''Запрещенный подграф''' (''[[Forbidden subgraph]]'') - Говорят, что ''[[уграф]]'' содержит | ||
''уграф'' содержит | запрещенный подграф, если в нем существуют различные [[вершина|вершины]] <math>p_1</math>, <math>p_2</math> и <math>p_3</math>, что найдутся непересекающиеся по [[внутренняя вершина|внутренним вершинам]] [[простой путь|простые пути]] <math>P_{0,1}</math>, <math>P_{1,2}</math>, <math>P_{1,3}</math>, <math>P_{2,3}</math>, <math>P_{3,2}</math>, где <math>P_{i,j}</math> обозначает [[путь]] от вершины <math>p_i</math> до <math>p_j</math>. Отсутствие в уграфе запрещенного подграфа равносильно ''регуляризуемости уграфа''. | ||
запрещенный подграф, если в нем существуют различные вершины <math>p_1</math>, <math>p_2</math> и <math>p_3</math>, | |||
что найдутся непересекающиеся по внутренним вершинам простые пути <math>P_{0,1}</math>, | |||
<math>P_{1,2}</math>, <math>P_{1,3}</math>, <math>P_{2,3}</math>, <math>P_{3,2}</math>, где <math>P_{i,j}</math> обозначает | |||
путь от вершины <math>p_i</math> до <math>p_j</math>. Отсутствие в уграфе запрещенного подграфа равносильно | |||
''регуляризуемости уграфа''. | |||
См. также ''Аранжируемый граф, Одновходовый граф, Разборный граф, Сводимый управляющий граф''. | [[Файл:Forbidden subgraph.png|500px]] | ||
==См. также== | |||
''[[Аранжируемый граф]], [[Одновходовый граф]], [[Разборный граф]], [[Сводимый управляющий граф]]''. | |||
==Литература== | ==Литература== | ||
[Касьянов/88], | [Касьянов/88], | ||
[Евстигнеев-Касьянов/94]} | [Евстигнеев-Касьянов/94]} | ||
Версия от 18:39, 20 октября 2009
Запрещенный подграф (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]}