Той самий граф геометрично можна зобразити різноманітними способами. Так, на рис.2.8 наведені три зображення того самого графа. Такі графи називаються ізоморфними.
Рис. 2.7. Граф у формі дерева
Довільна підстановка j на множині вершин графа G, що зберігає відношення суміжності, тобто така, що уяви j(u) і j(v) вершин u і v суміжні тоді і тільки тоді, коли суміжні самі вершини u і v, називається автоморфізмом графа G. Іншими словами, автоморфізм графа - це ізоморфізм графа на себе.
1
1 2
2
1 4 3 4
4 3
Рис.2.8. Приклад ізоморфних графів 2 3
Довільний граф G має щонайменше один автоморфізм - тотожне перетворення е: VG ® VG, при якому e(v) = v для будь-якої вершини v. Очевидно, що якщо j - автоморфізм графа G, то й обернена підстановка j-1 також є автоморфізмом. Якщо підстановки j і f обидві є автоморфізми, то і їхній добуток jf - автоморфізм.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление