мост графа

Ответ от Karina z[гуру]
Теория графов
В математической теории графов и информатике граф — это совокупность объектов со связями между ними. Граф изображается как набор точек, некоторое из которых соединены линиями.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами.
Основы теории графов как математической науки заложил Л. Эйлер в 1736 г. , рассматривая задачу о кёнегсбергских мостах.
<Решение задачи о семи мостах Кёнигсберга. >
Семь мостов Кёнигсберга существовали в Кёнигсберге (нынешнем Калининграде) в XVI—XX веках. Взаимное расположение мостов натолкнуло Эйлера на размышления, приведшие к возникновению теории графов.
В пределах города река омывает два осторова. С берегов на острова перекинуты мосты.
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу, как теоретически, так и практически, во время прогулок. Но никому это не удавалось доказать, что это даже теоретически невозможно.
В 1736 году задача о семи мостах заинтересовала и Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно) .
Эйлер начертил упрощенную схему города. Получился граф, вершины которого - части города, а ребра - мосты.
Прежде, чем обосновать невозможность требуемого маршрута, Эйлер рассмотрел и другую, более сложную карту. В ходе рассуждений Эйлер пришёл к следующим выводам:
- Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин.
- Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
- Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
В итоге он доказал общее утверждение: для того, чтобы можно было обойти все ребра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнение следующих условий:
1. из любой вершины графа должен существовать путь по его ребрам в любую другую вершину (графы, удовлетворяющие этому требованию называются связными)
2.из каждой вершины должно выходить четное количество ребер.
Замкнутый путь, проходящий по одному разу по всем ребрам графа, называют с тех пор эйлеровым циклом.
Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечетное количество ребер. В этом случие начинать движение следует с одной из этих двух вершин, а заканчивать - в другой.
Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Упрощённая схема мостов Кёнигсберга.
Граф кёнигсбергских мостов
Источник: Отрывок из моего реферата по Эйлеру.