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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
Строка 2: Строка 2:
запрещенный подграф, если в нем существуют различные [[вершина|вершины]] <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]]
[[Файл:Forbidden subgraph.png|700px]]


==См. также==  
==См. также==  

Навигация