Расщепление вершины

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

Vertex splitting.png

Литература

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