Связь между вершинами и рёбрами графа.

Тривиальнымназывается граф, состоящий из одной вершины.

Мультиграфомназывается граф, в котором есть вершины, соединённые с двумя или большим числом вершин.

Параллельными называют различные рёбра, имеющие две общие вершины.

Кратностью пары вершин называется число соединяющих их рёбер..

Граф без петель и кратных рёбер называется простымили обыкновенным.

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

Пример полного графа

Если граф не является полным, его можно преобразовать в полный, добавив соответствующие рёбра.

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