Непомеченные графы

Подстановки. Подстановкой называется биекция множества на себя. Подстановка на множестве записывается в виде

,

при этом – перестановка элементов . Подстановка на конечном множестве может быть представлена ориентированным графов с множеством вершин и ребрами для всех . В этом графе у каждой вершины х полустепени исхода и захода равны 1. Поэтому граф подстановки состоит из непересекающихся ориентированных циклов (в нем могут быть петли – это циклы длины 1). На рисунке 4 показан граф подстановки

.

Рис. 4.

Набор чисел , где – количество циклов длины 1, – циклов длины 2,..., – циклов длины , называется цикловой структурой подстановки. Эти числа должны удовлетворять равенству . Число подстановок на множестве из элементов с цикловой структурой равно

.

Автоморфизмы. Автоморфизм – подстановка на множестве вершин графа, сохраняющая отношение смежности (две вершины смежны тогда и только тогда, когда смежны их образы). Иначе говоря, автоморфизм – это изоморфизм графа на себя. Множество автоморфизмов данного графа обозначается через .

Каким числом способов можно абстрактный граф с вершинами превратить в помеченный граф с множеством вершин ? Иначе: сколько различных графов можно получить, переставляя пометки вершин у данного помеченного графа ? Это зависит от графа: из можно получить 12 разных графов, из – 8, а для любая перестановка дает тот же самый граф. В общем случае число различных помеченных графов, которые можно получить из графа , дает формула

.

Орбиты пар. Пусть – подстановка на множестве . Относительно этой подстановки множество всех неупорядоченных пар различных элементов из разбивается на орбиты – одну пару можно превратить в другую, действуя на нее (может быть, многократно) подстановкой тогда и только тогда, когда обе пары принадлежат одной орбите. Если является автоморфизмом графа G, то все пары вершин из одной орбиты одновременно смежны или несмежны в этом графе. Обозначим число орбит пар относительно подстановки через . Любой граф, для которого эта подстановка является автоморфизмом, можно получить следующим образом: каждой орбите приписать одно из значений 0 или 1. Все пары вершин из орбиты объявить смежными, если этой орбите приписана 1, и несмежными, если ей приписан 0. Следовательно, число графов, для которых является автоморфизмом, равно .

Число зависит только от цикловой структуры подстановки. Оно равно

,

где – наибольший общий делитель чисел и , – остаток от деления числа на 2.

Число графов. Число абстрактных графов с вершинами обозначим через . Построим граф , имеющий вершины двух типов. Вершины первого типа соответствуют графам с множеством вершин , вершины второго – подстановкам на этом множестве. Вершину-граф соединим ребром с вершиной-подстановкой, если эта подстановка является автоморфизмом этого графа. Подсчитаем двумя способами число ребер в графе . С одной стороны, подстановка является автоморфизмом графов. Поэтому число ребер в графе равно

,

суммирование ведется по всем подстановкам на множестве . С другой стороны, из вершины, соответствующей графу , выходит ребер. Объединим все графы, изоморфные графу , в один класс, представляющий один абстрактный граф. Из каждой вершины-графа этого класса выходит ребер, а всего в классе имеется графов. Следовательно, всего из вершин этого класса выходит ребер. Так как имеется классов, то число ребер в графе равно . Получаем равенство

.

Учитывая формулу для , получаем формулу для числа абстрактных графов:

.

Задачи

2.1. Сколько имеется неориентированных графов с n вершинами, в которых допускаются

петли?

2.2. Найдите число ориентированных графов с n вершинами, в которых

а) возможны петли;

б) петель нет;

в) петель нет и каждая пара различных вершин соединена не более чем одним ребром;

г) возможны петли и каждая пара вершин соединена не более чем одним ребром;

д) петель нет и каждая пара различных вершин соединена точно одним ребром.

2.3. Найдите число графов с n вершинами, в которых возможны и ориентированные и

неориентированные ребра (но не петли), причем две вершины могут быть соединены

не более чем одним ребром.

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

пары вершин имеется не более четырех соединяющих эти вершины ребер.

2.5. Найдите число графов с n вершинами, в которых а) данные k вершин являются

изолированными (имеют степень 0); б) нет изолированных вершин. Верно ли, что

почти все графы не имеют изолированных вершин?

2.6. Если к графу с вершиной добавить еще одну вершину и соединить ее ребрами со

всеми вершинами нечетной степени, то получится граф с вершинами, в котором

степени всех вершин четны. Сколько имеется графов, у которых степени всех вершин

четны. Верно ли, что почти все графы имеют вершины нечетной степени?

2.7. Сколько имеется графов с вершинами, у которых степень каждой вершины равна 1?

2.8. Сколько различных помеченных графов можно получить, добавляя одно новое

ребро к графу ?

2.9. Сколько различных абстрактных графов можно получить, добавляя одно ребро к

графу ?

2.10. Сколько различных помеченных графов можно получить, добавляя одно ребро к

графу ?

2.11. Сколько различных абстрактных графов можно получить, добавляя одно ребро к

графу а) ? б) ?

2.12. Сколько различных помеченных графов можно получить, перенумеровывая

вершины графа а) ? б) ? в) ?

2.13. Сколько различных автоморфизмов имеет граф а) ; б) ; в) ; г) ?

2.14. Найдите по возможности малый граф, не имеющий нетривиальных автоморфизмов.

2.15. Опишите единственный нетривиальный автоморфизм графа с помощью

формулы (нумерация вершин начинается с 1).

2.16. Выразите формулами два автоморфизма графа , переводящих вершину i в

вершину j (нумерация вершин начинается с 0).

2.17. Пусть – двоичный вектор. На множестве вершин графа

рассмотрим преобразование, переводящее вершину в вершину

, ( – сумма по модулю 2). Докажите, что оно

является автоморфизмом этого графа.

2.18. Примените формулу для числа абстрактных графов при .