Подборка задач и теории для 6-7 класса.
Автор: Пятков Александр Дмитриевич
Данный материал раскрывает основные определения и теоремы темы «графы». Данная тема помогает решать множество олимпиадных задач по математике, а также помогает понять часть принципов используемых в программировании.
Графы ведение
Граф — совокупность точек, некоторые из которых соединены отрезками. Точки называются вершинами графа, отрезки ребрами.
1.В деревне 9 домов. Известно, что у Гоши соседи Иван и Роман, Максим сосед Ивану и Михаилу, Виктор — Алексею и Андрею, а также по соседству живут Константин с Андреем, Иван с Михаилом, Константин с Алексеем, Михаил с Романом и больше соседей в означенной деревне нет (соседними считаются дворы, у которых есть общий участок забора). Может ли Гоша огородами пробраться к Андрею за яблоками?
2.В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?
3.В некотором государстве 6 городов и 10 автодорог, каждая из которых связывает какие-то два города. Между городами устанавливается авиационное сообщение, исходя из принципа экономии: авиационная линия между двумя городами устанавливается тогда и только тогда, когда автомобильная дорога между этими городами отсутствует. Сколько авиалиний будет проведено?
Степень вершины — количество ребер, выходящих из данной вершины.
4.В стране 1329 городов, из каждого выходит по 4 дороги. Сколько всего дорог в стране?
5.Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.
6.Вася считает, что в его классе у всех разное число друзей-одноклассников. Не ошибается ли он?
7.Иван утверждает, что среди любых а) четырёх; б) пяти; в) шести человек обязательно найдётся либо трое знакомых друг с другом, либо трое незнакомых. Не завирается ли он?
8.Петя заметил, что у всех его 25 одноклассников различное число друзей в этом классе. Сколько друзей у Пети? (Укажите все решения.)
Дополнительные задачи
9.Докажите, что существует граф с 2n вершинами, степени которых равны 1, 1, 2, 2, ..., n, n.
10.Докажите, что не существует многогранника, у которого было бы ровно семь ребер.
11.Верно ли, что два графа изоморфны, если
а)у них по 10 вершин, степень каждой из которых равна 9?
б)у них по 8 вершин, степень каждой из которых равна 3?
в)они связны, без циклов и содержат по 6 ребер?
12.В некотором городе на любом перекрестке сходятся ровно 3 улицы. Улицы раскрашены в три цвета так, что на каждом перекрестке сходятся улицы трех разных цветов. Из города выходят три дороги. Докажите, что они имеют разные цвета.
Эйлеровы графы
1.Волшебная страна Фарг почти вся состоит из непреодолимых гор и рек. В ней есть шесть городов: А, Б, В, Г, Д и Е. Известно, что из А проложены дороги в Б и Г, из Б — в А, Г и Д, из В — в Г и Е, из Г — в В и Д, из Д — в Б и Г, из Е — только в В. Все остальные дороги непроходимы.
а)Нарисуйте карту страны Фарг.
б)Нарисуйте карту так, чтобы дороги не пересекались.
в)Может ли житель города А попасть в город Д, если ему нельзя проходить через Г?
г)Сможет ли он при тех же условиях попасть в город Е?
Будем называть графом набор точек (вершин), некоторые из которых соединены между собой линиями (рёбрами). Граф называется связным, если от любой его вершины можно по рёбрам добраться до любой другой (и несвязным иначе). Степенью вершины называется число выходящих из нее ребер. Два графа будем называть одинаковыми, если выполнены следующие два условия:
1)у них равное число вершин;
2)вершины каждого графа можно пронумеровать так, что если вершины с номерами i и j соединены ребрами в одном графе, то вершины с теми же номерами соединены таким же числом рёбер и в другом графе, а если вершины с номерами i и j не соединены ребром в одном графе, то вершины с теми же номерами не соединены и в другом графе.
2.Найдите все наборы одинаковых графов:
3.Найдите количество:
а)графов с двумя вершинами; б)графов с тремя рёбрами;
в)связных графов с тремя рёбрами; г)несвязных графов с четырьмя вершинами.
4.Можно ли начертить данные графы одним росчерком (не отрывая руки от бумаги и не проходя по ребру дважды)?
5.Докажите, что граф с более чем двумя вершинами нечётной степени невозможно начертить одним росчерком (не отрывая ручки от бумаги и не проводя никакое ребро дважды).
6.Дана проволока длиной 12 см. Можно ли сложить из нее каркас куба с ребром в 1 см? Проволоку нельзя резать.
Разные задачи
7.Докажите, что среди любых шести человек обязательно найдутся либо три попарно знакомых, либо три попарно незнакомых.
8.Пешеход обошел шесть улиц одного города, пройдя каждую ровно два раза, но не смог обойти их, пройдя каждую лишь один раз. Могло ли такое быть, если в городе нет тупиков?
Двудольные графы
Определение : Граф называется двудольным, если его вершины можно раскрасить в два цвета так, чтобы рёбра соединяли только пары вершин разного цвета.
Теорема о числе рёбер двудольного графа.
а) Если в двудольном графе п белых вершин, и все они имеют степень s, то всего в графе ns рёбер.
б) Число рёбер равно сумме степеней всех белых вершин (а также равно сумме степеней всех чёрных вершин).
Лемма о рукопожатиях
Сумма степеней всех вершин графа равна удвоенному количеству рёбер.
-----------------------------------------------------------------------------------------------------------------------------------------------
Задача 1. Нарисуйте двудольный граф, где чёрные и белые вершины — это соответственно чёрные и белые клетки доски 3 х 3, а рёбра соответствуют ходам коня.
Задача 2. Каждый граф можно превратить в двудольный, покрасив все его вершины в белый цвет и добавив чёрную вершину в середину каждого ребра. Сколько вершин каждого цвета и сколько рёбер у полученного графа, если у исходного было v вершин и г рёбер?
Задача 3. В классе 20 человек. На праздник каждый мальчик подарил каждой девочке по цветку.
а) Какое наибольшее число цветков могло быть подарено?
б) Тот же вопрос, если в классе 21 человек.
в) Сформулируйте теорему о максимальном количестве рёбер в двудольном графе с 2п вершинами; с 2п + 1 вершинами.
Задача 4. Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?
Задача 5. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 — по 4 друга, а 10 — по 5 друзей?
Задача 6. Джон, приехав из Диснейленда, рассказывал, что там, на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?
Задача 7. Докажите, что связный граф, в котором степень каждой вершины чётна, при удалении любого ребра остаётся связным.
Задача 8. В шахматном турнире в один круг участвуют 17 человек. Верно ли, что в любой момент турнира найдется шахматист, сыгравший к этому моменту четное число партий(может быть, ни одной)?
Задача 9. Футбольный мяч сшит из 32 лоскутов: белых шестиугольников и черных пятиугольников. Каждый черный лоскут граничит только с белыми, а каждый белый – с тремя черными и тремя белыми. Сколько лоскутов белого цвета?
Деревья
Определение: Связный граф без циклов называется деревом.
Теорема 1. В любом дереве (в котором более одной вершины) есть вершина, из которой выходит ровно одно ребро.
Теорема 2. В дереве количество вершин на 1 больше количества рёбер:
V = Е + 1.
Теорема 3. Из любого связного графа можно удалить часть рёбер (не удаляя вершин) так, чтобы осталось дерево.
Его называют остовным деревом графа или каркасом графа.
------------------------------------------------------------------------------------------------------------
Задача 0. Выделите остовное дерево в полном графе из 4, 5, 6 вершин.
Задача 1. Нарисуйте все деревья с пятью вершинами. Объясните, почему других деревьев нет.
Задача 2. В графе все вершины имеют степень три. Докажите, что в нём есть цикл.
Задача 3. Докажите, что в дереве (в котором больше одной вершины) найдутся хотя бы две висячие вершины.
Задача 4. Волейбольная сетка имеет вид прямоугольника размером 50 х 600 клеток. Какое наибольшее число раз можно разрезать составляющие сетку верёвочки так, чтобы сетка не распалась на куски?
Задача 5. Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.
Задача 6. Докажите, что связный граф, в котором вершин на одну больше, чем ребер, является деревом (то есть не содержит циклов).
Микс
Задача 1. В некотором государстве 99 городов, некоторые пары городов соединены дорогами длиной в 1, 3 или 5 вёрст, причём от каждого города до каждого по этим дорогам можно добраться ровно одним способом. Из каждого города в каждый другой отправились гонцы с важным донесением. Докажите, что суммарное расстояние, пройденное гонцами, делится на 4.
Задача 2. На Малом Мехмате дети договорились послать друг другу электронные письма. Те из них, у кого число знакомых чётно, отправят письма всем знакомым, а те, у кого число знакомых нечётно, отправят письма всем незнакомым. Придя домой и включив компьютер, Гоша увидел, что ему пришло 99 писем. Докажите, что он получит ещё хотя бы одно.
Задача 3. Докажите, что среди любых шести человек всегда найдутся либо трое попарно знакомых, либо трое попарно незнакомых.
Задача 4. На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече?
Задача 5. Можно ли раскрасить ребра куба в красный и чёрный цвета так, чтобы муравей мог пройти из любой вершины в любую, гуляя только по красным ребрам, а жук — только по чёрным?
Задача 6. Из спичек выложили клетчатый квадрат 8 х 8 со стороной клетки в одну спичку. Какое наименьшее число спичек надо убрать, чтобы с любой клетки на любую другую можно было пройти, не перепрыгивая через спички?
Задача 7. На плоскости дано 100 окружностей, составляющих связную фигуру. Доказать, что эту фигуру можно нарисовать, не отрывая карандаша от бумаги, и не проводя дважды одну и ту же линию.
Задача 8. В стране Древляндия 101 город, некоторые из них соединены дорогами. При этом любые два города соединяет ровно один маршрут. Сколько в этой стране дорог?
