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

Расщепление вершины (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] дуг.

Литература

[Лекции],

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

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