683
правки
Запрещенный подграф: различия между версиями
Материал из WikiGrapp
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Запрещенный подграф''' (''Forbidden subgraph'') - Говорят, что ''уграф'' содержит запрещ...) |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показано 7 промежуточных версий 2 участников) | |||
| Строка 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>, | [[Файл:Forbidden subgraph1.png|600px]] | ||
<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>. Отсутствие в уграфе запрещенного подграфа равносильно | ==См. также== | ||
'' | * ''[[Аранжируемый граф]],'' | ||
* ''[[Одновходовый граф]],'' | |||
* ''[[Каркас уграфа]],'' | |||
* ''[[Разборный граф]],'' | |||
* ''[[Регуляризуемый граф]],'' | |||
* ''[[Сводимый управляющий граф]].'' | |||
==Литература== | ==Литература== | ||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
* Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. | |||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
[ | [[Категория: Сводимые и регуляризуемые графы]] | ||
