Определение графа

История возникновения теории графов.

Тема 4. ГРАФЫ И СЕТИ

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

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

Рис. 1. Иллюстрация к задаче о Кенигсбергских мостах

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

Рис. 2. Иллюстрация к задаче о трех домах и трех колодцах

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

Число вершин графа G обозначим р, а число ребер — q

.

Дата добавления: 2015-05-26