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

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

Запрещенный подграф (Forbidden subgraph) — Говорят, что уграф содержит запрещенный подграф, если в нем существуют различные вершины $p_{1}$ , $p_{2}$ и $p_{3}$ , что найдутся непересекающиеся по внутренним вершинам простые пути $P_{0, 1}$ , $P_{1, 2}$ , $P_{1, 3}$ , $P_{2, 3}$ , $P_{3, 2}$ , где $P_{i, j}$ обозначает путь от вершины $p_{i}$ до $p_{j}$ . Отсутствие в уграфе запрещенного подграфа равносильно регуляризуемости уграфа.

См. также

Литература

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

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

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

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

См. также

Литература

Навигация

Поиск