плотный граф

Пло́тный граф — граф, в котором число рёбер близко к максимально возможному у полного графа с числом вершин : Граф, имеющий малое число рёбер, принято называть разреженным графом. Вообще говоря, разница между разреженным и плотным графом условна и зависит от контекста. Для неориентированного простого графа (рёберная) плотность графа с числом вершин определяется как отношение числа его рёбер к числу рёбер полного графа: . Максимальное число рёбер равно так что максимальная плотность графа равна 1 (для полных графов) и минимальная равна 0 — для несвязанного графа.