алгебраїчні операції
Оскільки граф складається з двох множин (вершини і ребра), то різні операції над множинами природним чином породжують відповідні операції над графами. Наприклад, об'єднання двох графів і визначається як граф, у якого,, а перетин - як граф, у якого,. Обидві операції ілюструє рис. 1.12.
Доповненням (додатковим графом) до графу називається граф, у якого безліч вершин той же, що у, а безліч ребер є доповненням множини до безлічі всіх невпорядкованих пар вершин. Інакше кажучи, дві різні вершини суміжні в графі тоді і тільки тоді, коли вони несуміжні в графі. Наприклад,. Інший приклад показаний на рис. 1.13. Очевидно, що завжди.
Під сумою двох абстрактних графів розуміють об'єднання графів з непересічними множинами вершин. Точніше кажучи, мається на увазі наступне. Спочатку вершин графів-доданків привласнюються імена (позначки, номери) так, щоб безлічі вершин не перетиналися, потім отримані графи об'єднуються. Операція складання асоціативна, тобто для будь-яких трьох графів. Тому можна утворювати суму будь-якого числа графів, що не вказуючи порядку дій за допомогою дужок. Якщо складаються примірників одного і того ж графа, то отриманий граф позначається через. Наприклад,. На рис. 1.14 зображений граф.
З'єднанням двох графів і називається граф. одержуваний з їх суми додаванням усіх ребер, що з'єднують вершини першого доданка з вершинами другого. Будемо записувати цю операцію як. На рис. 1.15 представлений граф. Легко бачити, що операції додавання і з'єднання графів пов'язані один з одним такими простими співвідношеннями:
Введемо ще два типи спеціальних графів, які легко описуються за допомогою операції з'єднання. Перший - повний двочастковий граф. У цьому графі безліч вершин розбите на два підмножини (частки), в одному з яких вершин, в іншому, і дві вершини в ньому суміжні тоді і тільки тоді, якщо вони належать різним підмножини. Другий - колесо. На рис. 1.16 показані графи і.
Твір графів і визначається наступним чином. Безліччю вершин графа є декартовій твір множин і, тобто вершини цього графа - впорядковані пари, де - вершина першого співмножники, - вершина другого. Вершини і в суміжні тоді і тільки тоді, якщо і суміжно з в графі, або і суміжно з в графі. За допомогою операції твори можна висловити деякі важливі графи через найпростіші. Наприклад, твір двох ланцюгів дає прямокутну решітку (див. Рис. 1.17). Якщо один з співмножників перетворити в цикл, додавши одне ребро. то прямокутні грати перетвориться в циліндричну. а якщо і другий співмножник перетворити в цикл, то вийде тороїдальна решітка.
Інший приклад - - мірний куб, який визначається наступним чином. Вершинами його є всілякі впорядковані виконавчі набори довжини. Всього, таким чином, в цьому графі вершин. Вершини і суміжні в ньому тоді і тільки тоді, коли набори і розрізняються точно в одній координаті. За допомогою операції твори граф можна визначити рекурсивно:
На рис. 1.18 показано, як виходить з.