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

Если вершины и принадлежат некоторому ребру , то говорят, что это ребро инцидентно вершинам и .

Такие вершины называются смежными вершинами.

Петлёй называется ребро, если оно инцидентно одной и той же вершине.

Изолированнойназываетсявершина,не инцидентная ни одному ребру.

Нуль- графомназывается граф, в котором все вершины изолированные.

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

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

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

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

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

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

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

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

123 4

Дата добавления: 2017-02-13; просмотров: 2578;