4194
правки
Расщепление вершины: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Расщепление вершины''' (''Vertex splitting'') - 1) преобразование графа, заключающеес...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Расщепление вершины''' (''Vertex splitting'') - | '''Расщепление вершины''' (''[[Vertex splitting]]'') - | ||
1) преобразование графа, | 1) преобразование [[граф|графа]], | ||
заключающееся в замене вершины <math>v</math> вершинами | заключающееся в замене [[вершина|вершины]] <math>v</math> вершинами | ||
<math>v'</math> и <math>v''</math>, соединенными ребром <math>(v',v'')</math>, причем вершины, смежные | <math>v'</math> и <math>v''</math>, соединенными [[ребро|ребром]] <math>(v',v'')</math>, причем вершины, [[смежные вершины|смежные]] | ||
с <math>v</math>, распределяются между новыми вершинами каким-то способом. При | с <math>v</math>, распределяются между новыми вершинами каким-то способом. При | ||
расщеплении вершины в орграфе последняя заменяется вершинами <math>v'</math> и | расщеплении вершины в [[орграф|орграфе]] последняя заменяется вершинами <math>v'</math> и | ||
<math>v''</math>, соединенными | <math>v''</math>, соединенными | ||
дугой <math>(v',v'')</math>, причем дуги, заходившие в <math>v</math>, | [[дуга|дугой]] <math>(v',v'')</math>, причем дуги, [[заходящая дуга|заходившие]] в <math>v</math>, | ||
теперь заходят в <math>v'</math>, а дуги, исходившие из <math>v</math>, теперь исходят из | теперь заходят в <math>v'</math>, а дуги, [[исходящая дуга|исходившие]] из <math>v</math>, теперь исходят из | ||
<math>v''</math>; | <math>v''</math>; | ||
2) преобразование '' уграфа'', при котором некоторая вершина | 2) преобразование '' [[уграф|уграфа]]'', при котором некоторая [[вершина]] | ||
<math>p</math>, не являющаяся ни '' начальной'', ни ''конечной'' и не имеющая петли, | <math>p</math>, не являющаяся ни '' [[начальная вершина|начальной]]'', ни ''[[конечная вершина|конечной]]'' и не имеющая [[петля|петли]], | ||
заменяется на <math>r</math> экземпляров по одному для каждой из <math>r</math> | заменяется на <math>r</math> экземпляров по одному для каждой из <math>r</math> | ||
заходящих в <math>p</math> дуг. | заходящих в <math>p</math> дуг. | ||
[[Файл:Vertex splitting.png|500px]] | |||
==Литература== | ==Литература== | ||
[Лекции], | [Лекции], | ||