Способы задания графов
Рассмотрим одну из задач, положивших начало теории графов - задачу о Кенигсбергских мостах, которая заключается в следующем:
Семь мостов города Кенигсберга расположены на реке Прегель так, как изображено на рис.3.3, соединяя его части A,B,C,D. Нужно найти такую точку города, выйдя из которой можно пройти по всем мостам города по одному разу и вернуться в нее обратно.
Эйлер показал, что эта задача не имеет решения. Каждый мост он заменил линией, соединяющей точки, соответствующие берегам. В результате получился граф, изображенный на рис.3.4.
|
|||
|
|||
Рис.3.3 Рис.3.4
предыдущаяследующая