Задачи для самостоятельного решения.
Задачи, решаемые с помощью теории графов
Задача о 7 Кённигсберских мостах
Через город протекает река Прегель. В городе - семь мостов, расположенных так, как показано на рисунке выше. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз?
Задачи на связность графа
Задача №1. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?
Решение. Построим граф: города изобразим вершинами графа, а авиалинии – ребрами. Вершины 3, 5, 9 связаны между собой, но не связаны с остальными. Значит, долететь из города 1 в город 9 нельзя.
Ответ: нет, нельзя.
Задача №2. Можно ли выписать в ряд цифры от 0 до 9 так, чтобы сумма любых стоящих рядом цифр делилась либо на 5, либо на 7, либо на 13?
Решение
Ответ: можно
Задача №3. В деревне 9 домов. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор – Диме и Никите, Евгений – сосед Никиты, а больше соседей в этой деревне нет (соседними считаются дворы, у которых есть общий участок забора). Может ли Пётр огородами пробраться ночью к Никите за яблоками?
Решение. Ответить на вопрос задачи сразу нелегко. Выпишем имена мальчиков и соединим соседей линиями:
|
|
|
Изображение ситуации, описанной в условии задачи, помогает сделать вывод: Пётр не может огородами пробраться к Никите, так как они не соседи.
Ответ: нет, не может.
Задача №4. Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Решение. Повторим ту же идею: изобразим ситуацию из условия задачи на рисунке. Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию – отрезок или часть кривой, соединяющая конкретные точки – имена (рисунок справа).
Если подсчитать число линий, изображенных на рисунке, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.
Ответ: всего было сделано 10 рукопожатий.
Задачи на степени вершин графа
Задача №5. В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.
|
|
|
Задача №6. На концерте каждую песню исполняли двое артистов, и никакая пара не выступала вместе более одного раза. Всего было 12 артистов, каждый выступил по 5 раз. Сколько было песен?
Решение. Рассмотрим граф, вершинами которого являются выступавшие артисты. Соединим пару артистов ребром, если они вместе пели. Получим граф с 12 вершинами степени 5, каждой песне соответствует ребро. Аналогично предыдущему примеру, в графе (12 · 5) : 2 = 30 рёбер, то есть было 30 песен.
Ответ: 30 песен.
Обратите внимание на то, что рёбра считать легче, чем песни или провода. Рёбра легко изображать, именно это свойство (наглядность) обусловило столь широкое распространение графов.
Задача №7. В фирме 50 компьютеров. Некоторые пары компьютеров должны быть соединены проводами. От каждого компьютера должно отходить ровно по 8 кабелей. Сколько всего понадобится кабелей?
Решение:
Задача №8. В некотором графе 40 вершин. Степень каждой вершины равна 7. Сколько ребёр в графе?
Задачи для самостоятельного решения.
1. Сева нарисовал 10 точек, некоторые из которых соединил отрезками. После этого он спрятал рисунок в чемодан, чемодан закрыл на ключ, а ключ проглотил. В ответ на это Наташа заслала в его чемодан разведывательного таракана, который сообщил, что из точек выходит соответственно 5, 5, 4, 4, 3, 3, 2, 2, 1, 1 отрезка. Сколько отрезков нарисовал Сева?
|
|
|
2. В некотором государстве 40 городов и из каждого выходит по 7 дорог. Сколько всего в государстве дорог? (Каждая дорога соединяет какие-то два города.)
3. В деревне Пятнашкино 15 домов. Электрик решил соединить проводами каждый дом ровно с девятью другими. Сможет ли он это сделать?
4. В компьютерном классе 17 компьютеров. Некоторые из них соединены проводами. Известно, что от каждого компьютера отходит по четыре провода, а каждый из проводов имеет длину 15 метров. Найдите общую длину проводов в компьютерном классе.
Дата добавления: 2021-04-15; просмотров: 1126; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!