§ 32. Основные понятия для неориентированных графов

Ребро. Ребром графа называется такая пара элементов что

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

Ребро обозначается

или

Множество ребер графа обозначается через

Рис. 129.

Множество вершин вместе с множеством ребер определяют неориентированный граф, который обозначается через

Каждому графу можно однозначно сопоставить неориентированный граф Обратное, очевидно, неверно. Неориентированному графу соответствуют различных графов где число ребер, 5 — число вершин.

Например, граф на рис. 129 имеет 14 дуг и 8 ребер.

Цепь. Цепью называется такая последовательность ребер что каждое ребро соприкасается одним из концов с ребром (если оно существует), а другим — с (если оно существует). Цепь можно обозначить последовательностью вершин, которые она содержит. Можно рассматривать как конечные, так и бесконечные цепи.

Например, для графа на рис. 129

Длина цепи. Длиной цепи называется число ребер, которые она содержит.

Простая цепь. Элементарная цепь. Эти понятия определяются точно так же, как соответствующие понятия для путей, только вместо дуг рассматриваются ребра.

Цикл. Циклом называется конечная цепь, которая начинается и заканчивается в одной и той же вершине.

Например, для графа на рис. 129 цепи являются циклами.

Понятие цикла графа не следует смешивать с понятием цикла, определенным в § 16 и относящимся к подстановкам.

Иногда на множестве циклов графа рассматривают отношение эквивалентности, считая эквивалентными циклы, проходящие одни и те же вершины в одинаковом порядке. Например, для графа на рис. 129 .

Простой цикл. Элементарный цикл. Эти понятия определяются точно так же, как соответствующие понятия для контуров, только вместо дуг рассматриваются ребра.

Связный граф. Граф называется связным, если для всех всегда существует цепь из

Сильно связный граф всегда связен.

Например, граф на рис. 120 связный, не не сильно связный, граф на рис. 129 — не связный.

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

Например, граф на рис. 129 имеет две компоненты связности:

Пусть компоненты связности, порожденные подмножествами вершин Тогда

а также

Степень вершины. Степенью вершины называется число ребер, для которых одним из концов служит (другой конец отличен от она обозначается через Например, для графа на рис. 129

Регулярный подграф степени d. Подграф называется регулярным степени если степень каждой его вершины равна

Например, граф на рис. 130 имеет регулярный подграф степени 3, где .

Гамильтонова цепь. Гамильтонов цикл. Эти понятия определяются точно так же, как соответствующие понятия для путей и контуров, только вместо дуг рассматриваются ребра.

Рис. 130.

Рис. 131.

Рис. 132.

Замечания относительно неориентированных графов. 1) Как отмечалось, каждому графу можно сопоставить неориентированный граф, если дуги заменить ребрами. Например, ориентированному графу на рис. 131, а также графу на рис. 133 сопоставляется один и тот же неориентированный граф на рис. 132. Не следует смешивать обозначения и

Рис. 133.

Рис. 134.

2) В некоторых случаях можно неориентированный граф не отличать от симметрического графа без петель, которому он соответствует (например, граф на рис. 134 и граф на рис. 132). Но такое отождествление не всегда удобно и не всегда возможно. Понятие неориентированности не обязательно совпадает с понятием двусторонней ориентированности.

Например (как мы увидим в § 60), в транспортной сети симметрия некоторых дуг может сочетаться с несимметрией их пропускных способностей.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)