Разборный граф

Материал из WEGA
Версия от 14:02, 14 января 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Разборный граф''' (''Collapsible graph'') - ''уграф'' <math>G</math>, который может быть преоб...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Разборный граф (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].

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

Литература

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

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