Запрещенный подграф: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Запрещенный подграф''' (''Forbidden subgraph'') - Говорят, что ''уграф'' содержит запрещ...)
 
Нет описания правки
Строка 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]. Отсутствие в уграфе запрещенного подграфа равносильно регуляризуемости уграфа.

Файл:Forbidden subgraph.png

См. также

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

Литература

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

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