| §1 Теория графов
|
| 1. Определение графа
| Графом называется совокупность двух множеств: множества точек V и множество линий Е - подмножество VxV. Ясно, что Е={(vi,vj)| vi,vj ÎV}.
Множество V- множество вершин графа, Е – множество ребер. Обозначение: G=(V,E).
Граф есть упорядоченная пара  , где  - непустое множество, называемое множеством вершин;  - бинарное отношение на . Если - неупорядоченное бинарное отношение на (т.е.  в  , то  ), то - множество ребер, и граф является неориентированным.
Ориентированный граф есть упорядоченная пара , где - множество вершин, а - упорядоченное отношение на (т.е.  ). В этом случае называется множеством дуг. Первая и вторая вершины дуги называется соответственно начальной и конечной вершинами.
|
| 2. Отношение инцидентности
| Между множествами V и Е устанавливается отношение инцидентности: двум элементам из множества V ставится в соответствие один элемент из множества Е.
|
| 3. Смежные вершины
| Два ребра, инцидентные одной вершине, называются смежными.
Если два смежные различных ребра инциденты одной и той же вершине, то они называются смежными.
Смешные вершины. Если две вершины инциденты одному ребру, то они называются смежными.
| Задача.
 ,  - смежные вершины;  ,  - не являются смежными; ребра  и  смежные ребра, а и  нет.
|
| 4. Петля
| Если ребро инцидентно только одной вершине, то это петля.
Ребро, инцидентное только одной вершине, называется петлей.
|
| 5. Кратные ребра
| Два ребра, инцидентные одной паре вершин, называются кратными
Кратность пары вершин называется число соединяющих их ребер.
|
| 6. Безреберный граф
| Если множество Е пустое, то граф называется пустым (безреберным), все его вершины голые.
|
| 7. Полный граф
| Если все вершины графа попарно смежны, то граф полный.
|
| 8. Дополнительный граф
| Граф, дополняющий данный граф до полного, называется дополнительным.
|
| 9. Ориентированный (орграф), неориентированный граф
| Если ребра имеют направления, то граф ориентированный или орграф, иначе граф неориентированный.
Геометрическая (графическая) интерпретация графа G=(V,E), где множество вершин V={a,b,c,d,e}, а множество ребер E={(a,c),(a,d),(b,d),(c,d)}, приведена на рисунке
Неориентированный конечный граф.
|
| 10. Изоморфные графы
| Графы, отличающиеся только нумерацией вершин, но сохраняющие при этом множества V и E и соответственные инцидентности, называются изоморфными.
Графы изоморфны
Задача.
Изоморфны ли пары графов?
а) 
а) Изоморфны. Каждый из них состоит из одного простого цикла длины 5.
б) 
б) Неизоморфны. У одного есть вершина степени 4, а у второго нет.
г) 
г) Несмотря на полное совпадение наборов степеней вершин графы неизоморфны: в одном их них есть мост – ребро при удалении которого он теряется связность, а в другом моста нет.
|
| 11. Мультиграф. Псевдограф
| Если у графа  имеется несколько дуг, исходящих из вершины  и заходящих в вершину  , то такие дуги называются кратными, а сам граф называется мультиграфом.
Псевдограф − граф, в котором есть петли и/или кратные ребра.
Мультиграф − псевдограф без петель.
|  Задача.
На рисунке изображен мультиграф. Сколько исходящих дуг имеет вершина 4?
Решение.
Запишем вначале все дуги (исходящие и входящие), связанные с точкой 4.
Это дуги: (4; 1); (4; 3); (4; 4) и (3; 4). Исходящими из точки 4 являются первые три дуги. Последняя дуга (3; 4) – это входящая дуга в точку 4.
Ответ. 3.
|
| 12. Степень (валентность вершин)
| Степенью (или валентностью) вершины называется суммарное количество входящих в эту вершину и выходящих из нее дуг.
Если вершина изолированная, то ее степень равна нулю. Если вершина концевая, то ее степень равна единице.
Степенью (валентностью) вершины называется число инцидентных ей ребер.
|
| 13. Маршрут графа. Цепь/цикл графа
| В неориентированном (ориентированном) графе последовательность из  ребер (дуг)  ,  , …  называется маршрутом (ориентированным маршрутом) длины , если существует соответствующая последовательность из  (не обязательно различных вершин)  , таких, что  инциденто  ,  .
Маршрут (ориентированный маршрут) называется замкнутым (незамкнутым), если   . Если   , то маршрут называется цепью (путем).
Если , то цепь (путь) называется циклом (контуром). Если вершины различны, получаем простую цепь.
|
| 14. Связный граф
| Граф называется связным, если каждая пара вершин может быть соединена цепью.
|
| 15. Компоненты графа
| Граф, который не является связным, может быть разбит на конечное число связных подграфов, называемых компонентами или частями.
|
| 16. Связность графа
| Связностью графа называется наименьшее число вершин, удаление которых делает исходный граф несвязным.
|
| 17. Разрез графа
| Разрезом графа называется минимальное множество ребер, удаление которых увеличивает число компонент.
|
| 18. Полный граф
| Граф называется полным, если каждая вершина соединена ребром с каждой из всех других вершин.
|
 
