Практическая работа по дисциплине «Теория вероятностей и математическая статистика» для ОАТК, пример оформления

Решение задач с графами Задача 1 Условие Между девятью планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер, Юпитер – Марс и Марс – Уран. Можно ли добраться с Земли до Марса? Решение Нарисуем схему: планетами будут соответствовать точки, а соединяющим их маршрутам – не пересекающиеся между собой линии. Теперь видно, что долететь от Земли до Марса нельзя. Ответ Нельзя. Задача 2 Условие Несколько Совершенно Секретных Объектов соединены подземной железной дорогой таким образом, что каждый Объект напрямую соединён не более чем с тремя другими, и от каждого Объекта можно добраться под землей до любого другого, сделав не более одной пересадки. Каково максимальное число Совершенно Секретных Объектов? Решение Оценка. Из данного Объекта можно добраться за один «ход» до трёх Объектов, а с пересадкой – еще до  2·3 = 6  Объектов. Следовательно объектов не больше 10. Пример с 10 Объектами изображен на рисунке. Ответ

  Задача 3 Условие Можно ли расположить на плоскости а) 4 точки так, чтобы каждая из них была соединена отрезками с тремя другими (без пересечений)? б) 6 точек и соединить их непересекающимися отрезками так, чтобы из каждой точки выходило ровно 4 отрезка? Решение См. рис. Ответ Можно. Замечания Изображены проекции на плоскость правильного тетраэдра и октаэдра. Задача 4 Условие В некоторой группе из 12 человек среди каждых девяти найдутся пять попарно знакомых. Докажите, что в этой группе найдутся шесть попарно знакомых. Решение Возьмём граф на 12 вершинах, которые соответствуют людям, две его вершины соединены, если люди незнакомы. Если в этом графе нет циклов нечётной длины, то его вершины можно разбить на две части, в каждой из которых вершины не будут соединены. Предположим, что в графе есть циклы нечётной длины. Рассмотрим нечётный цикл минимальной длины. Пусть его длина равна n. Рассмотрим все возможные случаи. 1)  n = 3.  Тогда, если среди девяти человек, не входящих в этот цикл, есть двое незнакомых, то среди оставшихся семи человек из каждых четырёх найдутся трое знакомых (добавим к этим четырём двух незнакомых из девятки и трёх незнакомых из цикла). Отсюда следует, что в подграфе на семи вершинах каждые два ребра имеют общую вершину. Любое третье ребро обязано проходить через эту вершину, иначе среди четырёх человек не найдутся трое знакомых. Поэтому все ребра имеют общую вершину, и, удаляя эту вершину, мы получаем шесть попарно знакомых. 2)  n = 5.  Тогда, как и выше, среди оставшихся семи из каждых четырёх найдутся трое знакомых, и среди этих семи найдутся шесть знакомых. 3)  n = 7.  Тогда среди пяти человек, не входящих в этот цикл, все попарно знакомы (если есть двое незнакомых, то, добавив к ним семерых из цикла, получим противоречие с условием). Если есть человек из цикла, знакомый со всеми этими пятью, то все доказано. В противном случае каждый из цикла не знаком с кем-то из оставшихся. Так как  7 > 5,  то найдётся человек A из оставшихся, не знакомый с двумя из цикла B, C. Из того, что мы взяли нечётный цикл минимальной длины, следует, что B и C должны быть «незнакомы через одного D» (см. рис.). Но тогда D знаком со всеми из пяти оставшихся, потому что удаляя из цикла D на A, мы получаем снова цикл длины 7, а в дополнении к циклу длины 7 все попарно знакомы. 4) Цикла длины 9 нет по условию задачи. 5)   n = 11.  Тогда, как и выше при рассмотрении циклов длины 7, мы видим, что оставшийся человек может быть не знаком максимум с двумя из цикла. Но тогда в цикле легко найти пять человек, знакомых между собой и с оставшимся. (Например, взяв идущих через одного по циклу и знакомых с оставшимся.) Задача 5 Условие В некотором государстве было 2002 города, соединённых дорогами так, что если запретить проезд через любой из городов, то из каждого из оставшихся городов можно добраться до любого другого. Каждый год король выбирает некоторый несамопересекающийся циклический маршрут и приказывает построить новый город, соединить его дорогами со всеми городами выбранного маршрута, а все дороги этого маршрута закрыть за ненадобностью. Через несколько лет в стране не осталось ни одного несамопересекающегося циклического маршрута, проходящего по ее городам. Докажите, что в этот момент количество городов, из которых выходит ровно одна дорога, не меньше 2002. Решение Рассмотрим граф, вершины которого соответствуют городам, а рёбра – дорогам, существовавшим в стране до начала всех преобразований. По условию над этим графом несколько раз подряд проделывается следующая операция: удаляются все рёбра некоторого простого цикла, а все вершины этого цикла соединяются с новой вершиной. Докажем, что в графе, получившемся после окончания всех преобразований, все вершины исходного графа будут иметь степень 1. Поскольку таких вершин ровно 2002, это даст нам полное решение задачи. Рассмотрим произвольную вершину v, принадлежащую исходному графу. По условию, при удалении этой вершины (и всех выходящих из нее рёбер) из исходного графа образуется связный граф. Докажем, что это свойство сохраняется после применения к графу описанной в условии операции. Рассмотрим произвольный граф G и вершину u этого графа, при удалении которой образуется связный граф. Пусть после применения к графу G описанной в условии операции образовался граф G’. Рассмотрим произвольный путь в графе G, не проходящий через u. В графе G’ некоторые ребра этого пути могут быть удалены, но их концы должны быть соединены с новой вершиной (обозначим ее w). Таким образом, заменив минимальный участок пути, содержащий все удаленные ребра, на пару рёбер, соединяющих концы этого участка с вершиной w, мы получим путь в графе G’, имеющий те же концы и не проходящий через u. Это означает, что если мы удалим из графа G’ вершину u, то для каждых двух вершин получившегося графа мы можем найти соединяющий их путь. Для старых (отличных от w) вершин этот путь получается описанным выше способом из пути, соединяющего их в графе, образовавшемся при удалении u из графа G, а вершина w должна быть соединена ребром хотя бы с одной из старых вершин, которая соединена путями со всеми остальными вершинами данного графа. Таким образом, при удалении вершины u из графа G’ связность сохраняется. Из доказанного следует, что после всех преобразований при удалении из получившегося графа вершины v образуется связный граф. Значит, если степень вершины v в получившемся графе больше 1, то между двумя соединёнными с v вершинами есть не проходящий через v путь. Этот путь вместе с вершиной v и двумя выходящими из нее рёбрами образует в получившемся графе простой цикл, что по условию невозможно. Таким образом, степень вершины v в этом графе равна 1. Задача 6 Условие Несколько команд сыграли между собой круговой турнир по волейболу. Будем говорить, что команда А сильнее команды B, если либо А выиграла у B, либо существует такая команда C, что А выиграла у C, а C – у B. а) Докажите, что есть команда, которая сильнее всех. б) Докажите, что команда, выигравшая турнир, сильнее всех. Решение б) Пусть турнир выиграла команда А. Если существует команда B, выигравшая и у А, и у всех команд, проигравших А, то у такой команды очков больше, чем у А, что невозможно. Противоречие.