Электронное пособие по дискретной математике. Научный форум dxdy

2. Решите следующую задачу по обходу графов:

В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.

Пусть в столицу входит a дорог. Тогда общее число "входящих" дорог равно 21 · 100 +a , а общее количество "выходящих" дорог не больше

20 · 100 + (100-a ). Поэтому 21 100 + а 20 100 + (100 – а), то есть 2а 0.

Таким образом, a = 0.

3.3.2.1. Орграф G1 (V,E): V={a, b, c, d, e, f}, задан как алгебраическая система.

a) Для приведенного отношения задайте орграф геометрически. б) Постройте матрицу смежности орграфа.

0) R = {(а, b), (b, а), (b, с), (с, b), (с, а), (а, с), (d, e), (е, d)};

1) R = {(а, b), (b, a), (b, с), (с, b), (с, d), (d, с), (с, а), (а, с)};

2) R = {(a, b), (b, а), (b, с), (с, b), (с, d), (d, с), (d, e), (e, d)};

3) R = {(а, b), (b, с), (а, с), (b, е), (с, f), (с, d), (d, f), (f, е)};

4) R = {(b, c), (a, d), (b, a), (d, c), (b, d), (с, a), (f, d), (f ,c)};

5) R = {(b, а), (а, а), (b, с), (с, d), (d, с), (d, b), (d, а), (d, e)};

6) R = {(a, b), (а, с), (а, d), (с, а), (d, e), (e, d), (c, c), (d, b)};

7) R={(b, a), (c, с), (а, d), (с, а), (d, e), (e, c), (d, b), (e, f)};

8) R = {(a, b), (а, с), (а, d), (e, а), (d, e), (e, d), (c, b), (d, d)};

9) R = {(a, e), (а, a), (а, d), (с, а), (d, e), (d, d), (c, c), (b, d)}.

3.3.2.2. Орграф задан геометрически. Укажите валентность вершин.

Постройте матрицу смежности орграфа.

8) 1

3.3.2.3. Дана матрица смежности орграфа. а) Задайте орграф геометрически, в) постройте матрицу инцидентности.

        

001100

001000

3.3.2.4. Дана матрица инцидентности орграфа. а) Задайте орграф геометрически, в) постройте матрицу смежности.

3.3.2.5. Решите следующие задачи по обходу графов:

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

1) В некотором государстве каждый город соединен с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы, выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?

2) Утверждают, что в одной компании из пяти человек каждый знаком с двумя другими. Возможна ли такая компания?

3) В некотором государстве 101 город. Все города соединены дорогами с односторонним движением, причем в каждый город входит 50 дорог и из каждого города выходит 50 дорог. Докажите, что из любого города можно доехать в любой другой, проехав не более, чем по двум дорогам.

4) На плоскости даны 6 точек так, что никакие три из них не лежат на одной прямой. Каждая пара точек соединена отрезком синего или красного цвета. Докажите, что среди данных точек можно выбрать такие три, что все стороны образованного ими треугольника будут окрашены в один цвет.

5) В некотором государстве 101 город. Некоторые города соединены дорогами с односторонним движением, причем в каждый город входит 40 дорог и из каждого города выходит 40 дорог. Докажите, что из любого города можно добраться до любого другого, проехав не более, чем по трем дорогам.

6) Можно ли провести в городе 10 автобусных маршрутов и установить на них остановки так, что какие бы 8 маршрутов ни были взяты, найдётся остановка, не лежащая ни на одном из них, а любые 9 маршрутов проходят через все остановки.

7) Жук ползет по ребрам куба. Сможет ли он последовательно обойти все ребра, проходя по каждому ребру ровно один раз? Указание: задумайтесь над вопросом: сколько раз жук может побывать в каждой вершине?

8) Художник нарисовал картину "Контур квадрата и его диагонали". Мог ли он нарисовать свою картину, не отрывая карандаша от бумаги и не проводя одну линию дважды? Указание : из каждой точки, за исключением начала и конца пути карандаша, должно исходить четное число линий.

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

3.3.2.6. Решите следующие задачи по обходу графов:

0) Метро города Урюпинска состоит из трёх линий и имеет, по крайней мере, две конечные станции и, по крайней мере, два пересадочных узла, причём ни одна из конечных станций не является пересадочной. С каждой линии на каждую можно перейти, по крайней мере, в двух местах. Нарисуйте пример такой схемы метро, если известно, что это можно сделать, не отрывая карандаша от бумаги и не проводя два раза один и тот же отрезок. Указание : не забудьте, что бывают кольцевые линии.

3) Доска имеет форму креста, который получается, если из квадратной доски 4 × 4 выкинуть угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу?

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

