Дискретная математика 3 (стр. 7 из 10)
Таким образом, все вершины графа можно разбить на непересекающиеся классы вершин связанных между собой отношением достижимости. И каждый такой класс будет компонентой неориентированного графа. То есть две различные компоненты неориентированного графа не пересекаются (не имеют общих вершин и общих ребер).
В ориентированном графе отношение достижимости не является отношением эквивалентности (не всегда выполняется симметричность) и поэтому компоненты ориентированного графа могут пересекаться.
#10.Граф G не связный.
Он состоит из трех компонент.
В примере 9 все графы связные.
¬Этот граф связный.
Не связный, так как вершина v2 и v5 не достижимы друг из друга. ®
Определение 11. Ориентированный граф называется сильно связным, если для любых двух его вершин u и v вершина v достижима из u и вершина u достижима из v (u и v взаимно достижимы). Бикомпонента ориентированного графа – это его максимальный сильно связный подграф.
#11.Граф G не связный. Бикомпонентой является подграф G1, порожденный множеством вершин {v1, v2, v3}.
G1 – сильно связный, ведь:v1 достижима из v2;
v1 достижима из v3;
v2 достижима из v1;
v2 достижима из v3 (v3, v1, v2);
v3 достижима из v1;
v3 достижима из v2.
Подграф G1 является максимальным сильно связным. Вершины v4 и v5 уже ни с одной из вершин v1, v2, v3 не взаимно достижимы.
Определение 12. Граф, у которого множество ребер пусто E(G)=Æ, называется вполне несвязным (или пустым)графом.
#12.
Определение 13. Простой граф, в котором любые две вершины смежны, называется полным графом. Обозначается Кn, где n – число вершин.
#13.Определение 14. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным. Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3, называются кубическими (или трехвалентными).
#14.¬ Кубический граф
Полный регулярный граф степени 5 ®
§4. Способы представления графов.
Наиболее известный и популярный способ представления графов состоит в геометрическом изображении точек (вершин) и линий (ребер). При численном решении задач на вычислительных машинах граф должен быть представлен дискретным способом. Представим несколько таких способов.
Определение 15.Матрицей смежности ориентированного графа с n вершинами называется матрица A=(aij), i, j=1, 2, …, n, в которой
.Для неориентированного графа матрица смежности определяется следующим образом:
Матрица смежности однозначно определяет структуру графа. Петля в матрице смежности может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1.
#15. Для ориентированного графа: 
Для соответствующего неориентированного графа:
Заметим, что в А в i-ой строке количество единиц равно полустепени исхода dg+vi, а количество единиц в i-ом столбце – полустепени захода dg-vi.
Для неориентированного графа матрица смежности вершин всегда симметрическая и сумма чисел в любой строке или столбце равна степени соответствующей вершины (здесь петля учитывается 1 раз).
Определение 16.Матрицей инцидентности графа с n вершинами и m ребрами называется матрица В=(bij), 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 число ребер минимально (скажем m0), то удаление любого ребра должно привести к увеличению числа компонент на 1. Таким образом, в получившемся графе будет n вершин, k+1 – компонент и m0-1 – ребер. Следовательно, в силу индуктивного предположения получается: m0-1³n-(k+1) Þm0³n-k. Утверждение верно.
Для доказательства оценки сверху можно считать каждую компоненту графа G полным графом. Предположим, что Ci и Cj – две компоненты соответственно с ni и nj вершинами и ni³nj>1. Если мы заменим Сi и Cj на полные графы с ni+1 и nj-1 вершинами, то общее число вершин не изменится, а число ребер увеличится на положительную величину равную ni-nj+1. Следовательно, для того, чтобы число ребер в графе G было максимально возможным (при заданных n и k), G должен состоять из k-1 изолированных вершин и полного графа с n-k+1 вершинами. Тогда количество ребер будет
. Отсюда следует нужное неравенство. ■Следствие 1.1. Любой простой граф с n вершинами и более чем
ребрами связен. 
Определение 17.Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.#17. Для данного графа разделяющими множествами будут
S1={e1, e2, e4}
S2={e3, e5, e6, e7}
Определение 18.Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.
#18. В примере 17 S1 не является разрезом. S2 – разрез.
Определение 19. Если разрез состоит из единственного ребра е, то е называется мостом или перешейком.
#19.е – мост
Все вышеприведенные определения легко переносятся на несвязные графы:
В произвольном графе Gразделяющим множеством называется такое множество ребер, удаление которого увеличивает число компонент в G. Разрезом в G называется разделяющее множество, никакое собственное подмножество которого не является разделяющим. Заметим, что в результате удаления ребер, принадлежащих разрезу, число компонент в G увеличивается ровно на единицу.
Определение 20. Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро. Такая цепь называется эйлеровой цепью.
Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым. При этом каждый эйлеров граф будет полуэйлеровым.
#20.Не эйлеров граф Полуэйлеров граф Эйлеров граф
Лемма 1. Если степень каждой вершины графа G не меньше двух, то граф G содержит цикл.
Доказательство. Если в графе G имеются петли или кратные ребра, то утверждение очевидно; поэтому предположим, что G является простым графом. Пусть v – произвольная вершина графа G; построим по индукции маршрут v®v1®v2®…, выбирая вершину v1 смежной вершине v, а для i³1 – выбирая vi+1 смежной vi и отличной от vi-1 (существование такой вершины vi+1 гарантировано условием леммы). Так как G имеет конечное число вершин, то в конце концов мы придем к вершине, которая была уже выбрана ранее.