На рисунке  - маршрут;  - цепь;  - цикл;  - простая цепь;  - простой цикл;  - разрез.
|
| 19. Двудольный граф
| Граф называется двудольным, если его вершины могут быть разбиты на два таких множества, что каждое ребро соединяет вершину одного множества с вершиной другого.
|
| 20. Регулярный граф
| Связный граф называется регулярным, если все его вершины имеют одинаковую степень.
|
| 21. Эйлеров путь. Критерий Эйлера
| Эйлеровым путем в графе G называется такой путь, в котором каждое из ребер встречается только один раз. Эйлер показал, что такой путь существует тогда и только тогда, когда граф содержит не более двух вершин нечетной степени и является связным. Эйлеров цикл существует тогда и только тогда, когда в нем все вершины четные.
ТеоремаЭйлера. В любом конечном графе сумма степеней вершин равна удвоенному числу его ребер.
|
| 22. Матрица смежности
| Матрица смежности
данная матрица симметрична относительно главной диагонали, а главная диагональ состоит из нулей, за исключением петель.
|  Задача.
Составить матрицу смежности для графа, изображенного на рисунке.
Решение.
Граф, изображенный на рисунке  состоит из трех  вершин  . И двух дуг   . Значит матрица смежности  для нашего графа будет размером  :
 .
Поясним, как получена первая строка матрицы. Первая строка  показывает связь точки  с остальными точками: дуги  , то есть петли, нет, значит 0; дуга  есть, значит 1; дуги  нет, значит – 0. Поясним вторую строку  . Она показывает связь точки  с остальными точками: дуги  нет, значит – 0, дуги  , то есть петли, нет, значит – 0; дуга  есть, значит 1. Третья строка полностью состоит из нулей, так как из точки  к остальным точкам нет связи, значит нет дуг:  ;  ;  .
Ответ. .
|
| 23. Матрица инциндентности
| Матрица инцидентности
 в случае неориентированного графа
 в случае ориентированного графа
| Задача.
Записать матрицу инцидентности для мультиграфа , изображенного на рисунке.
 Решение.
Мультиграф, изображенный на рисунке - орентирован, состоит из четырех  вершин  и семи  дуг (на рисунке дуги дополнительно обозначены цифрами). Значит матрица будет размером  , то есть четыре строки и семь столбцов:
 .
Поясним первую строку. Она показывает расположение всех семи дуг по отношении к точке :
дуга 1 в точку входит, значит ставим (– 1);
дуга 2 в точку входит, значит ставим (– 1);
дуги 3, 4, 5, 6 в точку не входят и не выходят, поэтому в первой строке на месте 3, 4, 5,6 стоят нули;
дуга 7 из точки выходит, поэтому в первой строке на седьмом месте стоит единица.
Поясним вторую строку матрицы. Она показывает расположение всех дуг по отношению к точке : дуги 1, 2, 3, 4 и 6 выходят из точки , поэтому во второй строке на первом, втором, третьем, четвертом и шестом местах стоят единицы. А вот дуга 5 в точку входит, поэтому на пятом месте стоит (– 1). Дуга 7 в точку не входит и не выходит, поэтому на седьмом месте стоит 0.
Аналогично формируются третья строка (соответствующая точке  ) и четвертая строка (соответствующая точке  ). Предлагаем самостоятельно проанализировать эти строки.
|
| 24. Дерево
| В неориентированном графе связный подграф, не имеющий циклов называется деревом.
Если все вершины графа принадлежат дереву, то оно называется покрывающим.
Ориентированное дерево имеет корень в вершине , если существует путь от к каждой из других вершин. Ребра графа, принадлежащие покрывающему дереву, называются ветвями. Все остальные ребра называются хордами.
|
|
| Матрица инциденций неориентированного графа обладает следующими очевидными свойствами:
1) в графе без петель каждый столбец этой матрицы имеет в точности две единицы, соответствующие паре вершин ребра;
2) если в графе имеются петли, то в столбцах, соответствующих петлям, имеется по одной единице, а в остальных – по две.
|
| | | | |
