Олимпиадная математика. Задачи по теории графов с решениями и указаниями. 5-7 классы

ЗАДАЧИ
ПО ТЕОРИИ ГРАФОВ
с решениями и указаниями 

Москва
Лаборатория знаний
2023

Под редакцией 
М. В. Федотова

ОЛИМПИАДНАЯ
МАТЕМАТИКА

Н. Л. Семендяева, М. В. Федотов

5–7 
классы

Электронное издание

УДК 373.167.1:519.17
ББК 22.176я721.6
С30

Семендяева Н. Л.
С30
Олимпиадная
математика.
Задачи
по
теории
графов
с
решениями
и
указаниями.
5–7
классы : учебно-методическое пособие / Н. Л. Семендяева, М. В. Федотов ; под редакцией М. В. Федотова. —
Электрон. изд. — М. : Лаборатория знаний, 2023. —
178 с. — (ВМК
МГУ — школе). — Систем.
требования:
Adobe Reader XI ; экран 10". — Загл. с титул. экрана. —
Текст : электронный.
ISBN 978-5-93208-618-6
Настоящее пособие составлено на основе олимпиадных
задач по математике преподавателями факультета ВМК МГУ
имени М. В. Ломоносова. Пособие содержит теоретический
материал,
подборку
задач,
а
также
указания
и
решения
к большинству задач.
Рекомендуется школьникам 5–7 классов, интересующимся олимпиадными задачами, учителям математики, руководителям кружков и факультативов.
УДК 373.167.1:519.17
ББК 22.176я721.6

Деривативное издание на основе печатного аналога: Олимпиадная математика. Задачи по теории графов с решениями
и указаниями. 5–7 классы : учебно-методическое пособие /
Н. Л. Семендяева, М. В. Федотов ; под редакцией М. В. Федотова. — М. : Лаборатория знаний, 2023. — 175 с. : ил. —
(ВМК МГУ — школе). — ISBN 978-5-93208-328-4.

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений,
установленных
техническими
средствами
защиты
авторских
прав,
правообладатель вправе требовать от нарушителя возмещения убытков
или выплаты компенсации

ISBN 978-5-93208-618-6
© Лаборатория знаний, 2023

ОГЛАВЛЕНИЕ

От редактора
. .. .. .. .. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
4

Предисловие .. .. .. .. .. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
5

Используемые обозначения . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
6

Часть I. Теория и задачи
. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
7

1. Вводные задачи . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .
8

2. Степень вершины, подсчёт числа рёбер .. .. .. .. .. .. .. . 14

3. Связность графов. Эйлеровы графы .. .. .. .. .. .. .. .. .. . 20
4. Маршруты, цепи, циклы, двудольные графы
. .. .. .. . 26

5. Деревья
.. .. .. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 32

6. Плоские графы
. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 36

7. Ориентированные графы
. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 40

Часть II. Указания и решения .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 43

1. Вводные задачи . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 43

2. Степень вершины, подсчёт числа рёбер .. .. .. .. .. .. .. . 66
3. Связность графов. Эйлеровы графы .. .. .. .. .. .. .. .. .. . 96

4. Маршруты, цепи, циклы, двудольные графы
. .. .. .. .118

5. Деревья
.. .. .. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .131

6. Плоские графы
. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .146

7. Ориентированные графы
. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .157

Ответы .. .. .. .. .. .. .. .. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .170

Список литературы
.. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .173

ОТ РЕДАКТОРА

Уважаемый читатель, вы держите в руках одну из книг серии
«ВМК МГУ — школе». Учебно-методические пособия, входящие
в эту серию, являются результатом более чем пятнадцатилетнего труда коллектива авторов, работающих на подготовительных
курсах факультета вычислительной математики и кибернетики
(ВМК) МГУ имени М. В. Ломоносова.
Сейчас изданы пособия по алгебре, геометрии, информатике
и физике для старшеклассников для подготовки к ЕГЭ, олимпиадам и вступительным экзаменам в вузы. Недавно вышли
пособия по математике для подготовки к ГИА для девятиклассников.
Но
мы
не
хотим
останавливаться
только
на
стандартных
задачах,
необходимых
для
сдачи
ГИА
и
ЕГЭ
и
экзаменов
в вузы. Мы хотим, чтобы школьники с младших классов и до
окончания школы могли решать задачи повышенной сложности — олимпиадные задачи, на которые у учителя обычно не
остаётся времени на обычном уроке математики. Большинство
книг по этой тематике выходят без разбивки по классам либо
без разбивки по темам. Многие хорошие книги с олимпиадными
задачами вышли давно и с тех пор
не переиздавались. Мы
собрали много задач из различных старых и не очень старых
сборников олимпиадных задач и предлагаем их вам.
Настоящее
пособие
рассчитано
на
5–7
классы
и
является
пятым в серии пособий по олимпиадным задачам. Будет ещё
несколько книг для 5–7 классов. Параллельно мы уже ведём
работу над сборником задач для 8–9 классов. Завершит серию,
конечно же, пособие для 10–11 классов.
Большинство олимпиадных задач, особенно для младшей и средней школы, не намного сложнее обычных школьных задач по математике. Поэтому не бойтесь их. Они только все вместе выглядят
страшными, а каждая задача по отдельности вполне вам по силам.
Берите их и решайте. Дорогу осилит идущий.

