Полное и разреженное графы отличаются количеством связей между вершинами.

Полный граф (полносвязный) — это граф, в котором каждая вершина соединена с каждой другой. 1 В таком графе количество рёбер примерно равно количеству вершин, возведённому в квадрат. 2

Разреженный граф — это граф, в котором количество рёбер намного меньше, чем количество вершин в квадрате. 2 Матрица смежности такого графа в основном заполнена нулями. 23

В контексте сетевой архитектуры разреженный граф может означать, что по мере роста графа число связей в нём растёт пропорционально или медленнее числу вершин. 1

Таким образом, полное граф характеризуется высокой плотностью связей, в то время как разреженный граф имеет более низкую плотность.