Контрольные задания > Задание 4: На рисунке мы видим план Кенигсберга XVIII в. Существовала легенда, что счастлив будет тот, кто совершит прогулку по городу, пройдя ровно один раз по каждому из семи мостов. Знаменитый математик Эйлер задался вопросом: а возможно ли это? Он решил эту задачу с помощью графа. Нарисуйте граф для этой задачи. 1. Что изображают вершины? 2. Что изображают ребра? 3. Как переформулировать задачу для графа?
Вопрос:

Задание 4: На рисунке мы видим план Кенигсберга XVIII в. Существовала легенда, что счастлив будет тот, кто совершит прогулку по городу, пройдя ровно один раз по каждому из семи мостов. Знаменитый математик Эйлер задался вопросом: а возможно ли это? Он решил эту задачу с помощью графа. Нарисуйте граф для этой задачи. 1. Что изображают вершины? 2. Что изображают ребра? 3. Как переформулировать задачу для графа?

Смотреть решения всех заданий с листа

Ответ:

Ответ:

Краткое пояснение: Необходимо определить, что в задаче о Кёнигсбергских мостах представляют собой вершины и рёбра графа, и как переформулировать задачу в терминах теории графов.
  1. Что изображают вершины?

    2. Вершины графа изображают части города (например, острова или берега), соединенные мостами.

  2. Что изображают ребра?

    3. Рёбра графа изображают мосты, соединяющие эти части города.

  3. Как переформулировать задачу для графа?

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

Ответ: Вершины графа - части города, ребра графа - мосты, задача - существует ли Эйлеров путь.

Цифровой атлет: Achievement unlocked: Домашка закрыта

Сэкономил время — спас вечер. Иди чиллить, ты это заслужил

Стань легендой класса: поделись решением с теми, кто в танке

ГДЗ по фото 📸
Подать жалобу Правообладателю