-
Понятие графа. Способы задания графа. Пример.
Графом называется множество вершин и соединяющих их дуг.
Способы задания графа.
-
Графический:
x1
x2
x5
x4 x3
-
Аналитический:
а) задание графика в виде множеств образов:
Г
x1
= {x2}
Гx4
= {x5}
Гx2 = {x2, x3, x4} Гx5 = {x2}
Гx3 = {x4}
б) задание графика в виде перечисления:
Г={<x1,x2>,<x2,x2>,<x2,x3>,<x2,x4>,<x3,x4>,<x4,x5>,<x5,x2>}.
-
С помощью матрицы инциденций (инцидентности).
столбцы - множество всевозможных дуг графа.
На пересечении строки и столбца ставится +1, если данная дуга заходит в вершину, и -1, если дуга исходит из вершины.
|
|
|
|
|
|
|
|
|
|
х1 |
-1 |
|
|
|
|
|
|
|
х2 |
+1 |
2 |
-1 |
|
|
-1 |
+1 |
|
х3 |
|
|
+1 |
-1 |
|
|
|
|
х4 |
|
|
|
+1 |
-1 |
+1 |
|
|
х5 |
|
|
|
|
+1 |
|
-1 |
-
С помощью матрицы смежностей (самый популярный способ).
В матрице смежности графа G строки и столбцы есть вершины графа. При наличии дуги между вершинами графа на пересечении вершины-строки, из которой исходит дуга, и вершины-столбца, куда дуга заходит, ставится единица.
|
|
х1 |
х2 |
х3 |
х4 |
х5 |
|
х1 |
|
1 |
|
|
|
|
х2 |
|
1 |
1 |
1 |
|
|
х3 |
|
|
|
1 |
|
|
х4 |
|
|
|
|
1 |
|
х5 |
|
1 |
|
|
|
-
Виды графов: эйлеров, полный, планарный, деревья. Примеры.
Цепь называется эйлеровой, если она является простой и проходит по всем ребрам графа.
Эйлеровым циклом называется простой цикл, проходящий по всем ребрам.
Граф, имеющий эйлеровый цикл, называется эйлеровым графом.
Теорема: Для того чтобы связный граф был эйлеровым необходимо и достаточно, чтобы степени всех вершин его были четными.
Таким образом, решена задача о Кенигсбергских мостах. Слово «решена» здесь используется в расширненном понимании, принятом в обиходе у математиков, поскольку Эйлер на самом-то деле доказал, что задача не имеет решения.
Следствие. Для того, чтобы в графе существовала Эйлерова цепь необходимо, чтобы в нем было ровно две вершины с нечетной степенью, причем эта цепь начинается в одной из этих вершин и заканчивается в другой.
Известная детская задача нарисовать, не отрывая карандаша, домик – лучшая иллюстрация к этому следствию.
Граф называется полным, если любые две его вершины смежены, т.е. имеют общее ребро.
1
5
2
- К5
4
3
n(n-1) 2
Т
еорема:
В полном графе с n вершинами
ребер.
Граф
G называется
дополнением
графа G, если их объединение дает полный
граф.
1 2
1 2
G
G
4 3 4 3
1
1
5
2 4 3
G G
4 3 2 5
Дерево - это связный граф без циклов. Дерево – это граф, между любой парой вершин которого существует единственная цепь.
Теорема: В графе типа дерева с n вершинами n-1 ребер.
П
римеры
деревьев.
Диаметром для графов типа дерева является максимальное расстояние между его вершинами.
Определим для каждой вершины ее расстояние от самого удаленного листа Минимальное число - радиус, эта вершина корневая (центральная).
В любом дереве существует одна или две (смежные) корневые вершины
Граф - плоский, если он изображен на плоскости без пересечения ребер.
Граф - планарный, если он может быть изображен на плоскости без пересечения ребер.
Л
юбой
плоский граф может быть преобразован
в граф с прямыми ребрами.
неплоский, но плоский плоский с
планарный прямыми ребрами
Граф, где все вершины соприкасаются с внешней гранью - внешнепланарный.
Два "замечательных" непланарных графа:
К5 К3,3
Любой граф, содержащий в качестве подграфа К5 или К3,3 - непланарен.