Дискретная математика 3 (стр. 7 из 10)

Таким образом, все вершины графа можно разбить на непересекающиеся классы вершин связанных между собой отношением достижимости. И каждый такой класс будет компонентой неориентированного графа. То есть две различные компоненты неориентированного графа не пересекаются (не имеют общих вершин и общих ребер).

В ориентированном графе отношение достижимости не является отношением эквивалентности (не всегда выполняется симметричность) и поэтому компоненты ориентированного графа могут пересекаться.

#10.

Граф G не связный.

Он состоит из трех компонент.

В примере 9 все графы связные.

¬Этот граф связный.

Не связный, так как вершина v₂ и v₅ не достижимы друг из друга. ®

Определение 11. Ориентированный граф называется сильно связным, если для любых двух его вершин u и v вершина v достижима из u и вершина u достижима из v (u и v взаимно достижимы). Бикомпонента ориентированного графа – это его максимальный сильно связный подграф.

#11.

Граф G не связный. Бикомпонентой является подграф G₁, порожденный множеством вершин {v1, v2, v3}.

G₁ – сильно связный, ведь:

v₁ достижима из v₂;

v₁ достижима из v₃;

v₂ достижима из v₁;

v₂ достижима из v₃ (v₃, v₁, v₂);

v₃ достижима из v₁;

v₃ достижима из v₂.

Подграф G₁ является максимальным сильно связным. Вершины v₄ и v₅ уже ни с одной из вершин v₁, v₂, v₃ не взаимно достижимы.

Определение 12. Граф, у которого множество ребер пусто E(G)=Æ, называется вполне несвязным (или пустым)графом.

#12.

Определение 13. Простой граф, в котором любые две вершины смежны, называется полным графом. Обозначается К_n, где n – число вершин.

#13.

Определение 14. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным. Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3, называются кубическими (или трехвалентными).

#14.

¬ Кубический граф

Полный регулярный граф степени 5 ®

§4. Способы представления графов.

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

Определение 15.Матрицей смежности ориентированного графа с n вершинами называется матрица A=(a_ij), i, j=1, 2, …, n, в которой

.

Для неориентированного графа матрица смежности определяется следующим образом:

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

#15. Для ориентированного графа:

Для соответствующего неориентированного графа:

Заметим, что в А в i-ой строке количество единиц равно полустепени исхода dg⁺v_i, а количество единиц в i-ом столбце – полустепени захода dg^-v_i.

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

Определение 16.Матрицей инцидентности графа с n вершинами и m ребрами называется матрица В=(b_ij), i=

, j= , строки которой соответствуют вершинам, а столбцы – ребрам. Элементы матрицы равны для неориентированного графа:

Для ориентированного графа:

#16.

Строки соответствуют вершинам, расположенным по порядку, а столбцы – дугам в таком порядке: (1,2), (1,3), (2,1), (2,3), (2,4), (2,5), (2,7), (3,5), (4,1), (4,5), (4,7), (6,4), (6,5), (6,7), (7,4), (7,5).

В=

§5. Число ребер простого графа. Разрезы.

Теорема 1. Пусть G – простой граф с n вершинами и k компонентами связности. Тогда число m его ребер удовлетворяет неравенствам

.

Доказательство. Первое неравенство

докажем методом математической индукции по числу ребер в G.

База индукции. Если G вполне несвязный граф, то утверждение верно.

Индукционное предположение. Предположим, что утверждение верно для количества ребер меньше m.

Шаг индукции. Если в графе G число ребер минимально (скажем m₀), то удаление любого ребра должно привести к увеличению числа компонент на 1. Таким образом, в получившемся графе будет n вершин, k+1 – компонент и m₀-1 – ребер. Следовательно, в силу индуктивного предположения получается: m₀-1³n-(k+1) Þm₀³n-k. Утверждение верно.

Для доказательства оценки сверху можно считать каждую компоненту графа G полным графом. Предположим, что C_i и C_j – две компоненты соответственно с n_i и n_j вершинами и n_i³n_j>1. Если мы заменим С_i и C_j на полные графы с n_i+1 и n_j-1 вершинами, то общее число вершин не изменится, а число ребер увеличится на положительную величину равную n_i-n_j+1. Следовательно, для того, чтобы число ребер в графе G было максимально возможным (при заданных n и k), G должен состоять из k-1 изолированных вершин и полного графа с n-k+1 вершинами. Тогда количество ребер будет

. Отсюда следует нужное неравенство. ■

Следствие 1.1. Любой простой граф с n вершинами и более чем

ребрами связен.

Определение 17.Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.

#17. Для данного графа разделяющими множествами будут

S₁={e₁, e₂, e₄}

S₂={e₃, e₅, e₆, e₇}

Определение 18.Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

#18. В примере 17 S₁ не является разрезом. S₂ – разрез.

Определение 19. Если разрез состоит из единственного ребра е, то е называется мостом или перешейком.

#19.

е – мост

Все вышеприведенные определения легко переносятся на несвязные графы:

В произвольном графе Gразделяющим множеством называется такое множество ребер, удаление которого увеличивает число компонент в G. Разрезом в G называется разделяющее множество, никакое собственное подмножество которого не является разделяющим. Заметим, что в результате удаления ребер, принадлежащих разрезу, число компонент в G увеличивается ровно на единицу.

§6. Эйлеровы графы.

Определение 20. Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро. Такая цепь называется эйлеровой цепью.

Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым. При этом каждый эйлеров граф будет полуэйлеровым.

#20.

Не эйлеров граф Полуэйлеров граф Эйлеров граф

Лемма 1. Если степень каждой вершины графа G не меньше двух, то граф G содержит цикл.

Доказательство. Если в графе G имеются петли или кратные ребра, то утверждение очевидно; поэтому предположим, что G является простым графом. Пусть v – произвольная вершина графа G; построим по индукции маршрут v®v₁®v₂®…, выбирая вершину v₁ смежной вершине v, а для i³1 – выбирая v_i+1 смежной v_i и отличной от v_i-1 (существование такой вершины v_i+1 гарантировано условием леммы). Так как G имеет конечное число вершин, то в конце концов мы придем к вершине, которая была уже выбрана ранее.