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

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

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

Литература

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

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

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