Рассмотрим унарные операции на графе

Удаление вершины. Если х_i -вершина графа G = (X, A), то G–х_i -порожденный подграф графа G на множестве вершин X–х_i, т. е. G–х_i является графом, получившимся после удаления из графа G вершины х_i и всех ребер, инцидентных этой вершине. Удаление вершины х₃ показано на рис. 2.3,б (для исходного графа, изображенного на рис. 2.3,а). Матрица смежности исходного графа представлена на таблице 2.1а). Результирующая матрица смежности графа после выполнения операции удаления вершины х_i получается путем удаления соответствующего i- го столбца и i-ой строки из исходной матрицы и "сжимания" матрицы по вертикали и горизонтали начиная с (i+1)- го столбца и (i+1)-ой строки (таблица 2.1б). В дальнейшем элементы графа могут быть переобозначены.

Рис. 2.3.

Удаление ребра или удаление дуги. Если a_i -дуга графа G = = (X, A), то G-a_i – подграф графа G, получающийся после удаления из G дуги a_i. Заметим, что концевые вершины дуги a_i не удаляются. Удаление из графа множества вершин или дуг определяется как последовательное удаление определенных вершин или дуг. Удаление дуг a₄ и a₇ показано на рис. 2.3,в. Результирующая матрица смежности графа после выполнения операции удаления дуги a_i получается путем удаления соответствующих элементов из исходной матрицы (таблица 2.1в).

Замыкание или отождествление. Говорят, что пара вершин х_i и x_j в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все дуги в графе G, инцидентные х_i и x_j, становятся инцидентными новой вершине. Например, результат замыкания вершины х₁ и х₂ показан на рис. 2.3,г для графа G (рис. 2.3,а). Матрица смежности графа после выполнения операции замыкания вершин х_i и x_j получается путем поэлементного логического сложения i- го и j- го столбцов и i-ой и j- строк в исходной матрице и "сжимания" матрицы по вертикали и горизонтали (таблица 2.1г).

Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин. Граф, изображенный на рис. 2.3,д получен стягиванием дуги a₁, а на рис. 2.3,е – стягиванием дуг a₁, a₆ и a₇. Соответствующие результирующие матрицы смежности показаны в таблицах 2.1д и 2.1е.