Изображения из Приложения 1, Приложения 2 и Приложения 3 распределены в тексте работы при публикации!

Задача 1: В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?

Ответ: Нет, так как 9+10=19 и это нечетное число (смотри теорему 2).

Задача 2: Как вы помните, охотник за мертвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарева. Установите, какое имение кому принадлежит, если ни по одной из дорог Чичиков не проезжал более одного раза.

Рассмотрим схему: к A и B идут всего две дороги, поэтому отмечаем их.

Значит, Чичиков обязательно должен был проехать по OC. Отмечаем BD.
Чтобы посетить E, но также попасть в G, существует единственный маршрут.

Итого получается A – Ноздрев, B – Плюшкин, C – Коробочка,D –Тентетников,E – Бетрищев, F – Петух, G – Констанжогло, H – Собакевич, O – Манилов,X – Кошкарев.

Задача 3: В автомобильных гонках Коля, Боря, Юра заняли первые четыре места.
На вопрос, какие места они заняли, трое из них ответили:
1) Коля ни первое, ни четвертое;
2) Боря второе;
3) Вова не был последним.

Ответ:
1 – Вова;
2 – Боря;
3 – Коля;
4 – Юра.


Задача 4: Может ли так случиться, что в одной компании из шести человек один человек каждый знаком с двумя и только с двумя другими?

Существует два графа соответствующих условию задачи.

Однако стоит отметить, что во втором варианте получилась не одна, а две компании, где участники одной из них не знакомы с участниками другой.

Задача 5: В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией тогда и только тогда, когда двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли из города 1 добраться в город 9?

Решение:

Ответ: нельзя.


Задача 6: Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см? Какое наименьшее число раз придётся ломать проволоку, чтобы всё же изготовить требуемый каркас?

Решение: Нет, нельзя, потому что в кубе вершины представляют собой узлы графа, где сходятся по три ребра. Такие узлы называют "нечетными". Из топологии известно, что нельзя построить граф, не отрывая карандаша от бумаги, если в графе больше двух нечетных узлов. А в кубе - 8 вершин!

Задача 7: Задачи о колодцах.
Три человека жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам. Однажды эти люди перессорились и решили провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались.

Ответ: Это невозможно.

Задача 8:
Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

Решение:

Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки — имена.

Если подсчитать число ребер графа, изображенного на рисунке справа, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.

Решение:

Пусть существует некоторый город А.

Из него можно добраться не более, чем до трёх городов, а из каждого из них ещё не более чем до двух (не считая А).

Тогда всего городов не более 1+3+6=10.

Значит всего городов не более 10.

Пример на рисунке (его ещё называют графом Петерсона) показывает существование авиалиний.

Задача 10: Дима, приехав из Врунляндии, рассказал, что там есть несколько озёр, соединенных между собой реками. Из каждого озера вытекают 3 реки, и в каждое озеро впадают 4 реки. Докажите, что он ошибается.

Решение:
Если вытекают 3 реки, а впадают 4 – это невозможно, т. к. количество «втекающих», должно быть равно количеству «вытекающих». Дима не прав.

Задача 11: Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков. Докажите, что найдутся команды А, В и С такие, что А выиграла у В, В выиграла у С, а С выиграла у А.

Решение:
Пусть А и В набрали одинаковое количество очков, но В выиграла у А, тогда если для любой команды С, у которой выиграла А, выиграла и В, то у В должно быть очков больше, чем у А. Значит, есть такая команда С, что А выиграла у С, а С выиграла у В.

Задача 12: В Цветочном городе каждый коротышка знаком с 6 малышками, а каждая малышка – с 6 коротышками. Докажите, что в этом городе число малышек равно числу коротышек.

Решение:
Если знакомство вида «коротышка – малышка» - это ребро графа, то n – число коротышек, m – число малышек. Тогда всех знакомств (ребер) коротышек 6n, а малышек 6m. Значит 6n= 6m, тогда в этом городе число малышек равно числу коротышек.

Вернуться
к содержанию исследовательской работы
В мире графов