Аноним

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

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Разборный граф''' (''[[Collapsible graph]]'') -
'''Разборный граф''' (''[[Collapsible graph]]'') ''[[уграф]]'' <math>\,G</math>,  который может
''[[уграф]]'' <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>\,q</math>; оно удаляет <math>\,p</math> и <math>\,(p,q)</math> из <math>\,G</math> и заменяет в нем дуги, заходящие в <math>\,p</math>, на дуги, заходящие в <math>\,q</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>p</math> и <math>(p,q)</math> из <math>G</math> и заменяет в нем дуги, заходящие в <math>p</math>, на дуги, заходящие в <math>q</math>.


[[Файл:Collapsible graph.png|750px]]
[[Файл:Collapsible graph.png|750px]]


==См. также==  
==См. также==  
''[[Аранжируемый граф]], [[Запрещенный подграф]], [[Одновходовый граф]], [[Регуляризуемый граф]], [[Сводимый управляющий граф]].''
* ''[[Аранжируемый граф]],''
* ''[[Запрещенный подграф]],''
* ''[[Одновходовый граф]],''
* ''[[Регуляризуемый граф]],''
* ''[[Сводимый управляющий граф]].''
==Литература==
==Литература==
[Касьянов/88],
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


[Евстигнеев-Касьянов/94]
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.