Математическое моделирование на графах. Часть 1. Берцун В.Н. - 5 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Глава 1. Основные понятия теории графов 5
Глава 1
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
1.1. Из истории теории графов
Теория графов как математическая дисциплина стала активно
развиваться еще со времен Эйлера (1707 – 1783 гг.), который в 1736 г.
решил задачу о Кёнигсбергских мостах [2]. В городе два острова,
соединенные семью мостами (см. рис. 1.1). Можно ли побывать на
всех четырёх частях суши, пройдя по каждому мосту один раз и
оказаться на той части суши, с которой началось движение?
B
C
A
L
1
4
2
3
6
7
5
Рис. 1.1
Термин граф, который был введен в употребление Кенигом,
подразумевает наличие наглядной графической интерпретации рас-
сматриваемого объекта. Эйлер отождествил с точкой (вершиной
графа) каждую часть суши, а каждый мост – с линией (ребром графа),

Страницы