1023
правки
Разборный граф: различия между версиями
Материал из WEGA
нет описания правки
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Разборный граф''' (''[[Collapsible graph]]'') — ''[[уграф]]'' <math>\,G</math>, который может | '''Разборный граф''' (''[[Collapsible graph]]'') — ''[[уграф]]'' <math>\,G</math>, который может | ||
быть преобразован в [[тривиальный граф|тривиальный]] итеративным применением следующих двух преобразований: <math>\,T1</math> — ''[[удаление ребра|удаление петли]]'' и <math>\,T2</math> — ''[[слияние двух вершин]]''. Преобразование <math>\,T1</math> определено для любой [[вершина|вершины]] <math>\,p</math> уграфа <math>\,G</math> и состоит в удалении [[дуга|дуги]] <math>\,(p,p)</math> из <math>\,G</math>. Преобразование <math>\,T2</math> определено только для такой пары вершин <math>\,p</math> и <math>\,q</math>, что <math>\,p</math> — единственный | быть преобразован в [[тривиальный граф|тривиальный]] итеративным применением следующих двух преобразований: <math>\,T1</math> — ''[[удаление ребра|удаление петли]]'' и <math>\,T2</math> — ''[[слияние двух вершин]]''. Преобразование <math>\,T1</math> определено для любой [[вершина|вершины]] <math>\,p</math> уграфа <math>\,G</math> и состоит в удалении [[дуга|дуги]] <math>\,(p,p)</math> из <math>\,G</math>. Преобразование <math>\,T2</math> определено только для такой пары вершин <math>\,p</math> и <math>\,q</math>, что <math>\,p</math> — единственный | ||
[[предшественник вершины|предшественник]] <math>\,q</math>; оно удаляет <math> | [[предшественник вершины|предшественник]] <math>\,q</math>; оно удаляет <math>q</math> и <math>(p,q)</math> из <math>G</math> и заменяет в нем дуги, исходящие из <math>q</math>, на дуги, исходящие из <math>p</math>. | ||
[[Файл:Collapsible graph.png|750px]] | [[Файл:Collapsible graph.png|750px]] | ||
| Строка 8: | Строка 8: | ||
* ''[[Аранжируемый граф]],'' | * ''[[Аранжируемый граф]],'' | ||
* ''[[Запрещенный подграф]],'' | * ''[[Запрещенный подграф]],'' | ||
* ''[[Каркас уграфа]],'' | |||
* ''[[Одновходовый граф]],'' | * ''[[Одновходовый граф]],'' | ||
* ''[[Регуляризуемый граф]],'' | * ''[[Регуляризуемый граф]],'' | ||
* ''[[Сводимый управляющий граф]].'' | * ''[[Сводимый управляющий граф]].'' | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | * Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | ||
