Плотный граф
граф, в котором число рёбер близко к максимальному / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Плотный граф?
Кратко изложите эту статью для 10-летнего ребёнка
ПОКАЗАТЬ ВСЕ ВОПРОСЫ
Пло́тный граф — граф, в котором число рёбер близко к максимально возможному у полного графа с числом вершин
:
Граф, имеющий малое число рёбер, принято называть разреженным графом.
Вообще говоря, разница между разреженным и плотным графом условна и зависит от контекста.
Для неориентированного простого графа (рёберная)[1] плотность графа с числом вершин определяется как отношение числа его рёбер
к числу рёбер полного графа:
.
Максимальное число рёбер равно так что максимальная плотность графа равна 1 (для полных графов) и минимальная равна 0 — для несвязанного графа[2].