Графы, отображения
Немного теории
Изображая элементы некоторого множества точками и соединяя некоторые пары точек отрезками, мы получаем наглядное представление для очень популярного объекта дискретной математики. Он называется графом; точки (элементы множества) называются вершинами, отрезки (или дуги) – рёбрами графа. Некоторые вершины графа могут быть не соединены рёбрами. Точки пересечения рёбер графа на его изображении не всегда считаются его вершинами, поэтому вершины графа часто выделяют кружочками.
Вершина называется чётной (нечётной), если она принадлежит чётному (нечётному) числу рёбер. Граф называется чётным, если все его вершины чётные.
Теорема. Количество нечётных вершин в любом графе – чётное число.
Последовательность различных рёбер графа, каждое последующее из которых начинается в конце предыдущего, называется путём. Путь, в котором никакое ребро не встречается дважды, называется простым.
Граф, из любой вершины которого можно пройти в любую другую путём, состоящим из ребер, называется связным. Замкнутый путь по ребрам графа называется циклом. Цикл, который содержит все рёбра графа, называется обходом графа. Обход, при котором каждое ребро графа проходится только один раз, называется правильным.
Теорема. Для произвольного связного чётного графа существует правильный обход, который можно начать в любой вершине и который обязательно заканчивается в ней же.
Теорема. Если связный граф имеет ровно две нечётные вершины, то для него существует правильный обход, причём этот обход в одной нечётной вершине начинается, а в другой – заканчивается.
Теорема. Если в графе больше двух нечётных вершин, то для него невозможен правильный обход.
Связный граф без циклов называется деревом.
Теорема. Граф является деревом тогда и только тогда, когда любые две его вершины соединены ровно одним простым путём.
Теорема. Дерево имеет вершин на одну больше, чем рёбер.
Если все циклы графа имеют чётную длину, то его вершины можно раскрасить в два цвета так, что вершины одного цвета не соединены ни одним ребром; такой граф называется двудольным.
Если на ребрах графа расставить стрелки, то получится ориентированный граф (орграф). Любое отображение f конечного множества А в себя задаёт орграф, из каждой вершины а (элемент множества А) которого выходит одна стрелка – в вершину f(а). (При этом возможны и петли – стрелки, идущие из а в а; они соответствуют неподвижным точкам отображения f.) Если f взаимно однозначное отображение множества А в себя, то орграф распадается на циклы и петли.
Граф, который можно нарисовать так, чтобы его рёбра не пересекались (нигде, кроме вершин), называется плоским (а такое изображение правильным).
Теорема Эйлера. Для правильно изображённого связного плоского графа выполняется равенство:
В + Г – Р = 2,
где В – количество вершин графа, где Г – количество частей (граней), на которые плоский граф разбивает плоскость, где Р – количество рёбер графа.
Теорема Эйлера справедлива так же для произвольного выпуклого пространственного многогранника.
Один из примеров сложного графа – схема телефонной сети.
При решении задач рассматриваются также графы, рёбра или вершины которых раскрашены в несколько цветов, или помечены числами.
Задачи с решениями
1. Существует ли замкнутая ломаная, которая пересекает каждое своё звено ровно один раз и состоит из:
а) 6 звеньев;
б) 7 звеньев?
а) Для любого чётного n > 6 существует замкнутая ломаная из n звеньев, пересекающая каждое своё звено ровно один раз. Пример для n = 6 показан на рисунке 1. Для n > 8 на рисунке 2 показана конструкция части ломаной (правило построения остальной части ясно).
Ответ: существует.
б) Предположим, что удалось построить такую ломаную. Рассмотрим какую-нибудь точку её самопересечения. В ней пересекаются два звена, причём больше ни с какими другими звеньями они не пересекаются. Поэтому все звенья ломаной можно разбить на пары, соответствующие её точкам самопересечения. Значит, звеньев – чётное число и их не может быть семь.
Это рассуждение показывает, что вообще не существует ломаной с нечётным числом звеньев, пересекающей каждое своё звено ровно один раз.
Ответ: не существует.
2. В обществе, состоящем из 2013 человек, среди любых четырех человек можно выбрать, по крайней мере, одного, знакомого с остальными тремя. Каково минимально возможное количество людей, которые знакомы со всеми?
Если незнакомых людей нет, то количество людей, которые знакомы со всеми, равно 2013. Пусть А и В не знакомы друг с другом. Тогда все остальные люди между собой знакомы (если С не знаком с D, то в группе A, B, С, D никто не знаком с остальными тремя). Если А и В знакомы со всеми остальными, то 2011 человек знакомы со всеми. Если же А не знаком также и с С, где С и В различны, то и A, и В, и С знакомы со всеми остальными 2010 людьми (так как в любой группе А, B, С, D только D может быть знакомым с остальными тремя), которые к тому же знакомы между собой. Таким образом, минимальное количество людей, знакомых со всеми, равно 2010.
Ответ: 2010.
3. В трёх вершинах правильного пятиугольника расположили по фишке. Разрешается передвигать их по диагонали в любую свободную вершину. Можно ли таким образом добиться того, чтобы одна из фишек вернулась на свое место, а две другие поменялись местами?
Последовательно пронумеруем вершины пятиконечной звезды (полученной в результате возможных перемещений фишек) числами 1, 2, 3, 4, 5. Видим, что из вершины 1 можно за один ход попасть в вершину 3 или в вершину 4; из вершины 2 – или в вершину 4, или в вершину 5; из вершины 3 – или в вершину 5, или в вершину 1; из вершины 4 – или в вершину 1, или в вершину 2; из вершины 5 – или в вершину 2, или в вершину 3. Эти перемещения становятся более «естественными», если такую пятиконечную звезду «развернуть» в пятиугольник с вершинами пронумерованными в таком порядке: 1, 3, 5, 2, 4.
Тогда перемещениям по сторонам звезды соответствуют перемещения фишек по сторонам пятиугольника из некоторой вершины в одну из соседних (если она не занята). Очевидно, что с помощью таких перемещений по сторонам пятиугольника нельзя изменить порядок размещения фишек, а, значит, нельзя добиться того, чтобы одна из фишек на звезде вернулась на своё место, а две другие поменялись местами.
Ответ: нельзя.
4. Все грани выпуклого многогранника являются треугольниками. Докажите, что каждое ребро этого многогранника можно покрасить в красный или синий цвет так, чтобы в итоге из любой его вершины в любую другую можно было попасть, двигаясь только по красным ребрам, а также только по синим.
Пусть A – вершина многогранника и АА1, АА2, ... , ААn – ребра, из неё выходящие. Ребро АА1 красим в синий цвет, остальные ребра – в красный. Все звенья ломаной А2А3...Аn красим в синий цвет. Ребро А1А2 – в красный. Последовательно добавляем грани, примыкающие к уже покрашенной части многогранника. Если у грани оказались два покрашенных ребра, то третье ребро красим любым цветом, если покрашено одно ребро, то оставшиеся два красим разными цветами.
5. В некотором государстве система авиалиний устроена таким образом, что каждый город соединен авиалиниями не более чем с тремя другими, и из каждого города можно попасть в любой другой, сделав не более одной пересадки.
Какое наибольшее количество городов может быть в этом государстве?
Из любого города А можно добраться не более чем до трёх городов, а из каждого из них не более чем до двух (не считая А). Таким образом, всего городов не более, чем
1 + 3 + 3·2 = 10.
Пример на следующем рисунке показывает, что нужная система авиалиний с десятью городами существует.
Замечание. То, что речь идёт об одном примере, а не о двух – не оговорка. Приведённые выше два графа изоморфны и могут, в некотором смысле, считаться одним и тем же графом. (Два изоморфных графа встречаются и в решении задачи 3.) Этот граф в теории графов часто используется в качестве примера и даже имеет специальное название «граф Петерсена».
Ответ: 10 городов.
6. Клетчатая плоскость раскрашена десятью красками так, что соседние (то есть имеющие общую сторону) клетки покрашены в разные цвета, причём все десять красок использованы. Каково минимально возможное число пар соседних красок? (Две краски называются соседними, если ими покрашены какие-то две соседние клетки.)
Каждому раскрашиванию плоскости поставим в соответствие граф следующим образом. Изобразим краски точками с номерами 1, 2, 3, … , 10. Ясли краски соседние, то соединим соответствующие точки ребром. Тогда каждой паре соседних красок будет соответствовать ребро графа. Очевидно, что из каждой вершины графа выходит хотя бы одно ребро. Полученный граф должен быть связным, потому что иначе плоскость разобьётся на несколько отдельных частей, что невозможно. Наименьшее количество рёбер в связных графах с одинаковым количеством вершин – у дерева. Значит, количество пар соседних красок не может быть меньше чем 9. Остаётся указать такой способ раскрашивания плоскости, при котором количество пар соседних красок равно 9. Это можно сделать, например так, – раскрасить каждую диагональ одной краской, причём краски чередовать в таком порядке:
… 3, 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3 … .
Следующий рисунок даёт зрительное представление предложенного способа раскраски плоскости.
Ответ: 9.
7. На множестве S введено отношение → , которое выполнено для пар элементов из множества S и обладает следующими свойствами:
1) для любых различных элементов a и b из S выполнено ровно одно из отношений а→b или b→а;
2) для любых трех различных элементов a, b, c из S выполнение отношений а→b и b→c влечет за собой выполнение отношения с→а.
Каково наибольшее число элементов, которое может содержать множество S?
Предположим, что в множестве S найдутся три элемента a, b, c такие, что а→b и а→с. Если b→c, то из а→b и b→с следует с→а, что противоречит условию а→с. Если же с→b, то из а→с и с→b следует b→а, что противоречит условию а→b.
Аналогично доказывается, что в S нет элементов а, d, е таких, что d→а и e→а.
Если в множестве S имеется 4 или более элементов (один из которых обозначим через а), то из первого условия задачи следует, что в S найдутся или такие элементы b и с, что а→b и а→с, или же такие элементы d и е, что d→а и е→a. В обоих случаях получаем противоречие. Поэтому в множестве S не более трех элементов.
Пример множества S с тремя элементами а, b, с, удовлетворяющего обоим условиям задачи, может быть таким: а→b, b→с, с→а.
Ответ: 3.
8. Муха села на вершину модели правильного додекаэдра (рисунок 1) и решила обойти его, двигаясь по ребрам додекаэдра; при этом ей удалось посетить все вершины, не побывав ни в одной из них дважды и вернувшись в конце путешествия в исходную вершину. После этого она попробовала обойти тем же способом все вершины ромбического додекаэдра, ограниченного 12 ромбами (рисунок 2). Удалось ли ей это?
Многогранник образует пространственную сеть, сторонами которой являются ребра, узлами – вершины, а ячейками грани многогранника. Дорога мухи должна образовать замкнутую ломаную линию, без кратных точек, принадлежащую указанной выше сети. Возможность выделения такой дороги сохранится, если мы деформируем сеть так, чтобы уместить ее на плоскости.
На рисунке 3 мы видим растянутую на плоскости сеть ребер правильного додекаэдра. Зеленой линией обозначен путь мухи, отвечающий условию задачи.
Теперь подобным же образом растянем на плоскости сеть ромбического додекаэдра (рисунок 4). Узлы сети можно разделить на два класса: на такие, в которых сходятся три ребра, и на такие, в которых сходятся четыре ребра (на рисунке узлы подписаны соответствующим образом).
Каждый узел первого класса соединен отрезком только с узлами второго класса, и наоборот. Поэтому муха во время своего путешествия должна была проходить поочередно через узлы первого класса и узлы второго класса. Так как узлов первого класса восемь, а узлов второго класса шесть, то муха не может посетить всех вершин ромбического додекаэдра, передвигаясь по ребрам так, чтобы не пройти через одну вершину дважды и вернуться к исходной точке.
9. В ориентированном графе 101 вершина. У каждой вершины число входящих и число выходящих ребер равно 40. Доказать, что из любой вершины можно попасть в любую, проходя не более чем по трём ребрам.
Пусть a и b – две вершины данного графа, A – множество из 40 вершин, в которые ведут рёбра из a, B – множество из 40 вершин, из которых идут рёбра в b, C – множество из оставшихся вершин.
Предположим, что из a нельзя пройти в b по трём рёбрам. Тогда все рёбра, выходящие из A, идут в A или в C. Этих рёбер по условию всего 40·40 = 1600. Но рёбер внутри A не больше чем (40·39)/2 = 780, а рёбер, которые выходят из А в С не больше чем 40·19 = 760, что в сумме даёт 1540 < 1600. Полученное противоречие опровергает сделанное предположение. Значит, из любой вершины можно попасть в любую, проходя не более чем по трём рёбрам.
10. На вечере собралось несколько юношей и девушек. При этом оказалось, что если выбрать любую группу юношей, то число девушек, знакомых, по крайней мере, с одним из юношей этой группы, будет не меньше числа юношей в группе. Доказать, что все юноши одновременно смогут танцевать каждый в паре со знакомой девушкой.
Будем решать задачу индукцией по n – числу юношей. Для n = 1 утверждение вытекает из того, что для одного юноши обязательно найдется знакомая девушка. Пусть утверждение доказано для всех чисел, меньших n. Докажем его для числа n. Рассмотрим два случая.
1) Найдется такая группа А из k < n юношей, что общее число всех знакомых с ними девушек равно k. Пусть каждый юноша из этой группы танцует со знакомой девушкой (это возможно в силу предположения индукции). Тогда для оставшихся юношей и девушек условие задачи будет выполнено. Действительно, если имеется группа В из j не входящих в А юношей, то у юношей из объединения множества В с множеством А имеется не менее чем j + k знакомых девушек. Юноши, входящие в А, знакомы в общей сложности не более чем с k девушками. Значит, j юношей из группы В знакомы по крайней мере с j из оставшихся девушек. Таким образом, по предположению индукции, каждый из юношей, не входящих в А, также может танцевать со знакомой ему девушкой.
2) У любой группы из любого количества k < n юношей число знакомых девушек превышает k. Тогда, если один из юношей будет танцевать со знакомой ему девушкой, то множество оставшихся юношей и девушек будет по-прежнему удовлетворять условию задачи. Действительно, любая группа из k < n – 1 оставшихся юношей знакома не менее чем с k + 1 девушками (одна из которых, возможно, уже танцует). Значит, по предположению индукции, каждый из оставшихся юношей также сможет танцевать со знакомой ему девушкой.
Задачи без решений
1. В некотором обществе любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Доказать, что в этом обществе все имеют одинаковое число знакомых.
2. В стране любые два города соединены дорогой с односторонним движением. Доказать, что существует город, из которого можно проехать в любой другой не более чем по двум дорогам.
3. В розыгрыше первенства страны по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трёх команд нашлись две, уже сыгравшие между собой?
4. В некотором поселке 1000 жителей. Ежедневно каждый из них делится узнанными вчера новостями со всеми своими знакомыми. Известно, что любая новость становится известной всем жителям поселка. Докажите, что можно выбрать 90 жителей так, что если одновременно всем им сообщить какую-то новость, то через 10 дней она станет известной всем жителям поселка.
5. В некоторой стране из каждого города в любой другой можно проехать, минуя остальные города. Известна стоимость каждого такого проезда. Составлены два маршрута поездки по городам страны. В каждый из этих маршрутов каждый город входит ровно по одному разу. При составлении маршрута руководствовались следующим принципом: начальный пункт маршрута выбирается произвольно, а на каждом следующем шаге среди городов, через которые маршрут ещё не проходил, выбирается тот, поездка в который из предыдущего города имеет наименьшую стоимость (если таких городов несколько, то выбирается любой из них); и так до тех пор, пока не будут пройдены все города. При составлении второго маршрута начальный город тоже выбирается произвольно, а на каждом следующем шаге среди городов, через которые маршрут ещё не проходил, выбирается тот, поездка в который из предыдущего города имеет наибольшую стоимость. Докажите, что общая стоимость проезда по первому маршруту не больше общей стоимости проезда по второму маршруту.
Создано на конструкторе сайтов Okis при поддержке Flexsmm - накрутка подписчиков в тик ток