Полный график
- Полный граф – простой неориентированный граф с уникальной связью между каждой парой различных вершин.
- Полный орграф – ориентированный граф с уникальной связью между каждой парой различных вершин в каждом направлении.
- Теория графов обычно датируется работой Леонарда Эйлера “Семь мостов Кенигсберга” (1736 год).
- Рисунки полных графов с вершинами в точках правильного многоугольника появились в XIII веке в работе Рамона Льюлла.
- Полный граф Kn имеет n (n – 1) / 2 ребра и является правильным графом степени n – 1.
- Все полные графы являются своими собственными максимальными кликами и максимально связаны.
- Дополнительный граф полного графа – пустой граф.
- Если каждому ребру полного графа задана ориентация, результирующий ориентированный граф называется турниром.
- Kn может быть разложено на n деревьев Ti, и гипотеза Рингеля задает вопрос о возможности разложения полного графа K2n + 1 на копии любого дерева с n ребрами.
- Полный граф с n вершинами представляет собой ребра (n – 1)-симплекса и играет важную роль в геометрии и топологии.
Полный текст статьи: