Полные, насыщенные, регулярные и взвешенные графы

Полный — скелетный неограф, в котором каждая пара вершин соединена ребром. Если n - количество вершин, m - ребер, то

Насыщенный — полный граф, в каждой вершине которого есть петля.

Регулярный — граф, степени всех вершин которого равны.

Взвешенный — граф, вершинами или ребрам (дугам) которого приписаны веса.

Вес — значение, поставленное в соответствие данному ребру (вершине) взвешенного графа. Обычно, вес - вещественное число, в таком случае его можно интерпретировать как длину ребра.