ТГиК-2019-Семинар-11.11.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Задачи на семинар и самостоятельную работу

1.Условие:

Доказать, что

  а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;

  б) в дереве с n вершинами ровно  n – 1  ребро;

  в) в дереве не меньше двух висячих вершин;

  г) в связном графа из n вершин не меньше  n – 1  ребра;

  д) если в связном графе n вершин и  n – 1  ребро, то он – дерево.

Решение:

а) Если граф – не дерево, то в нём есть простой цикл. Любое ребро из этого цикла можно выкинуть без нарушения связности. Этот процесс остановится, когда граф станет деревом.

б) У дерева есть висячая вершина. Удалим её вместе с ребром, которое из нее выходит. Оставшийся граф также является деревом. Поэтому у него есть висячая вершина, которую мы также удалим вместе с выходящим из нее ребром. Проделав эту операцию  n – 1  раз, мы получим граф, состоящий из одной вершины (в котором, конечно, нет рёбер). Поскольку каждый раз удалялось ровно одно ребро, то сначала их было  n – 1.

в) Выйдем из висячей вершины и пойдём по графу . Так же как и там этот путь закончится в другой висячей вершине.

г) Удалим из графа несколько вершин, превратив его в дерево. В полученном дереве  n – 1  вершина, а в иcходном – не меньше.

д) Если это не так, то, превратив его в дерево, мы получим противоречие с п. б).

2.Условие:

Докажите, что в любом графе

  а) сумма степеней всех вершин равна удвоенному числу рёбер (и следовательно, чётна);

  б) число вершин нечётной степени чётно.

Решение:

  а) При сложении степеней вершин каждое ребро учитывается дважды: по разу для каждой из вершин, которые оно соединяет.

  б) Сразу следует из а) и того очевидного факта, что сумма нечётного числа нечётных чисел нечётна.

3.Условие:

Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток. Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски?

Решение:

Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а рёбрами – верёвочки. В этом графе нужно удалить как можно больше рёбер так, чтобы он остался связным. Будем убирать рёбра по очереди до тех пор, пока это возможно. Заметим, что если в графе есть цикл, то возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Подсчитаем число рёбер в нашем графе в этот момент. Количество вершин осталось тем же –  51·601 = 30651.  Число рёбер в дереве на единицу меньше, то есть их 30650. Сначала же их было  601·50 + 600·51 = 60650.  Таким образом, можно удалить 30000 рёбер (но не более!).

4.Условие:

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

Решение:

Соединим эти две вершины A и B путем. Пусть a – его длина. Расстояние от любой вершины до A и B отличаются на величину, имеющую ту же чётность, что и a. Поэтому если число вершин чётно, то (независимо от чётности a) удаленности A и B отличаются на чётное число, что противоречит условию.

5.Условие:

Пусть связный плоский граф с V вершинами и E рёбрами разрезает плоскость на F кусков. Докажите формулу Эйлера:  V – E + F = 2.

Решение

Будем удалять рёбра по одному, пока граф не превратится в дерево. На каждом шаге число как число рёбер, так и число кусков уменьшается на 1 (при удалении ребра два примыкающих к нему куска сливаются в один). Поэтому величина  V – E + F  не меняется. Но для полученного дерева она равна 2, поскольку  E = V – 1 , а  F = 1.

6.Условие:

В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?

Решение:

Будем считать отмеченные точки и вершины квадрата вершинами, а соединяющие их отрезки и стороны квадрата – рёбрами плоского графа. Для каждого куска, на которые этот граф разбивает плоскость, подсчитаем число ограничивающих его рёбер, и все полученные числа сложим. Поскольку каждое ребро разделяет два куска, то в итоге получим удвоенное число рёбер. Так как все куски, кроме внешнего – треугольники, а внешний кусок ограничен четырьмя рёбрами, то  3(F – 1) + 4 = 2E,  то есть  E = 3(F – 1) : 2 + 2.  Заметим, что число вершин нашего графа равно 24 и подставим количества вершин и рёбер в формулу Эйлера :  24 – (½ (F – 1) + 2) + F = 2.

Отсюда  F = 43.  Таким образом, число треугольников, на которые разбился квадрат, равно 42.

7.Условие:

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

Решение:

Обозначим количество линий у авиакомпаний через a, b и c. Если мы закроем последние c авиалиний, то граф останется связным, поэтому  a + b ≥ 14 . Аналогично,  b + c ≥ 14,  c + a ≥ 14.  Складывая эти неравенства, получаем:  2(a + b + c) ≥ 42,  то есть у трёх компаний в сумме не менее 21 авиалинии.

8.Условие:

Туристическая фирма провела акцию: "Купи путевку в Египет, приведи четырёх друзей, которые также купят путевку, и получи стоимость путевки обратно". За время действия акции 13 покупателей пришли сами, остальных привели друзья. Некоторые из них привели ровно по четыре новых клиента, а остальные 100 не привели никого. Сколько туристов отправились в Страну Пирамид бесплатно?

Решение:

Каждый из x "счастливчиков" привёл по 4 друга. Тогда "приведённых" клиентов 4x, еще 13 пришли сами, значит, всего туристов было  13 + 4x.  С другой стороны, x человек привели новых клиентов, а 100 – не привели, то есть всего туристов было  x + 100.  Итак,  13 + 4x = x + 100,  откуда  x = 29.