задача л эйлера про мосты

закономерности 7. такой граф начертить «одним росчерком» невозможно. Значит, и пройти по кенигcбергским мостам, соблюдая заданные условия, нельзя.

рисунке имеет четыре нечетные вершины, то, согласно

нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа, представленного на рисунке. Но, поскольку граф на этом

Решение: Прохождение по всем мостам при условии, что

Решить эту задачу удалось в 1736 г. . В ходе решения задачи (после интерпретации условия задачи в виде графа, где вершины - острова и берега, а ребра - мосты, представленного на рисунке), Л. Эйлер установил, помимо уже рассмотренных нами, (доказательство этих закономерностей предлагаем вам).

Задача заключается в следующем: нужно пройти (если это возможно) по всем семи мостам так, чтобы на каждом из них побывать лишь по одному разу и вернуться к тому месту, откуда начал маршрут.

К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали с берегами и друг с другом два острова, расположенные в пределах города (см.рисунок)

Кенигсбергские мосты

Закономерность 3. Число нечетных вершин любого графа четно.

Эта закономерность справедлива не только для полного, но и для любого графа.

Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф однородный.

Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

определенным графам.

Сформулируем некоторые закономерности, присущие

Вершина называется нечетной- если степень этой вершины нечетная, четной если степень этой вершины четная.

Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Степень вершины А обозначим Ст.А. На рисунке :

На рисунке изображен граф с пятью вершинами.

Cтепень вершины- количество ребер графа, исходящих из этой вершины.