Прямые отображения

Многозначные отображения

Рис. 2.3.

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

Удаление вершины. Если х_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б). В дальнейшем элементы графа могут быть переобозначены.

Удаление ребра или удаление дуги. Если 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е.

Прямым отображением 1-го порядка вершины х_i является множество таких вершин графа, для которых существует дуга (х_i, x_j), т. е Г¹(х_i) = {x_j: дуга (х_i, x_j) A} для графа G = (X, A), где X ={ х_i }, i =1, 2,..., n – множество вершин, а A = {a_i}, i = = 1, 2,..., m – множество дуг.

Прямое отображение 2-го порядка вершины х_i – это прямое отображение от прямого отображения 1-го порядка, т. е. Г⁺²(х_i) = Г⁺(Г⁺¹ (х_i)).

Аналогично можно записать для прямого отображения 3-го и т. д. n-го порядка.

Г⁺³(x_i)= Г⁺(Г⁺²(x_i))= Г⁺(Г⁺(Г⁺¹(x_i)))

...

Г⁺ⁿ(x_i)=Г⁺(Г^+(n-1)(x_i)).

Рис. 3.1. Орграф G

Прямые многозначные отображения для графа на рис. 3.1 находятся следующим образом:

Г⁺¹(x₁)=(x₂,x₃),

Г⁺²(x₁)=Г⁺(Г⁺¹(x₁))=Г⁺(x₂,x₃)=(x₃,x₅),

Г⁺³(x₁)=Г⁺(Г⁺²(x₁))=Г⁺(x₃,x₅)=(x₃,x₁) и т. д.