Алгебра
Английский
Биология
География
Геометрия
История
Русский
Обществознание
Физика
Химия
Информатика
Литература
МатематикаВопрос:
129. Какое максимальное число кёнигсбергских мостов можно пройти по одному разу и вернуться в исходную точку? А если не требовать возвращения в исходную точку?
Ответ:
Если требовать возвращения в исходную точку (Эйлеров цикл), то пройти можно 0 мостов, так как все вершины имеют нечётную степень. Если не требовать возвращения (Эйлеров путь), то можно пройти 5 мостов, так как можно выбрать начальную и конечную вершины с нечётной степенью, а остальные вершины должны иметь чётную степень.
Похожие
- 125. Какие из графов, изображённых на рисунке 82, содержат эйлеровы циклы? Найдите эти циклы.
- 126. Какие из фигур, изображённых на рисунке 83, можно нарисовать, не отрывая карандаша от бумаги и не проводя никакую линию дважды? Если возможно, покажите, как это сделать.
- 127. В каких пределах может меняться степень вершин:
- 128. Можно ли в задаче о кёнигсбергских мостах пройти по каждому из семи мостов по одному разу, если не требовать возврата в исходную точку?
- 130. Петя вбил в землю 5 колышков и соединил некоторые из них верёвками. Могло ли так получиться, что к каждому колышку привязано ровно по 3 верёвки?
- 131. На олимпиаде по математике каждый из 30 участников решил по 4 задачи, а каждую задачу решили ровно 10 человек. Сколько задач было на олимпиаде?
- 132. В чемпионате города по футболу участвует 12 команд. Чемпионат проводится в один круг (каждая команда встречается с каждой по одному разу). Докажите, что в любой момент проведения чемпионата всегда найдутся хотя бы две команды, сыгравшие одинаковое число матчей.
