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

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


* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
[[Категория: Сводимые и регуляризуемые графы]]

Текущая версия от 09:35, 11 июня 2023

Запрещенный подграф (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 subgraph1.png

См. также

Литература

  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
  • Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.
  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.