Асиметричний граф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Вісім асиметричний графів із 6 вершинами
Граф Фрухта, найменший асиметричний кубічний граф
Види графів за їхніми автоморфізмами
відстанево-транзитивний[en]відстанево-регулярний[en]сильно регулярний[en]
симетричний (дуго-транзитивний)t-транзитивний, t ≥ 2
(якщо зв'язний)
вершинно- та реберно-транзитивний[en]реберно-транзитивний і регулярнийреберно-транзитивний
вершинно-транзитивнийрегулярний
граф Келікососиметричний[en]асиметричний

У теорії графів, розділі математики, неорієнтований граф називається асиметричним графом, якщо він не має нетривіальних симетрій.

Формально, автоморфізм графу є перестановкою р його вершин з тією властивістю, що будь-які дві вершини U і V суміжні тоді і тільки тоді, коли p(U) і p(V) є суміжними. Тотожне відображення графу на себе завжди автоморфізм, і називається тривіальним автоморфізмом графу. Асиметричний граф — це граф, для якого не існує ніяких інших автоморфізмів.