5) В центре куба 3 3 3 сидит жук. Доказать, что он, переползая через ребра, не сможет обойти все кубики 1 1 1по одному разу.

6) В квадрате 6×6 отмечают несколько клеток так, что из любой отмеченной можно пройти в любую другую отмеченную, переходя только через общие стороны отмеченных клеток. Отмеченную клетку называют концевой, если она граничит по стороне ровно с одной отмеченной. Отметьте несколько клеток так, чтобы получилось а) 10, б) 11, в) 12 клеток.

7) В одной из вершин а) октаэдра б) куба сидит муха. Может ли она проползти по всем его ребрам ровно по одному разу и возвратиться в

исходную вершину? (Примечание : октаэдр представляет собой две четырехугольные пирамиды, склеенные по основаниям.)

8) Как, не отрывая карандаша от бумаги, провести шесть отрезков таким образом, чтобы оказались зачёркнутыми 16 точек, расположенных в вершинах квадратной сетки 4 на 4?

9) Можно ли провести в каждом квадратике на поверхности кубика Рубика диагональ так, чтобы получился несамопересекающийся путь? Указание: на поверхности кубика Рубика всего 54 квадрата.

3.4. Задачи оптимизации на графах

Если дуге ориентированного графа G 1 (V ,E) поставлено в соответствие некоторое вещественное числоa (u ,v ), называемоевесом, то последовательность вершинv 0 ,v 1 ,...,v p определяет путь вG 1 а егодлина

определяется как сумма весов:

a(vi 1 , vi

Если в произвольном

графе вес каждой дуги равен единице, то длина пути равна числу дуг. Задача о кратчайшем пути возникает чаще всего при решении

транспортных и дискретных задач динамического программирования и др. Длину кратчайшего пути обозначаютr (v i ,v j ) и называютрасстоянием отv i доv j (расстояние может быть отрицательным). Для любого орграфа можно построитьматрицу расстояний R=r (i, j). Заполняется матрица построчно, выбирая вершину слева (справа). Значением является наименьшее число дуг, связывающее вершину слева с одной из вершин строки.

Если не существует ни одного пути из v i вv j , то полагаемr (v i ,v j ) = . Если каждый контур нашего графа имеет положительную длину, тократчайший путь будет всегдаэлементарным путем, т.е. в последовательностиv 1 ,...,v p не будет повторов.

Среднее отклонение вершины vi от центра графа D(vi )равно:

D(vi )1 r(vi , v),

m v V

где m - число дуг в графе, v - пробегает вершины графа, n – количество вершин графа, i = 1..n.

Вершина, для которой D(vi ) окажется минимальным, называетсяцентром графа (возможно несколько вершин – центр графа).

Путем или маршрутом на графе G1 (V,E) называется последовательность его вершин и ребер v1e1v2e2v3…vnen vn+1, в которой

любые два соседних элемента инцидентны. Путь называетсяпростым , если всеребра и всевершины на нем, кроме первой и последней, различны.

Маршрут называется цепью , если все его ребра различные. Маршрут называетсяпростой цепью , если все его вершины, а значит и ребра, различные.

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

Цикл называетсяпростым , если в нем нет одинаковыхвершин , кроме первой и последней, т.е. если всевершины различны.

Если в графе нетциклов , то он называетсяациклическим .

Теперь можно иначе определить понятие дерева. Связный граф без циклов называется деревом .

Примеры выполнения заданий

D(2)=D(3)=6/8=3/4;

Итак, центром графа являются вершины 2 и 3.

2. Посёлок построен в виде квадрата 3 квартала на 3 квартала (кварталы - квадраты со стороной b, всего 9 кварталов).Какой наименьший путь должен пройти асфальтоукладчик, чтобы заасфальтировать все улицы, если он начинает и кончает свой путь в угловой точке A? (Стороны квадрата - тоже улицы).

Рис. 6. Кратчайший путь

Понятно, что длина маршрута асфальтоукладчика не меньше 24, так как он должен проехать по каждой улице хотя бы один раз. Докажем, что по крайней мере по четырём улицам ему придётся проехать по два раза. Ровно на восьми перекрёстках пересекается нечётное число улиц.

Следовательно, любой кольцевой маршрут асфальтоукладчика должен проходить по два раза по крайней мере по 8/2 = 4 улицам.Минимальная длина маршрута асфальтоукладчика равна 28; один из возможных маршрутов приведён на рисунке 6.

3. Задайте граф геометрически и решите задачу:

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

Отметим школьников на плоскости точками и соединим стрелочкой, если один кидал во второго. Получившаяся картинка будет выглядеть как несколько циклов с "рожками" (путями, ведущими от точки в цикл). Каждую такую фигуру легко разбить на три группы: разрывая цикл, одного школьника относим в первую группу, а получившиеся деревья разбиваем на четные и нечетные вершины.

Задания для самостоятельного выполнения

3.4.1. Запишите: 1) любой путь, не являющийся цепью; 2) цепь и простую цепь; 3) цикл, простой цикл, если таковые имеются.

