Асимметричный граф
В теории графов , разделе математики, неориентированный граф называется асимметричным, если он не имеет нетривиальных симметрий .
Формально автоморфизм графа — это перестановка p его вершин , обладающая тем свойством, что любые две вершины u и v смежны тогда и только тогда, когда p ( u ) и p ( v ) смежны.Тождественное отображение графа на самого себя всегда является автоморфизмом и называется тривиальным автоморфизмом графа. Асимметричный граф — это граф, для которого нет других автоморфизмов.
Обратите внимание, что термин «асимметричный граф» не является отрицанием термина « симметричный граф », поскольку последний относится к более сильному условию, чем наличие нетривиальных симметрий.
Примеры [ править ]
Наименьшие асимметричные нетривиальные графы имеют 6 вершин. [1] Наименьшие асимметричные регулярные графы имеют десять вершин; существуют десятивершинные асимметричные графы, которые являются 4-регулярными и 5-регулярными. [2] [3] Один из пяти самых маленьких асимметричных кубических графов. [4] с двенадцатью вершинами, — граф Фрухта открытый в 1939 году. [5] Согласно усиленной версии теоремы Фрухта , существует бесконечно много асимметричных кубических графов.
Свойства [ править ]
Класс асимметричных графов замкнут относительно дополнений : граф G асимметричен тогда и только тогда, когда его дополнение таково. [1] Любой асимметричный граф с n -вершинами можно сделать симметричным, добавляя и удаляя в общей сложности не более n /2 + o( n ) ребер. [1]
Случайные графики [ править ]
Доля графов на n вершинах с нетривиальным автоморфизмом стремится к нулю с ростом n , что неформально выражается как « почти все конечные графы асимметричны». Напротив, опять же неформально, «почти все бесконечные графы обладают нетривиальной симметрией». Точнее, счетные бесконечные случайные графы в модели Эрдеша – Реньи с вероятностью 1 изоморфны высокосимметричному графу Радо . [1]
Деревья [ править ]
Наименьшее асимметричное дерево имеет семь вершин: оно состоит из трех путей длиной 1, 2 и 3, связанных в общей конечной точке. [6] В отличие от ситуации с графами, почти все деревья симметричны. В частности, если дерево выбрано равномерно случайным образом среди всех деревьев на n помеченных узлах, то с вероятностью, стремящейся к 1 по мере увеличения n , дерево будет содержать несколько двух листьев, смежных с одним и тем же узлом, и будет иметь симметрии, меняющие эти два листа. [1]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д и Эрдеш, П .; Реньи, А. (1963), «Асимметричные графы» (PDF) , Acta Mathematica Hungarica , 14 (3): 295–315, doi : 10.1007/BF01895716 , заархивировано из оригинала (PDF) 6 июля 2017 г. , извлечено 22 апреля 2010 г.
- ^ Барон, Г.; Имрих, В. (1969), «Асимметрично правильный графен», Acta Mathematica Венгерской академии наук , 20 : 135–142, doi : 10.1007/BF01894574 , MR 0238726 .
- ^ Гевирц, Аллан; Хилл, Энтони; Кинтас, Луи В. (1969), «Минимальное количество точек для правильных асимметричных графов», Технический университет Федерико Санта-Мария. Scientia , 138 : 103–111, MR 0266818 .
- ^ Буссемейкер, ФК; Кобельич, С.; Цветкович, Д.М.; Зайдель, Дж. Дж. (1976), Компьютерное исследование кубических графов , отчет EUT, том. 76-WSK-01, кафедра математики и информатики, Технологический университет Эйндховена
- ^ Фрухт, Р. (1939), «Построение графов с заданной абстрактной группой». , Compositio Mathematica (на немецком языке), 6 : 239–250, ISSN 0010-437X , Zbl 0020.07804 .
- ^ Квинтас, Луи В. (1967), «Экстремумы, касающиеся асимметричных графов», Журнал комбинаторной теории , 3 (1): 57–82, doi : 10.1016/S0021-9800(67)80018-8 .
