Тема 2.
Основные теории графов.
2.1. Из теории графов.
В 19 веке появилась потребность в математическом понятии для описания следующих рисунков.
Применение в физике для исследования электрических цепей, в химии для описания больших молекул. Так возникло понятие графа.
Вскоре выяснилось, что понятие графа имеет многочисленные примеры в самой математике и информатике (описание больших массивов, алгоритм сортировки и поиска в них).
1.2. Понятие графа и его составляющие.
Опр. Пусть дано множество X и многозначное отображение f:X->X. Тогда говорят, что задан ориентированный граф (орграф).
Элементами x
c X
называют вершинами орграфа узлами).
Тогда (x;y),где
у c f(x),
называют дугой (изображается стрелкой).
Последовательность дуг такая, что конец каждой дуги (кроме последней) является началом последующей, называют путем в орграфе.
Замкнутый
путь называют контуром.
Если в орграфе отождествить пары (x,y) и (y,x) (то есть «стереть» наконечники стрелок), то возникает неориентированный граф (граф).
Для него дуга переименовывается в ребро, путь – в цепь, контур – в цикл.
граф
ребро
вершины цепь цикл
Замечание: в отличии от геометрических фигур, являющихся жесткими объектами, графы являются мягкими объектами (топологическими). Это означает, что ребра (дуги) графа можно рассматривать и изгибать, сохраняя лишь количество вершин и их соединений.
=>
Один и тот же граф.
Ясно, что в теории графов отсутствует понятие геометрической длины ребра (дуги). То есть все ребра (дуги) одинаковы. Если же ребра неравноправны, то на них ставят особые числа, называемые весом ребер (дуг).
Опр. Если каждому ребру (дуге) графа приписано некоторое число λк≥0 (вес ребра, дуги), то граф называется взвешенным (нагруженным).
2.3 Связные графы.
О
пр.
Неориентированный граф называется
связным, если любые 2 его вершины можно
соединить цепью.
Связный граф Несвязный граф
Попробуем разобраться в устройстве несвязных графов научно-математически. Нам поможет понятие отношения.
Опр: На множестве вершин графа X введем отношение Г: xГy, если x и Y можно соединить цепью.
Предложение: Отношение Г является отношением эквивалентности.
Доказательство.
Рефлексивно xГx - верно
Симметрично xГy => yГx - верно
Транзитивно xГy, yГz => - верно.
Значит это отношение эквивалентности. По теореме (свойство отношения эквивалентности) весь граф распадается на объединение непересекающихся классов эквивалентности, в каждом из которых любые 2 вершины можно соединить цепью. То есть весь граф распределяется на несколько непересекающихся свободных подграфов – компонент связности.
Два компонента связности
Если же сам граф связан, то он состоит из одного компонента.