double arrow

Основное определение


Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании

Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.

1. Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рис. 9.1(а)). Эта задача была решена Эйлером (1707-1783) в 1736 году.

2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 9.1(б)). Эта задача была решена Куратовским (1896-1979) в 1930 году.

3. Задача о четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом (рис. 9.1(в)).

а) б) в)

Рисунок 9.1.

Определение 9.1. Графом G(V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множества E неупорядоченных пар различных элементов множества V (E – множество ребер). G(V, E)=<V, E>, V≠Æ, EÌV´V, E=E-1. Число вершин графа G обозначим р, а число ребер — q: p:=p(G):=|V|, q:=q(G):=|E|.




Определение 9.2. Пусть ν1, ν2 — вершины, e = (ν1, ν2) – соединяющее их ребро. Тогда вершина νi и ребро e инцидентны, вершина ν2 и ребро e также инцидентны. Два ребра, инцидентные одной вершине, называются смежными, две вершины, инцидентные одному ребру, также называются смежными.







Сейчас читают про: