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

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

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

Литература

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

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

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