Расщепление вершины: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Расщепление вершины''' (''[[Vertex splitting]]'') -
'''Расщепление вершины''' (''[[Vertex splitting]]'')
1) преобразование [[граф|графа]],
1) преобразование [[граф|графа]],
заключающееся в замене [[вершина|вершины]] <math>v</math> вершинами
заключающееся в замене [[вершина|вершины]] <math>v</math> вершинами
Строка 18: Строка 18:


==Литература==
==Литература==
[Лекции],  
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


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


[Евстигнеев-Касьянов/94]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

Текущая версия от 12:26, 30 августа 2011

Расщепление вершины (Vertex splitting) — 1) преобразование графа, заключающееся в замене вершины [math]\displaystyle{ v }[/math] вершинами [math]\displaystyle{ v' }[/math] и [math]\displaystyle{ v'' }[/math], соединенными ребром [math]\displaystyle{ (v',v'') }[/math], причем вершины, смежные с [math]\displaystyle{ v }[/math], распределяются между новыми вершинами каким-то способом. При расщеплении вершины в орграфе последняя заменяется вершинами [math]\displaystyle{ v' }[/math] и [math]\displaystyle{ v'' }[/math], соединенными дугой [math]\displaystyle{ (v',v'') }[/math], причем дуги, заходившие в [math]\displaystyle{ v }[/math], теперь заходят в [math]\displaystyle{ v' }[/math], а дуги, исходившие из [math]\displaystyle{ v }[/math], теперь исходят из [math]\displaystyle{ v'' }[/math];

2) преобразование уграфа, при котором некоторая вершина [math]\displaystyle{ p }[/math], не являющаяся ни начальной, ни конечной и не имеющая петли, заменяется на [math]\displaystyle{ r }[/math] экземпляров по одному для каждой из [math]\displaystyle{ r }[/math] заходящих в [math]\displaystyle{ p }[/math] дуг.

Vertex splitting.png

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.