Операції на графах - Банк рефератів, творів, доповідей, курсових та дипломних робіт
БІЛОукраїнський ДЕРЖАВНИЙ УНІВЕРСИТЕТ ІНФОРМАТИКИ ТА РАДІОЕЛЕКТРОНІКИ
«Операції на графах»
Операції на графах дозволяють утворювати нові графи з кількох простих. У цьому пункті будуть розглянуті операції на графах без паралельних ребер (дуг).
Нехай 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 - матриці суміжності вершин цих графів. Тоді матрицею суміжності вершин графа G1IG2 є матриця A = A1IA2, утворена поелементним логічним додаванням матриць A1 і A2.
Розглянемо виконання операції об'єднання графів, безліч вершин яких збігаються. Нехай G1(X1,E1) і G2(X2,E2) – графи без паралельних ребер та безлічі X1 і X2 вершин цих графів незбігаються. Нехай A1 і A2 – матриці суміжності вершин графів. Для таких графів операція об'єднання може бути виконана в такий спосіб.
Відповідно до визначення операції об'єднання графів знайдемо безліч вершин результуючого графа як X1IX2. Побудуємо допоміжні графи G'1 і G'2, безлічі вершин яких є безліч X1IX2, а безліч ребер (дуг) визначається множинами E1 для графа G'1 і E2 для графа G'2. Очевидно, що матриці A'1 і A'2 суміжності вершин цих графів можуть бути отримані з матриць A1 і A2 шляхом додавання додаткових стовпців і рядків з нульовими елементами.
Застосувавши до граф G'1 і G'2 теорему 4.1, знайдемо матрицю суміжності вершин графа G'1ІG'2 як A'1ІA'2. Очевидно, що отриманої матриці суміжності вершин відповідає граф, безліч вершин якого дорівнює X1X2, а безліч ребер визначається, як E1IE2, що відповідає операції об'єднання графів.
Приклад 1. Виконати в матричній формі операцію поєднання графів G1 і G2, представлених на рис. 1.