2014-02-09
1165
B
A
ТЕОРИЯ ГРАФОВ
Начало теории графов как математической дисциплине было положено Леонардом Эйлером в его знаменитом решении задачи о Кенигсбергских мостах в 1736 году. План города Кенигсберга представлен на рис. 3.1. Задача о Кенигсбергских мостах сводилась к тому, чтобы построить маршрут своей воскресной прогулки так, чтобы, начиная в любой точке суши (A, B, C или D) пройти по всем мостам строго по одному разу и вернуться в исходную точку (начало маршрута).
 |
Рис. 3.1. Иллюстрация к задаче о Кенигсбергских мостах.
Такую задачу не предоставляется возможным решить классическими методами математики. Для решения такой задачи был предложен качественно новый аппарат – аппарат теории графов.
Графом называется пара следующего вида:
, (3.1)
где 
- график 
;
- множество вершин.
Иными словами, граф представляет совокупность множества вершин и дуг.
 |
Рис. 3.2. Граф
Граф, представленный на рис. 3. 2, состоит из множества вершин 
и множество дуг 
Графическое изображение графа является самым наглядным, но не единственным способом задания графа. Кроме того граф может быть задан:
|
|
|
1. перечислением:
2. множеством образов:
,
где 
- образ вершины
- множество вершин, в которые исходят дуги из данной вершины.
