Основоположником теории графов считают Леонарда Эйлера (1707 - 1783 гг.), решившего задачу о кенигсбергских мостах. В 18 - м веке г. Кенигсберг был расположен на обоих берегах и двух островах реки Преголя. Острова между собой и с берегами были связаны семью мостами (рис.4.1). Жители города любили размышлять над проблемой: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту только один раз?
Для решения задачи Л.Эйлер обозначил каждый остров, и оба берега реки маленькими кружками (вершинами) - x1, x2, x3, x4, а каждый мост - линией (ребром). Получился "граф" (рис.4.2).
Л.Эйлер обобщил задачу, которая на языке теории графов формулируется следующим образом: существует ли в графе цикл, содержащий все ребра (эйлеров цикл)?
Критерий, позволяющий решать задачи подобного класса, доказанный Эйлером, имеет следующий вид.
Эйлеров цикл в графе существует тогда и только тогда, когда степени всех его вершин четны.
То есть для существования эйлерова цикла в каждую вершину должно "заходить" четное число ребер. Как видно из рис.4.2 не все вершины графа удовлетворяют этому условию, поэтому данная задача не имеет решения.
Считается, что с задачи о кенигсбергских мостах началась теория графов.
Следует отметить, что всегда следует стараться обобщить задачу и искать решение не для частного случая, а для всего класса подобных задач. Нередко это бывает гораздо легче сделать.