3.4.2. Орграф задан геометрически. Постройте матрицу расстояний. Вычислите центр орграфа.

1. Орграф задан геометрически.
Постройте
расстояний.
Вычислите центр орграфа.

1. Доска имеет форму креста, который получается, если из квадратной доски $4 \times 4$ выкинуть угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу?
2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?
3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
4. В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
5. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 -- по 4 друга, а 10 -- по 5 друзей?
6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?
7. У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?
8. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?
9. Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?
10. Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.
11. Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?
12. В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города).
13. Докажите, что граф с $n$ вершинами, степень каждой из которых не менее $(n - 1)/2$, -- связен.
14. В Тридевятом царстве лишь один вид транспорта -- ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний -- одна, а из всех остальных городов -- по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками).
15. В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.
16. а) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?
    б) Какое наименьшее число раз придется ломать проволоку, чтобы все же изготовить требуемый каркас?
17. Докажите, что граф, в котором любые две вершины соединены ровно одним простым путем, является деревом.
18. Докажите, что в дереве любые две вершины соединены ровно одним простым путем.
19. Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).
20. В графе все вершины имеют степень 3. Докажите, что в нем есть цикл.
21. Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.
22. В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?
23. Докажите, что связный граф, у которого число ребер на единицу меньше числа вершин, является деревом.
24. Волейбольная сетка имеет вид прямоугольника размером $50 \times 600$ клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?
25. В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?
26. Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее ребрами так, чтобы он остался связным.
27. В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать в каждом городе, совершив не более
    а) 198 перелетов;
    б) 196 перелетов.
28. В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?
29. В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?
30. Граф, имеющий 5 вершин, каждая из которых соединена ребром с любой другой, не является плоским.
31. Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?
32. Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, -- не плоский.
33. Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.
34. Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо "красный", либо "синий" граф не является плоским.
35. Семиугольник разбит на выпуклые пяти- и шестиугольники, причем так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.

Кружок 6 класса

Руководитель Дмитрий Александрович Коробицын
2011/2012 учебный год

Занятие 3 (08.10.2011). Города и дороги

В некоторой стране а) 6; б) 20 городов, любые два из которых соединены дорогой. Сколько всего дорог в этой стране? в) Докажите, что если число городов равно n , то дорог n (n − 1) / 2 . Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка A на плане) до своего отеля (точка B). Он хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрёстке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет.

Решение. Поменяем немного правила начисления очков: за победу будем давать 2 очка, а за ничью 1 очко. Ясно, что после такой замены все условия задачи сохранятся и каждый из участников наберет целое число. Будем считать, что в этом турнире всего участников было n . Тогда все участники в сумме набрали n (n − 1) очков. Пусть у тех участников, которые набрали равное число очков, по k очков, а у Гоши G очков. Тогда

n (n − 1) = k (n − 1) + G .

Заметим, что G кратно n − 1. Но всего максимум очков могло быть 2(n − 1) (n − 1 тур, в каждом максимум два очка). Значит, G = 0, n − 1 или 2(n − 1). В первом и третьем случае получим то, что нужно доказать, во втором получим n = k + 1, или k = n − 1, но тогда все, в том числе и Гоша, набрали n − 1 очко, но это противоречит условию задачи.

Здравствуйте, использую этот форум что бы проверить следующее доказательство. Вообще эта задача - , но я слышал что ее школьники на олимпиаде решают.

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

Доказательство.
Города - это вершины. Ребра - это дороги.

Выясним, может ли быть граф несвязен. Если компонент больше, чем 3, то тогда выберем 2 вершины из одной, одну из другой и еще одну из третей. Получится, что они могут быть соединены максимум одним ребром. Условие задачи нарушается.
Пусть будет две компоненты, каждая состоит больше, чем из одной вершины. Тогда они должны быть все полными. Если это не так, то возьмем две несмежные вершинки из первой, любые две из другой. В таком наборе может быть соединены только два города. Противоречие. Тоже самое для другой компоненты. Значит, обе полные. Ну тогда берем любую одну вершину из первой и любую одну из второй компоненты. Условие задачи выполнено.
Пусть теперь одна компонента - это просто одна вершина степени 0. Тогда получается, что другая компонента будет из 99 вершин. Если у любой вершины убрать больше, чем два ребра, то сразу нарушение условия: возьмем вершину степени 0, вершину без двух ребер и вершины, к которым ребер от нее нет (1 ребро будет). Значит, у каждой вершины можно убрать только одно ребро. Но если так сделать, то у каждой вершины будет нечетная степень (до этого у каждой было 98). А нечетных степеней может быть только четное число, поэтому либо убираем где-то два ребра и нарушается ограничение о 4-х городах, либо оставляем все ребра и тогда полная вершина.

