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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 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>\,p</math> и <math>\,(p,q)</math> из <math>\,G</math> и заменяет в нем дуги, заходящие в <math>\,p</math>, на дуги, заходящие в <math>\,q</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.
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
* Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.


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

Текущая версия от 21:26, 8 октября 2019

Разборный граф (Collapsible graph) — уграф [math]\displaystyle{ \,G }[/math], который может быть преобразован в тривиальный итеративным применением следующих двух преобразований: [math]\displaystyle{ \,T1 }[/math]удаление петли и [math]\displaystyle{ \,T2 }[/math]слияние двух вершин. Преобразование [math]\displaystyle{ \,T1 }[/math] определено для любой вершины [math]\displaystyle{ \,p }[/math] уграфа [math]\displaystyle{ \,G }[/math] и состоит в удалении дуги [math]\displaystyle{ \,(p,p) }[/math] из [math]\displaystyle{ \,G }[/math]. Преобразование [math]\displaystyle{ \,T2 }[/math] определено только для такой пары вершин [math]\displaystyle{ \,p }[/math] и [math]\displaystyle{ \,q }[/math], что [math]\displaystyle{ \,p }[/math] — единственный предшественник [math]\displaystyle{ \,q }[/math]; оно удаляет [math]\displaystyle{ q }[/math] и [math]\displaystyle{ (p,q) }[/math] из [math]\displaystyle{ G }[/math] и заменяет в нем дуги, исходящие из [math]\displaystyle{ q }[/math], на дуги, исходящие из [math]\displaystyle{ p }[/math].

Collapsible graph.png

См. также

Литература

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