Асимметричный граф - Asymmetric graph
В теория графов, раздел математики, неориентированный граф называется асимметричный граф если у него нет нетривиальных симметрий.
Формально автоморфизм графа является перестановка п его вершин со свойством, что любые две вершины ты и v смежны тогда и только тогда, когда п(ты) и п(v) смежны. отображение идентичности графа на себя всегда является автоморфизмом и называется тривиальный автоморфизм графа. Асимметричный граф - это граф, для которого нет других автоморфизмов.
Примеры
Самая маленькая асимметричная не-тривиальные графы имеет 6 вершин.[1] Самая маленькая асимметричная регулярные графики иметь десять вершин; существуют асимметричные графы с десятью вершинами, которые являются 4-регулярными и 5-регулярными.[2][3] Один из пяти самых маленьких асимметричных кубические графы[4] двенадцать вершин Граф Фрухта открыт в 1939 году.[5] По усиленной версии Теорема Фрухта асимметричных кубических графов бесконечно много.
Характеристики
Класс асимметричных графов замкнут относительно дополняет: график грамм асимметричен тогда и только тогда, когда есть его дополнение.[1] Любой п-вершинный асимметричный граф можно сделать симметричным, добавляя и удаляя в общей сложности не более п/ 2 + o (п) края.[1]
Случайные графики
Доля графиков на п вершины с нетривиальным автоморфизмом стремятся к нулю при п растет, что неофициально выражается как "почти все конечные графы асимметричны ». Напротив, опять же неформально,« почти все бесконечные графы симметричны ». Более конкретно, счетный бесконечный случайные графы в Модель Эрдеша – Реньи с вероятностью 1 изоморфны высокосимметричному График Rado.[1]
Деревья
Самая маленькая асимметричная дерево имеет семь вершин: он состоит из трех путей длиной 1, 2 и 3, соединенных в общей конечной точке.[6] В отличие от графов, почти все деревья симметричны. В частности, если дерево выбирается равномерно случайным образом среди всех деревьев на п помеченные узлы, то с вероятностью, стремящейся к 1 как п увеличивается, дерево будет содержать два листа, смежных с одним и тем же узлом, и будет иметь симметрии, меняющие местами эти два листа.[1]
Рекомендации
- ^ а б c d е Эрдеш, П.; Реньи, А. (1963), «Асимметричные графики» (PDF), Acta Mathematica Hungarica, 14 (3): 295–315, Дои:10.1007 / BF01895716, заархивировано из оригинал (PDF) на 2017-07-06, получено 2010-04-22.
- ^ Барон, G .; Имрих В. (1969), "Asymmetrische Regäre Graphen", Acta Mathematica Academiae Scientiarum Hungaricae, 20: 135–142, Дои:10.1007 / BF01894574, МИСТЕР 0238726.
- ^ Гевиртц, Аллан; Хилл, Энтони; Квинтас, Луи В. (1969), "Минимальное количество точек для регулярных асимметричных графов", Universidad Técnica Federico Santa Maria. Scientia, 138: 103–111, МИСТЕР 0266818.
- ^ Bussemaker, F.C .; Cobeljic, S .; Цветкович, Д. М .; Зайдель, Дж. Дж. (1976), Компьютерное исследование кубических графов, Отчет EUT, 76-WSK-01, кафедра математики и вычислительной техники, Технологический университет Эйндховена
- ^ Фрухт, Р. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe"., Compositio Mathematica (на немецком), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.
- ^ Квинтас, Луи В. (1967), "Экстремумы относительно асимметричных графов", Журнал комбинаторной теории, 3 (1): 57–82, Дои:10.1016 / S0021-9800 (67) 80018-8.