Лекция: Основные понятия и характеристики графов.

Раздел 3. Теория графов.

Тема 3.1. Основные понятия и характеристики графов.

План

1. Графические представления исследуемой системы.

2. Гистограммы.

3. Круговые диаграммы.

4. Графы. Вершины и ребра графов.

5. Виды графов.

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

Теория графов берет начало с решения задачи о кенигсбергских мостах в 1736 году знаменитым математиком Леонардом Эйлером (1707-1783: родился в Швейцарии, жил и работал в России).

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

Никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно…

О. 1. Графом G(V,E) называется совокупность двух множеств - непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элемен­тов множества V (Е - множество ребер).

G(V,E): , EVxV

О. 2. Граф G – это математический объект, состоящий из множества вершин и множества ребер . Таким образом, граф полностью определяется совокупностью множеств .

Простой граф – конечные граф без петель и кратных ребер.

Обычно граф изображают диаграммой: вершины - точками (или кружками), ребра - линиями.

Виды графов.

Существуют два основных вида графов (и множество их подвидов): ориентированные и неориентированные.

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

Ребра ориентированного графа называются дугами.

Соответствующие вершины ориентированного графа называют узлами (началом и концом).

О.4. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).

О 5. Граф называется простым, если каждую пару вершин соединяет не более чем одно ребро.

О 6. Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным.

Различные ребра могут соединять одну и ту же пару вершин. Такие ребра называют кратными.

О. 7. Граф, содержащий кратные ребра, называется мультиграфом.

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

О. 7. Граф с кратными ребрами и петлями называется псевдографом.

Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым.

Как в случае ориентированного, так и в случае неориентированного ребра говорят, что вершины, соединяемые ребром, называются инцидентными этому ребру.

О. 8. Две вершины графа называются смежными, если существует соединяющее их ребро.

Два ребра называются смежными, если они имеют общую вершину.

(Ребро называется инцендентным двум вершинам, если оно связывает эти вершины.)

О. 9. Степенью вершины графа называется число ребер, которым принадлежит эта вершина. Еще называют его валентностью и обозначают

Вершина, имеющая степень 0, называется изолированной, а степень 1 – висячей.

О .10. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k.

Пример: Посчитаем степень всех вершин ,, , , .

О .11. Дополнением графа называется граф , с теми же вершинами, что и граф G, и имеющий те и только те ребра, которые необходимо добавить к графу G, чтобы он стал полным. На рисунке дополнением графа G₁ до G, является .

О .12. Подграфом графа G называется граф, все вершины и ребра принадлежат графу G.

О. 13. Граф G = (X, A) – полный, если каждая пара вершин соединена ребрами. В противном случаи граф называется неполным.

О .14. Граф G = (X, A) – симметрический, если для любой дуги (xi, xj) существует противоположно ориентированная дуга (xj, xi).

О .15. Граф G = (X, A) – планарный, если он может быть изображен на плоскости так, что не будет пересекающихся дуг.

О .16. Неориентированный граф G = = (X, A) – двудольный, если множество его вершин X можно разбить на два подмножества X1 и X2, что каждое ребро имеет один конец в X1, а другой в X2.

Пример.

Рис. 1. Неориентированный граф с петлей и кратными ребрами.

1. . .

Т.о. это неориентированный граф с петлей и кратными ребрами.

Рис. 2. Ориентированный граф с петлей и кратными ребрами.

2. . .

Т.о. это ориентированный граф с петлей и кратными ребрами.

Способы задания графов

1) Задание списка вершин и ребер. G = (V, E)

2) Геометрическая интерпретация (графический способ).

3) Матричный.

Матричный способ.

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

О. 17. Граф называется помеченным (перенумерованным), если его вершины отличаются одна от другой какими-либо методами.

 

Пример:

Матрица смежности определяется одинаково для ориентированного и неориентированного графов.

О.18. Матрица смежности – это квадратная матрица порядка , где смеж – число вершин, у которой

Пример:

 

О. 16. Матрицей инцидентности ориентированного графа называется прямоугольная матрица (n × m), где n – число вершин, m – число ребер, у которой

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

Пример:

Матрица инцидентности ориентированного графа, изображенного на рис. 3, имеет вид:

Матрица инцидентности графа, изображенного на рис. 2, имеет вид: