Операция раздвоения (расщепления) вершины

Пусть - некоторая из вершин графа . Множество смежных ей вершин произвольным образом разобьем на два класса и . Далее, удалим вершину вместе с инцидентными ей ребрами и добавим две новые вершины и соединенные ребром . Вершину соединим ребром с каждой вершиной множества , а вершину - с каждой вершиной из множества . Таким образом, из графа получен новый граф результате операции расщепления вершины . На рис. 2.9. приведен пример расщепления вершины

Рис. 2.9