Заместитель декана по учебной работе
факультета вычислительной математики и кибернетики
МГУ имени М. В. Ломоносова,
доцент кафедры математической физики
М. В. Федотов

ПРЕДИСЛОВИЕ

Каждый раздел пособия содержит теоретические основы, описание
методов
решения
задач,
примеры
применения
методов
и набор заданий для решения. Задачи в разделах в основном
расположены по принципу «от простого — к сложному». Аналогичная ситуация имеет место и с последовательностью разделов, поэтому сами разделы и задачи в разделах рекомендуется
изучать в предложенном порядке. Приступать к решению задач
надо после изучения соответствующего теоретического материала и разбора примеров.
После номера задачи в скобках приведены классы, для которых эта задача была предложена на олимпиаде. Однако это разделение на классы довольно условно. Понятно, что если задачу
давали в 5 классе, то её можно давать и в 6–7 классах, и часто,
наоборот, задача, которую давали на олимпиаде для 6–7 классов, вполне по силам пятиклассникам. Поэтому, придерживаясь
рекомендаций в скобках, относитесь к ним творчески. Кстати,
распределение задач по темам тоже не всегда однозначно. Одну
и ту же задачу можно было отнести к разным темам.
В принципе, по этому пособию можно заниматься три года: в 5 классе пройти по всем разделам, выбирая задачи для
5 класса, в 6 классе снова пройти по всем разделам, выбирая
задачи для 6 класса, и так далее. А можно пройти и за более короткий срок: за два года, если вы начали заниматься
в 6 классе, или за один год, если вы уже в 7 классе.

Рекомендуется
школьникам
5–7
классов,
интересующимся
олимпиадными задачами, учителям математики, руководителям
кружков и факультативов.

Желаем удачи!

ИСПОЛЬЗУЕМЫЕ ОБОЗНАЧЕНИЯ

{a}
— множество, состоящее из одного элемента a;
{a1, a2, . . . , an}— множество, состоящее из элементов
a1, a2, . . . , an;
∈
— знак принадлежности элемента множеству;
∪
— знак объединения двух множеств;
=⇒
— следовательно;
⇐⇒
— тогда и только тогда;
N
— множество всех натуральных чисел;
N0 = N ∪ {0};
Z
— множество всех целых чисел;
· · ·
· · ·

— знак системы, означающий, что должны выполняться
все
условия,
объединённые
этим
знаком;
· · ·
· · ·

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

Часть I. ТЕОРИЯ И ЗАДАЧИ

В
этом
пособии
приведены
задачи,
при
решении
которых
используется теория графов.
Теория
графов
не
изучается
в
5–7
классах
общеобразовательных школ. Однако есть задачи, которые легко решаются
с
помощью
теории
графов
и
трудно
или
даже
очень
трудно
решаются
другими
способами.
И
хотя
теория
графов
не
изучается
в
обычной
школе,
для
её
понимания
и
освоения
достаточно знаний по математике, которые даются в средней
школе. Определим понятие графа1).
Пусть
задано
некоторое
непустое
множество
элементов
V
и множество E пар различных элементов из V. Элементы множества V называются вершинами графа, элементы множества E
называются рёбрами графа, а пара (V, E), то есть множество
вершин и рёбер, называется графом.
Для
наглядности
обычно
используют
геометрическое
представление
графа.
Вершины
графа
изображаются
точками
на
плоскости. Если две вершины образуют ребро, то соответствующие две точки соединяют отрезком.
Например, на
рисунке
изображён
граф
G,
заданный
множеством вершин V = {1, 2, 3, 4, 5, 6} и множеством рёбер E =
= {(1; 2), (1; 3), (2; 4), (2; 5), (4; 5)}.

Две вершины, соединённые ребром, называются смежными;
они также называются концами этого ребра. При этом говорят,
что ребро выходит из вершины. Число рёбер, выходящих из

1)Для
желающих
более
подробно
разобраться
с
теорией
графов
рекомендуем книгу [7].

Часть I. Теория и задачи

