ИСТОРИЯ ТЕОРИИ ГРАФОВ

ТЕОРИЯ ГРАФОВ

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

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

Рисунок 4.1 – Кенигсбергские мосты

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

1 2

Рисунок 4.2 – Четыре цвета