Операция удаления вершины

Пусть G=(V,E) – граф, и - некоторая его вершина. Граф G₁ = G-v получен из графа G в результате удаления вершины v, т.е. , где - множество ребер (дуг) без ребер (дуг), инцидентных удаленной вершине v, т.е. при удалении вершины v удаляются все инцидентные ей ребра (дуги). На рис. 2.6. приведен пример удаления вершины 4 из графа.

Рис. 2.6

Нетрудно убедиться, что операция удаления вершины не зависит от порядка, в котором удаляются вершигы из графа.