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

Если вершины Связь между вершинами и рёбрами графа - №1 - открытая онлайн библиотека и Связь между вершинами и рёбрами графа - №2 - открытая онлайн библиотека принадлежат некоторому ребру Связь между вершинами и рёбрами графа - №3 - открытая онлайн библиотека , то говорят, что это ребро инцидентно вершинам Связь между вершинами и рёбрами графа - №1 - открытая онлайн библиотека и Связь между вершинами и рёбрами графа - №2 - открытая онлайн библиотека .

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

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

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

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

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

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

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

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

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

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

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

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