«Сетевые структуры данных. Понятие графа и его представления.»

3.3. Унарные операции

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

Рисунок 12 – Графы, предоставленные графическим способом

Рисунок 13 – Графы, предоставленные матричным способом

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

Замыкание или отождествление. Говорят, что пара вершин х_i и x_j в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все дуги в графе G, инцидентные х_i и x_j, становятся инцидентными новой вершине. Например, результат замыкания вершины х₁ и х₂ показан на рисунке 12(г) для графа G (рисунок 12(а)). Матрица смежности графа после выполнения операции замыкания вершин х_i и x_j получается путем поэлементного логического сложения i - го и j - го столбцов и i -ой и j - строк в исходной матрице и "сжимания" матрицы по вертикали и горизонтали (Рисунок 13(г)).
Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин. Граф, изображенный на рисунок 12(д) получен стягиванием дуги a₁, а на рисунок 12(е) – стягиванием дуг a₁, a₆ и a₇. Соответствующие результирующие матрицы смежности показаны в рисунке 13(д) и рисунке 13(е).