Полные графы

Определение. Пусть граф имеет n вершин. Если каждые две различные вершины графа соединены ребром, то граф называют полным. Полный граф, содержащий n вершин, обозначают K_n. Примеры полных графов с количеством вершин n = 1, 2, 3, 4, 5 показаны на рис.1.10.

Рис. 1.10. Полные графы с количеством вершин n = 1, 2, 3, 4, 5

Все элементы матрицы смежности полного графа K_n, кроме нулевых диагональных, равны 1.

Определение. Кликами графа G = (V, X) называют полные подграфы, входящие в G. Обозначают С(G). Число вершин в С(G) называют степенью клики. Обозначают d(C).

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

Задачи

1. Найти число рёбер в полном графе К_n .

2. Найти общее число всех попарно различных простых циклов в полном графе К_n с пронумерованными вершинами при условии, что начало цикла не фиксируется, а направление обхода учитывается.

3. Все вершины полного графа К_n пронумерованы. Сколько существует в нем попарно различных клик степени (n – 1), если порядок вершин в них не имеет значения?

4. Все рёбра полного графа К_n пронумерованы. Им присваивается ориентация. Сколько существует попарно различных вариантов ориентирования рёбер в К_n?