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

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


См. также ''Аранжируемый граф, Запрещенный подграф, Одновходовый граф, Регуляризуемый граф, Сводимый управляющий граф.''
[[Файл:Collapsible graph.png]]
 
==См. также==
''[[Аранжируемый граф]], [[Запрещенный подграф]], [[Одновходовый граф]], [[Регуляризуемый граф]], [[Сводимый управляющий граф]].''
==Литература==
==Литература==
[Касьянов/88],
[Касьянов/88],


[Евстигнеев-Касьянов/94]
[Евстигнеев-Касьянов/94]

Версия от 13:07, 15 января 2010

Разборный граф (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{ p }[/math] и [math]\displaystyle{ (p,q) }[/math] из [math]\displaystyle{ G }[/math] и заменяет в нем дуги, заходящие в [math]\displaystyle{ p }[/math], на дуги, заходящие в [math]\displaystyle{ q }[/math].

Collapsible graph.png

См. также

Аранжируемый граф, Запрещенный подграф, Одновходовый граф, Регуляризуемый граф, Сводимый управляющий граф.

Литература

[Касьянов/88],

[Евстигнеев-Касьянов/94]