Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Полные графы и их свойства.
Дополнение графа. Самодополнительные графы

На главную Математический раздел Криптография и т.д. Новости

Полный граф - граф, каждая пара вершин которого соединена ребром (или парой дуг - по одной в каждую сторону - если давать определение для орграфа). Полный граф с n вершинами содержит n(n-1)/2 рёбер. На рис. 1 приведена пара примеров полных графов. Полный граф с 4 вершинами содержит 6 рёбер (проверьте по рисунку и формуле), а с 5 вершинами - 10 рёбер.

Полные графы с n<5 вершинами являются планарными графами, то есть могут быть нарисованы так, чтобы рёбра пересекались только в вершинах. Полный граф с 5 вершинами не является планарным графов. Более крупные полные графы содержат полный граф с 5 вершинами в качестве подграфа, потому тоже не являются планарными графами в силу теоремы Куратовского-Понтрягина.

Также отметим ещё одно свойство полного графа (которое, к сожалению, часто не рассматривается в разных источниках). Пусть в полном графе с n вершинами мы выбрали две вершины A и B. При любом выборе число всевозможных путей из A в B, при которых мы никакую вершину не проходим дважды (то есть простых путей), вычисляется по формуле

Рассмотрим пример n=4 (см. рис. 2). Выберем вершины номер 1 и 4. Получим простые пути 1-4, 1-2-4, 1-3-4, 1-2-3-4, 1-3-2-4, то есть f(4)=5. По формуле: f(4)=2!(1/0! + 1/1! + 1/2!)= 2(1 + 1 + 0,5) = 5. Доказательство формулы основано на том, что остаётся n-2 вершин, отличных от A и B, среди них мы можем выбрать от 0 до n-2 вершин, причём важно, в каком порядке мы их выбрали, а не только какие вершины выбраны. Дальше мы используем комбинаторику, определяя, сколько существует вариантов выбора k объектов из n с учётом, что порядок выбора существенен.

Количество гамильтоновых циклов в полном графе с n вершинами составляет (n-1)! = (n-1)(n-2)...1. Доказательство - по той же схеме, что и предыдущей формулы.

Также с полным графом связано такое понятие, как дополнение графа. Дополнением графа G (или обратным графом) называется граф, в котором: 1) вершины те же, что и у G; 2) рёбра - такие, которых "не хватает" в G, чтобы он стал полным.

Заметим следующие свойства дополнения графа с n вершинами. Если у графа m рёбер, то у его дополнения n(n-1)/2 - m рёбер. Если некоторая вершина графа имеет x смежных вершин, то соответствующая вершина дополнительного графа будет иметь n-1-x смежных вершин. Может получиться так, что сам граф и дополнение графа - в принципе один и тот же граф, просто вершины пронумерованы по-разному. В этом случае граф называется самодополнительным графом.

Для желающих составить свои самодополнительные графы сделаем небольшую наводку. У самодополнительного графа с n вершинами должно быть вдвое меньше рёбер, чем у с n вершинами, то есть n должно быть таким, чтобы число n(n-1)/4 было целым. Это означает, что n должно быть кратным 4 либо давать остаток 1 при делении на 4. Так, n = 4 или n = 5 подходит, а n = 3 или n = 6 - нет.

copyright © Исканцев Н.В., 2014

К математическому разделу
На главную
X