вершины
v,
называется
степенью
вершины
v
и
обозначается
d(v).
Две
вершины,
не
соединённые
ребром,
называются
несмежными.
Для графа, изображённого на рисунке, d(1) = 2, d(2) = 3,
d(3) = 1, d(4) = 2, d(5) = 2, d(6) = 0. Вершина степени 0 называется изолированной (вершина 6 — изолированная), вершина
степени 1 называется висячей (вершина 3 — висячая). Вершины
1 и 2 являются смежными, а вершины 2 и 3 — несмежными.
Часто удобно рассматривать не весь граф, а какую-то его
часть — подграф. Граф H называется подграфом графа G, если
вершины
и
рёбра
графа
H
принадлежат
графу
G.
Подграф
H графа G называется подграфом, порождённым множеством
вершин {v1, v2, . . . , vp}, если он содержит вершины v1, v2, . . . , vp
и
все
рёбра
графа
G,
соединяющие
эти
вершины.
Подграф
H графа G называется подграфом, порождённым множеством
рёбер {e1, e2, . . . , es}, если он содержит рёбра e1, e2, . . . , es и все
вершины графа G, являющиеся концами этих рёбер.
В
графе
G,
изображённом
на
рисунке,
можно
выделить,
например,
два
подграфа:
H1
с
вершинами
{1, 2, 3}
и
рёбрами
{(1; 2), (1; 3)}
и
H2
с
вершинами
{2, 4, 5}
и
рёбрами
{(2; 4), (2; 5), (4; 5)}. При этом подграф H1 порождён множеством
вершин {1, 2, 3} или множеством рёбер {(1; 2), (1; 3)}, а подграф
H2
порождён
множеством
вершин
{2, 4, 5}
или
множеством
рёбер {(2; 4), (2; 5), (4; 5)}.

1.
Вводные задачи

Теоретический материал

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

Примеры решения задач

Пример 1. Между планетами введено космическое сообщение по
следующим маршрутам: З—К, П—В, З—П, П—К, К—В, У—М,
М—С, С—Ю, Ю—М, М—У. Можно ли добраться с З до М?

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

1. Вводные задачи
9

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

О т в е т. Нет.

Пример 2. В 15-этажном доме имеется лифт с двумя кнопками:
«+7» и «−9». Можно ли проехать с 3-го этажа на 12-й?
Р е ш е н и е. Приведём два способа решения: в первом способе
разберём, до каких этажей можно добраться, стартуя с 3-го
этажа,
а
во
втором,
наоборот,
посмотрим,
с
каких
этажей
можно попасть на 12-й этаж.
Первый способ. С 3-го этажа за один «ход» можно попасть
только
на 10-й, оттуда — только на 1-й, потом — на 8-й, на
15-й, на 6-й, на 13-й, на 4-й, на 11-й, на 2-й и, наконец, на
9-й. А с 9-го этажа никуда проехать нельзя. Поэтому до 12-го
этажа проехать не удастся. Графически это можно изобразить
так:
3 → 10 → 1 → 8 → 15 → 6 → 13 → 4 → 11 → 2 → 9.

Второй способ. На 12-й этаж за один «ход» можно попасть
только с 5-го, туда — только с 14-го, туда — только с 7-го. А на
7-й этаж приехать ниоткуда нельзя.

12 ← 5 ← 14 ← 7.

О т в е т. Нет.

Пример 3. 30 команд сыграли турнир по олимпийской системе.
Сколько всего было сыграно матчей?
Р е ш е н и е. В этой задаче можно не рисовать никаких графов.
За одну игру из турнира с олимпийской системой выбывает
ровно одна команда. Значит, для определения победителя необходимо сыграть 29 игр, чтобы выбыло 29 команд и осталась
одна — победитель.

О т в е т. 29 команд.

Часть I. Теория и задачи

Задачи

1.

✄
✂
✁
5-6 Дима, приехав из Врунляндии, рассказал, что там есть
несколько озёр, соединённых между собой реками. Из каждого озера вытекают три реки, и в каждое озеро впадают
четыре реки. Доказать, что он ошибается.

2.

✄
✂
✁
5-6 Школьный драмкружок, готовясь к постановке отрывка
из сказки А. С. Пушкина о царе Салтане, решил распределить роли между участниками.
— Я буду Черномором, — сказал Юра.
— Нет, Черномором буду я, — заявил Коля.
— Ладно, — уступил ему Юра, — я могу сыграть Гвидона.
— Ну, я могу стать Салтаном, — тоже проявил уступчивость
Коля.
— Я же согласен быть только Гвидоном! — произнёс Миша.
Желания мальчиков были удовлетворены. Как распределились роли?

3.

✄
✂
✁
5-6 Между
девятью планетами
Солнечной
системы введено космическое сообщение. Ракеты летают по следующим
маршрутам:
Земля—Меркурий,
Плутон—Венера,
Земля—
Плутон,
Плутон—Меркурий,
Меркурий—Венера,
Уран—
Нептун, Нептун—Сатурн, Сатурн—Юпитер, Юпитер—Марс
и Марс—Уран. Можно ли добраться с Земли до Марса?

4.

✄
✂
✁
6-7 Король хочет построить шесть крепостей и соединить
каждые две из них дорогой. Начертите такую схему расположения крепостей и дорог, чтобы на ней было только три
перекрёстка и на каждом из них пересекались две дороги.

5.

✄
✂
✁
6-7 Пешеход
обошёл
шесть
улиц
одного
города,
пройдя
каждую
ровно
два
раза,
но
не
смог
обойти
их,
пройдя
каждую лишь раз. Могло ли это быть?

6.

✄
✂
✁
6-7 Города A, B, C и D соединены дорогами так, как показано на рисунке. Сколькими способами можно проделать путь
из города A в город D, побывав в каждом городе ровно по
одному разу?