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

Рассмотрим несколько примеров, при решении которых успешно применяются графы.

Задача 1. Один из ребят сказал: «А у нас в группе 25 человек, и каждый дружит ровно с семью одногрупниками!» «Не может быть этого», - ответил приятелю Витя Иванов, студент старшего курса. Почему он так ответил?

Решение. Представим всех ребят в группе в виде вершин графа. Получим 25 вершин. Соединим вершины, обозначающие друзей, ребрами. Тогда из каждой вершины будет выходить по семь ребер. Сумма степеней вершин графа будет равна %%25x7=175%%. Это нечетное число. А нам известно, что сумма степеней вершин графа должна быть четна. Получили противоречие.

Задача 2. В стране 15 городов, каждый соединен дорогами не менее чем с 7-ю другими. Докажите, что из любого города можно проехать в любой другой либо напрямую, либо через один промежуточный город.

Решение. Рассмотрим город А. Он соединен дорогами с не менее чем семью городами В1, В2, …, В7, … Всего получилось не меньше 8 городов. Предположим, что есть город С, не связанный ни с А ни с В1, В2, …, В7, … Значит он связан только с теми городами, которые остались вне этого списка. Но таких городов меньше 7, что противоречит условию.

Задача 3. В классе 28 человек. Каждая девочка дружит с 4 мальчиками, а каждый мальчик – с 3 девочками. Сколько в классе мальчиков и девочек?

Решение. В графе, для этой задачи вершины, соответствующие мальчикам, выкрасим синим цветом, а вершины, соответствующие девочкам – красным. Каждое ребро графа соединяет ровно две вершины: одну синюю и одну красную. Пусть всего x красных и y синих вершин (%%x+y=28%% – уравнение №1). Выразим количество ребер в графе. С одной стороны, оно равно %%3x%%, с другой – %%4y%%. Получим уравнение №2: %%3x=4y%%. Решая систему из двух уравнений, легко найти, что %%x=16%%, а %%y=12%%.

Задача 4. Докажите, что среди учеников любого класса найдутся двое, имеющие одинаковое число знакомых в этом классе (если, конечно, в этом классе не менее двух учеников).

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

Задача 5. Расположите на плоскости 6 точек и соедините их непе­ресекающимися линиями так, чтобы из каждой точки вы­ходили четыре линии.

Решение. Смотри рисунок 12.

Рисунок 12. Плоская укладка графа с шестью вершинами.

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

Решение. План марсианского метро является связным графом. Возможны два варианта:

1 случай. Граф является деревом. Тогда этот граф имеет «висячую» вершину. Ее и следует перекрыть.

2 случай. Граф имеет циклы. Тогда нужно перекрыть одну из станций, принадлежащих этому циклу.