Города, от которых есть дороги ко всем остальным городам назовем q и p.

Далее доказываем по индукции, что для любого связного графа с ограничением о 4-х городах и г.путем условие будет выполняться.
База. из 4-х вершин очевидна: возьмем любое остовное дерево и в нем выберем вершину, отличную от листа, а вторую - лист.

Переход. Пусть есть граф из вершин. Тогда для всех графов меньше размера, для которых выполнено условие задачи, все доказано.

Необходимо доказать, что можно пользоваться индукционным предположением.
Назовем вершину, которая будет выкинута как .
Если есть граф из вершины, где для любых 4-х городов должны быть две дороги, то и для городов это тоже должно выполняться: будем рассматривать все города без одного. Главное, что бы граф не потерял связность, а это всегда можно делать, удаляя только висячую вершину, если таковая имеется.

Если получилось так, что в образовался г.путь, то не могла быть связна с одним из его концов (иначе г.путь в графе ). Значит, для удаления - это висячая вершина в остовном дереве. Если же получилось так, что так все еще нельзя: была соединена через одну вершину с концом, который удалили, то уберем другую. Одновременно не могло получиться так, что вершина соединена через одну вершину с обоими из концов: это был бы граф на 3-х вершинах (а если есть второй путь до конца, то в есть г.путь), а доказывается для графов, более чем для 4-х вершин.
Очевидно, что от удаления висячей вершины в остовном дереве, связность не теряется.

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

Теперь есть , соединенная с графом из вершин, в этой стране из городов есть свои p и q. Ясно, что если есть ребро от до p или q, то доказывать ничего не нужно. Тогда пусть нет дорог от до p и до q.
Множество, в которые есть дороги из p назовем A, а множество, в которые есть дороги из q, назовем B.
Пусть нет дороги из p в q. Тогда пусть город не соединен дорогой с городом . Но тогда должен иметь дороги и в p и в q, иначе возьмем вершины , , p и q.
Тогда получается, что город не может быть не соединен дорогами с городами из
Но тогда можно сделать город новым p, а q оставить прежней (или наоборот).

Значит, остался один случай: p и q соединены дорогой.
Названия множеств оставим теми же.
По предположению индукции: граф не имеет гамильтонова пути.
Еще раз, если есть дороги от до всего множества или до всего , то уже все доказано.

Теперь есть пара вершин и , от которых нет ребер к .
Если есть только , то кроет все, что не кроет q, - то p. Тогда - новый большой город.
Если пусто, то связна с и все доказано.

Если между и нет ребра, то берем , , и p - будет одно ребро. Значит оно есть. Теперь получается, что - полный подграф, впрочем, как и (иначе берем или , p или q по необходимости и несоединенные вершины).
Теперь расмотрим подграф на вершинах из . Попробуем покрыть все множество веришин простыми путями.
Пусть получилось покрытие только из 4-х простых путей. Возьмем по крайней вершине от каждого: если есть ребро, то можно было соединить две крайние вершины и получить более длинный путь. Получилась антиклика на четырех вершинах. Противоречие.
Теперь известно, что множество покрывается не более чем 3-мя простыми путями. Будем рассматривать каждый простой как одну вершину: если можно прийти в любой из концов, то можно и пройти по каждой вершине внутри него один раз - он же простой, а так можно сделать, т.к. в каждую вершину из можно попасть и через p и через q. Теперь есть только не более 3-х вершин.
Путь может состоять из одной вершины или более. Если более, то отождествляем весь путь его одной крайней вершиной.
Назовем левое множество - , правое - , среднее - (пути сжаты в вершины).
Про вершину можно забыть: если получилось, что имеет г.путь, то уже будет противоречие с индукционным предположением.
Случай 1. Среднее множество пусто. Тогда просто (по вершинам просто) обходим левое множество, ничаная с любой вершины, отличной от , заканчиваем в , потом в p , потом сразу q, потом в и просто обходим правое множество. Получился г.путь.
Случай 2. В среднем множестве одна вершина. Все тоже самое, но из p в q проходим через эту вершину.
Случай 3. Теперь есть в среднем множестве вершины