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