Асимметричный граф - Asymmetric graph

Восемь 6-вершинных асимметричных графов
В Граф Фрухта, один из пяти самых маленьких асимметричных кубические графы.
Семейства графов, определяемые их автоморфизмами
дистанционно-переходный→дистанционно-регулярный←строго регулярный
↓
симметричный (дуго-транзитивный)←т-переходный, т ≥ 2кососимметричный
↓
(если подключен)
вершинно- и реберно-транзитивные		→реберно-транзитивные и регулярные→ребро-транзитивный
↓↓↓
вершинно-транзитивный→обычный→(если двудольный)
двурегулярный
↑
Граф Кэли←нулевой симметричныйасимметричный

В теория графов, раздел математики, неориентированный граф называется асимметричный граф если у него нет нетривиальных симметрий.

Формально автоморфизм графа является перестановка п его вершин со свойством, что любые две вершины ты и v смежны тогда и только тогда, когда п(ты) и п(v) смежны. отображение идентичности графа на себя всегда является автоморфизмом и называется тривиальный автоморфизм графа. Асимметричный граф - это граф, для которого нет других автоморфизмов.

Примеры

Самая маленькая асимметричная не-тривиальные графы имеет 6 вершин.[1] Самая маленькая асимметричная регулярные графики иметь десять вершин; существуют асимметричные графы с десятью вершинами, которые являются 4-регулярными и 5-регулярными.[2][3] Один из пяти самых маленьких асимметричных кубические графы[4] двенадцать вершин Граф Фрухта открыт в 1939 году.[5] По усиленной версии Теорема Фрухта асимметричных кубических графов бесконечно много.

Характеристики

Класс асимметричных графов замкнут относительно дополняет: график грамм асимметричен тогда и только тогда, когда есть его дополнение.[1] Любой п-вершинный асимметричный граф можно сделать симметричным, добавляя и удаляя в общей сложности не более п/ 2 + o (п) края.[1]

Случайные графики

Доля графиков на п вершины с нетривиальным автоморфизмом стремятся к нулю при п растет, что неофициально выражается как "почти все конечные графы асимметричны ». Напротив, опять же неформально,« почти все бесконечные графы симметричны ». Более конкретно, счетный бесконечный случайные графы в Модель Эрдеша – Реньи с вероятностью 1 изоморфны высокосимметричному График Rado.[1]

Деревья

Самая маленькая асимметричная дерево имеет семь вершин: он состоит из трех путей длиной 1, 2 и 3, соединенных в общей конечной точке.[6] В отличие от графов, почти все деревья симметричны. В частности, если дерево выбирается равномерно случайным образом среди всех деревьев на п помеченные узлы, то с вероятностью, стремящейся к 1 как п увеличивается, дерево будет содержать два листа, смежных с одним и тем же узлом, и будет иметь симметрии, меняющие местами эти два листа.[1]

Рекомендации

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