Абстрактни операции върху графики - Банка от резюмета, есета, доклади, курсови работи и дипломни работи
БЕЛОБЪЛГАРСКИ ДЪРЖАВЕН УНИВЕРСИТЕТ ПО ИНФОРМАТИКА И РАДИОЕЛЕКТРОНИКА
"Операции върху графики"
Операциите върху графики ви позволяват да формирате нови графики от няколко по-прости. В този раздел ще бъдат разгледани операциите върху графи без успоредни ръбове (дъги).
Нека G1(X1,E1) и G2(X2,E2) са произволни графики. Обединение G1 и G2 на графи G1 и G2 е граф с набор от върхове X1 и X2 и с набор от ребра (дъги) E1 и E2.
Разгледайте операцията на примера на графиките G1(X1,E1) и G2(X2,E2), показани на фиг. 4.1. Наборите от върхове на първия и втория графики са равни съответно на X1 = и X2 = , а наборът от върхове на резултантния граф е дефиниран като X = X1 и X2 = . По подобен начин дефинираме набори от дъги на графика:
Получената графика G(X,E) = G1(X1,E1) и G2(X2,E2) също е показана на фиг. 1.
Операцията обединение има следните свойства, които следват от дефиницията на операцията и свойствата на операциите върху множества:
G1ИG2 = G2ИG1 - свойство на комутативност;
G1И(G2ИG3) = (G1ИG2)ИG3 е свойството за асоциативност.
Операцията за обединяване на графики може да се извърши в матрична форма. За графи с еднакъв набор от върхове е вярна следната теорема.
Теорема 1.Нека G1 и G2 са две графи (едновременно насочени или неориентирани) с едно и също множество от върхове X и нека A1 и A2 са матриците на съседство на върховете на тези графи. Тогава матрицата на съседство на върховете на графа G1 и G2 е матрицата A = A1 и A2, образувана от поелементното логическо събиране на матриците A1 и A2.
Нека разгледаме операцията по обединяване на графи, чиито набори от върхове не съвпадат. Нека G1(X1,E1) и G2(X2,E2) са графики без успоредни ръбове и наборите от върхове X1 и X2 на тези графики несъвпада. Нека A1 и A2 са матриците на съседство на върховете на техните графи. За такива графики операцията за обединение може да се извърши по следния начин.
В съответствие с дефиницията на операцията за обединение на графа, ние намираме множеството от върхове на получения граф като X1ИX2. Построяваме спомагателни графове G'1 и G'2, чиито набори от върхове са множеството X1 и X2, а множеството от ребра (дъги) се определя от множествата E1 за графа G'1 и E2 за графа G'2. Очевидно матриците на съседство A'1 и A'2 на върховете на тези графи могат да бъдат получени от матриците A1 и A2 чрез добавяне на допълнителни колони и редове с нулеви елементи към тях.
Прилагайки теорема 4.1 към графите G'1 и G'2, намираме матрицата на съседство на върховете на графа G'1 и G'2 като A'1 и A'2. Очевидно е, че получената матрица на съседство на върхове съответства на граф, чийто набор от върхове е равен на X1ИX2, а наборът от ръбове е дефиниран като E1ИE2, което съответства на операцията за обединяване на графа.
Пример 1. Изпълнете в матрична форма операцията за комбиниране на графиките G1 и G2, показани на фиг. 1.