какая-то теория / основные понятия
.pdfДИСКРЕТНАЯ МАТЕМАТИКА
ГРУППЫ 1/42, 1/147, 1/184
Ксенофонтова Ольга Леонидовна
ТЕОРИЯ ГРАФОВ
ОСНОВНЫЕ ПОНЯТИЯ
Из истории теории графов
Основоположником теории графов считается Леонард Эйлер, который доказал невозможность маршрута прохождения всех четырех частей суши в задаче о кенигсбергских мостах (1736 г.).
3
Основные понятия
Граф G=(V,E) - это пара двух конечных
множеств: конечного множества элементовточек, называемых вершинами (узлами)
графа, и конечного множества элементов-
линий, называемых ребрами.
Граф G=(V, E)
V={v1, v2, v3, v4, v5} ;
E={e1, e2, e3, e4, e5, e6, e7}
4
Основные понятия
Вершины vi и vj, определяющие ребро ek,
называются концевыми вершинами ребра ek.
Петля – замкнутое ребро(e5).
5
Основные понятия
Ребра с одинаковыми концевыми вершинами
называются параллельными (кратными) (e1,e4).
Количество таких пар ребер – это кратность
ребра.
6
Основные понятия
Ребро, принадлежащее вершине, называется
инцидентным (ребро e1 инцидентно вершинам v1 и v2). Или, если ребро графа соединяет две
его вершины, то это ребро им (вершинам) инцидентно.
7
Основные понятия
Число ребер, инцидентных некоторой
вершине, называется степенью этой вершины.
deg (А) = 1, deg (С) = 4, deg (D) = 2.
Вершина графа, имеющая степень, равную 1,
называется висячей. (Вершины А, B, E, H, G)
8
Степень вершины
Граф G=(V,E) называется регулярным или однородным (степени r), если степени всех его
вершин одинаковы. Степенью регулярного графа
называется степень его вершин.
9
Основные понятия
Теорема. В графе сумма степеней всех его
вершин – это число четное, равное удвоенному числу ребер графа:
deg (F) = 3, вершина F –
нечетная.
deg (С) = 4, deg (D) = 2,
вершины C и D - четные.
10