Полный граф
простой граф, в котором каждая пара различных вершин смежна / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Полный граф?
Кратко изложите эту статью для 10-летнего ребёнка
По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.[1] По́лный ориенти́рованный граф — ориентированный граф, в котором каждая пара различных вершин соединена парой ребер с противоположными ориентациями.[2] Принято считать, что теория графов берет свое начало с решения Леонардом Эйлером задачи о семи кёнигсбергских мостах, датированного 1736 годом, однако изображения полных графов, вершины которых располагаются в вершинах правильных многоугольников, встречаются ещё в 13 веке, в работе Раймунда Луллия.[3] Подобные рисунки иногда называют мистическими розами.[4]
Полный граф | |
---|---|
| |
Вершин | n |
Рёбер | |
Диаметр | |
Обхват | |
Автоморфизмы | n! (Sn) |
Хроматическое число | n |
Хроматический индекс |
n если n - нечётное, иначе n − 1 |
Спектр | |
Свойства | |
Обозначение | Kn |
Медиафайлы на Викискладе |
Обычно полный граф с вершинами обозначается через . Некоторые источники утверждают, что буква в этом обозначении является сокращением от немецкого слова нем. komplett,[5] в переводе на русский – «полный, целый», однако оригинальное название полного графа на немецком, нем. vollständiger Graph, не содержит буквы . По другой версии, такое обозначение полному графу было дано в честь Казимежа Куратовского, подчеркивая его вклад в развитие теории графов.[6]