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


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

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

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

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

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

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

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

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

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

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

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

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

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

 



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


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.009 сек.