4194
правки
Разборный граф: различия между версиями
Материал из WEGA
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Разборный граф''' (''Collapsible graph'') - ''уграф'' <math>G</math>, который может быть преоб...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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] | ||
