В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 8
Текст из файла (страница 8)
Произвольная подстановка ц на множестве вершин графа 6, сохраняющая отношение смежности, т. е. такан, что образы ср(и) и ср(о) вершин и и о сменвны тогда п только тогда, когда смежны сама воршпны и и о, называется автоморфизмом графа 6. 42 Иными словами, автоморфизм графа — это изоморфизм графа на себя. Любой граф 6 имеет по меньшей мере один автоморфизм — тождественное преобразование е: 1т6- )т6, при котором е(о)= о для любой вершины о.
Очевидно, что если гр — автоморфизм графа 6, то и обратная подстановка ср ' также является автоморфизмом, если же подстановки ср и ф обе суть автоморфизмы, то и пх произведение ~рф — азтоморфизм. Поэтому верно следующее (важное, хотя и очевидное) У т в е р ж д е н н е 11.1. Множество всех автоморфигмов графа относительно операиии умиохсеп»ся подстаповок является группой. Группа автоморфизмов рафа 6 обозначается через Ап1 6.
Очевидно также Утверждение 11.2. Всякий автоморфигм графа 6 является такясе автоморфигмом дополнительного графа 6, т. е. Апс 6 = Ап$6. Поскольку среди двух графов 6 и С хотя бы одни является связным, то в силу утверждения 11.2, когда мы имеем дело с группой автоморфизмов, достаточно рассматривать лишь связные графы.
Введем важное понятие орбиты группы подстановок. Пусть à — произвольнан группа подстановок на множестве К Определим на )т бинарное отношение —, положив и — и для и, о ~н 1т тогда и только тогда, когда в Г существует такал подстановка г, что г(и)= о. Очевидно, что отношение — является отношением эквивалентности и, следовательно, мнол«ество»т разбивается на классы эквивалентных элементов: все элементы, входящие в один класс, переводятся подстановками из группы Г друг в друга, а элементы из разных классов друг в друга не пореводятся.
Эти классы называютсн орбит ми группы Г. Разбиение множества вершин графа 6 на орбиты группы Ап» 6 — важная задача. В сущности, применение к графу автоморфизма означает перенумерацню его вершин, причем отношение смежности должно сохраняться. Поэтому для л»обого автоморфнзма ~р у вершины графа о и ее образа гр(о) «все одинаково» (степени равны, графы, порожденные окружениями, изоморфны и т. д.). Так что орбиты группы Апг 6 — это просто классы «одинаковых» вершин. Более того, известно, что проблема распознавания принадлежности двух вершин произвольного графа одной орбите его группы автоморфнзмов и проблема изоморфизма графов эквивалентны в том смысле, что любой алгоритм, эффективно решающий одну из этих проблем, может быть преобразован в эффективный алгоритм для другой (см., напр«имер (18)).
К сожалению эффективные алгоритмы для решения этих двух проблем не пзвостпы (о том, какие алгоритмы считаются эффективными, см. гл, Х11), Трудно сказать что-лпбо определенное о строении группы автоморфпзмов произвольного графа. Она может быль и «малой», и «большой». Пайдем, например, Ап1 С 1 для графа С, изобра»кенного на рис. 11.1. Очевидно, что любой автоморфизм либо оставляет неподвижной вершину 1, либо переставляет ее с вершиной 3.
В любой ситуации вершины 2 и 4 либо обе неподс 5 впжны, либо переводятся друг в друга. Рас. 113 Итак, Ап1 С состоит из четырех эле- ментов: е, транспозпцпй (1,3) и (2,4) и произведения этих трапспозпций — (1,3) (2,4). Очевидно, что каждый пз двух графов, нзображопн»лх на рпс. 11.2, имеет лишь один автоморфизм — тождественный, С другой стороны, очевидно, что группой автоморфпзмов полного графа К является вся симметрическая группа Я . О 1936 г. известен следующий вопрос Д.
Кенига: какие конечные группы являются группамп автоморфизмов графов? Этот вопрос можно интерпретировать двояким образом, Первый вариант: какие конечные группы Рис. 11.2 изоморфны группам автоморфизмов графов? На этот вопрос почти сразу же ответил Р. Фрухт (1938 г.). Т е о р е м а Ф р у х т а. Каждая конечная группа игог«орфна группе авто»яорфиг»иов некоторого графа. > Пусть à — группа порядка и) 1 (для и = 1 выше приводнлпсь примеры). Построим граф С описанным пнже способом. В качестве исходного множества вершин возьмем мпо»кество всех элементов группы Г.
Каждую упорядоченную пару (и, о) несовпадающпх вершин соединим простой цепью Р„. длины 3, добавляя всякий раз по две новые вершины а„, и Ь;. Р „=(и, а „, д„„, и). За- 44 тем к каждой из вершин а„„«прикленм» простую цепь Р(а, и, и) длины 1 (а, и, о), все вершины которой, исключая а..,.— новые. Аналогично построим цепи Р(Ь, и, г) длины 1 (Ь, и, п). При этом будем соблюдать следующее условие: длины всех цепей попарно различны всегда, кроме случая, когдаи о = и, лы и, и, ип п~ ~ Г.
В последном случае должно быть 1(а, и, о)=1(а, ип щ), 1(Ь, и, о)=1(Ь, ип г~), (1) Построенный таким образом граф обозначим буквой С. (На рпс $1.3 показаны соответствутощпе графы для Ряс. 11.3 л = 2 и 3. В этой ситуации à — циклическая группа: Г =(и, о' = е) при и = 2, Г = (о, о', пз = е) прн л = 3.) Докажем, что группы Ап$6 и Г изоморфны. Вначале фиксируем в Г какой-либо элемент и~ и следующим образом определим отображение 1.: УС вЂ” г'С.
Для х ~ Г 1 (х) = «сх — произведение элементов группы; вершины цепи Р(а, и, с) переводятся в вершины цепи Р(а, «си, и г), причем сохраняется последовательность вершин в цепи, т. е. 1 (а„„)= а<„.„п „, н т. д.; аналогично для цепи Р(Ь, юи, ис). Прямая проверка подтверждает, что 1 ш Ап1С. Теперь докажем равенство Ап1С=П.,: ю~Г). (2) Пусть ср — пропзвольпый автоморфизм графа С. Очевидно, что ~р все концевые вершины и, следовательно, все цепи Р„„переводит друг в друга.
Поэтому автоморфизм ~р переставляет друг с другом вершины вида а„„, а также Рвс. 11.5 Рис. 11.4 вершины вида Ь „. Следовательно, и элементы группы Г переставляются друг с другом, При этом из условии (1) следует, что если <р(и) = ип ~р(и) = вп то и п = и, вт для всех и, и ~ Г. Из этого равенства, положив <р(е)= и, получим <р(х)= юх для любого х ~н Г, т. е. «с = 1. Равенство (2) доказано. Далее, определим отображение «)с à — Ап1С, полол«ив «р(х) = 1„для любого х ~ Г. Очевидно, что отображение «Р является изоморфизмом групп Г и Апс С. З Конструкция, приведенная в предыдущем доказательстве, неэкономна в том смысле, что приводит к графам с болыпим числом элементов.
Как правило, эти графы можно «уменьшить». Например, при п = 2, 3 вместо графов, приведенных па рис. 11.3, можно взять графы на рнс. 11.4. Группой автоморфизмов графа, показанного па рис. 11.5, также является циклическая группа порядка 3. Можно указать примеры групп подстановок, которые хотя н изоморфны по теореме Фрухта группам автоморфизмов графов, по сами таковыми яе являются.
Рассмотрим зпакопеременную группу А., состоящую из всех четных подстановок (и > 3). Пусть А„— Ап1 С. Легко заме- 46 тить, что группа А„дваасдьс транзитивсса, т. е. для любых с, с, к, 1 св )тС, с чь у, й Ф 1, в Л„существует такая подстановка ср, что ср(с) = Й, ср(1) = й Если ср — автоморфнзм некоторого графа С, то в С либо любая пара вершин смежна, т. е.
С = К„, либо любая пара вершин не смежна, т. е. С = О„. В обоих случаях Асс«С = д ~ Л . Естественно возникает неизмеримо более сло»кный вариант вопроса Д. Кенига. Этот, по-видимому, далекий от решения вариант известен как П р о б л е м а К е н и г а. Уста»совать, какие условия необходимы и достаточны, чтобы для гадассной на многкестве У зруппы подстассовок Г существовал такой граф С с многкеством версаип У, сто Ап« С = Г. 5 12.
«Почти все» графы В этом параграфе приводятся некоторые результаты, характеризующие свойства графов прп большом числе вершин, т. е. в асимптотике. Эти свойства формулируются в терминах «почти всех графов» и отражасот тем самым типичный случай. Обозначим через У(п) мнонсество всех помеченных простых графов с множеством вершин У = (1, 2,, и). Как отмечалось в з 1, ~У (и) ~ = 2 ' . (") Пусть Р— некоторое свойство, которым каждый отдельно взятый граф из У(п) может обладать или не обладать. Через УР(п) обозначим множество тех графов из У(п), которые обладают свойством Р.
Будем говорит«в что почти все графы (почти каисдый граф) обладают свойством Р, если Пш ! У Р (п) )с'( У (и) ) = 1, о и почти нет графов, обладасощих свойством Р, если 1пп / УР (и) и У (п) / = О. е-~ Ясно, что если почти все графы обладают свойством Р, то почти нет графов, пе обладающих свойством Р. К настоящему времени получены результаты о большом количестве свойств графов в терминах «почти всех графов».
Приведем нокоторые нз этих результатов. Те ор ем а 12.1. Почти все графы связны. 1> Обозначим через У„(п) множество связных графов из У(п), а через У,(п) — множество тех графов из У(п), 47 в каждом из которых имеется по крайней мере одна компонента порядка г. Тогда справодлпво неравенство [о/21 ! Уз, (п) ! ) ! У (и) ! — ~, '! У, (п) !. (1) Далее рассмотрим следу ющпй прием построения графов: 1) мпон[ество [г разбиваем па подмножества [т~ и ['и тде 
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
