Алгебра
Английский
Биология
География
Геометрия
История
Русский
Обществознание
Физика
Химия
Информатика
Литература
Математика
Вопрос:
Пример 3. Начало теории графов положил Леонард Эйлер, решая задачу о семи мостах в г. Кёнигсберг. Сейчас это город Калининград. Через город протекает река Преголя, которую во времена Эйлера называли Прегель. На рисунке мы видим план Кенигсберга. Зеленым цветом показаны мосты через реку. Эйлеру предложили выяснить, можно ли пройти по всем семи 6 мостам, не проходя ни по одному дважды. Эйлер решил эту задачу с помощью графа, хотя еще и не использовал это слово. Нарисуйте граф для этой задачи. а) Что изображают вершины? б) Что изображают ребра? в) Как переформулировать задачу для графа?
Ответ:
a) В задаче о кёнигсбергских мостах вершинами графа изображают части города, разделённые рекой.
b) Рёбрами графа изображают мосты, соединяющие эти части города.
c) Переформулировка задачи для графа: Существует ли путь в графе, который проходит по каждому ребру ровно один раз?
Похожие
- Пример 3. Начало теории графов положил Леонард Эйлер, решая задачу о семи мостах в г. Кёнигсберг. Сейчас это город Калининград. Через город протекает река Преголя, которую во времена Эйлера называли Прегель. На рисунке мы видим план Кенигсберга. Зеленым цветом показаны мосты через реку. Эйлеру предложили выяснить, можно ли пройти по всем семи 6 мостам, не проходя ни по одному дважды. Эйлер решил эту задачу с помощью графа, хотя еще и не использовал это слово. Нарисуйте граф для этой задачи. а) Что изображают вершины? б) Что изображают ребра? в) Как переформулировать задачу для графа?
- Пример 4. Почти 100 лет потребовалось на решение задачи о четырех красках. Предположим, что на листе бумаги изображена контурная карта. Нужно раскрасить разные страны, причем страны с общей границей нужно красить в разные цвета, чтобы они не сливались. Сколько потребуется разных цветов? Для решения этой задачи применили теорию графов. Каждую страну обозначали вершиной. Если у двух стран был общий участок границы, вершины графы соединяли ребром. Изучая такие графы, доказали, что четырех красок достаточно. Каждый федеральный округ в Российской Федерации объединяет несколько регионов, например областей или республик. Постройте граф, где вершины соответствуют регионам Дальневосточного федерального округа. Ребро означает, что два региона имеют сухопутную границу
- Пример 5. Два черных и два белых коня стоят в углах шахматной доски 3 х 3, черные вверху, а белые внизу. Можно ли, передвигая их по шахматным правилам, поставить белых коней в два противоположных угла, а черных – в два других противоположных угла?
- Пример 6. Можно ли выписать в ряд натуральные числа от 1 до 9 так, чтобы сумма любых двух, стоящих рядом, делилась бы на 5 или на 12?
