Лекция 12: Графы - 2 (стр. 11 )

Задача 1. Диверсант выходит из леса в заданной точке (A). Он должен дойти до железной дороги (прямолинейной), заложить там мину и вернуться в лес в другой заданной точке (B), по туже сторону от ж/д (см. рис.). Как ему сделать это, пройдя по кратчайшему пути?

Решение: Нам надо искать кратчайший путь из точки A в точку B, пересекающий данную прямую. Если бы эти точки лежали по одну сторону от прямой (а не так, как на самом деле), мы бы просто соединили их отрезком! Но "если нельзя, но очень хочется, то можно": давайте отразим точку B относительно прямой в точку B' (см. рис. внизу). От A до B' провести путь по прямой уже можно. Теперь как преобразовать путь от A до B в путь от A до B' той же длины? Да очень просто - отразить относительно прямой часть пути после пересечения с ней (точки C или C' на рис.) - ведь симметрия не меняет расстояний. Тогда путь ACB перейдет в путь ACB' той же длины, а путь AC'B - в AC'B' (здесь соответствие путей - взаимно-однозначное!). Путь A'C'B', идущий по прямой, короче любого другого. Значит, исходно кратчайшим был соответствующий ему путь AC'B.

(!) Обратите внимание: AC' и BC' пересекают прямую под одинаковым углом. То есть, путь диверсанта "отскакивает" от прямой по закону "угол падения равен углу отражения" - точь-в-точь, как луч света отражающийся от зеркала. Соответственно, луч света, отражающийся от зеркала, тоже приходит в глаз наблюдателя кратчайшим путем.

Задача 2. AOB - прямой угол, C - точка внутри него. Докажите, что периметр тр-ника ABC меньше 2OC.

Решение: Прямой угол - это как-то несимметрично, некрасиво. Давайте отразим картинку относительно обеих сторон угла, как на рис. внизу. Тогда, раз симметрия сохраняет расстояния, AB=AB1=A1B=A1B1, AC=AC1=A1C2=A1C3 и BC=BC3=B1C1=B1C2. Поэтому P(ABC)=AB+AC+BC=CA+AB1+B1C2 - это длина ломаной из C в C2. А 2OC=OC+OC2 - это расстояние между теми же точками по прямой и оно, безусловно, короче, ч. т.д.

(!) Замкнутый путь - периметр какого-то многоугольника - можно и нужно превращать подобным образом в ломаную, соединяющую 2 различные точки.

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

Комбинирование методов.
Разумеется, наилучшие результаты может дать сочетание методов друг с другом. Рассмотрим такую показательную в этом смысле задачу:
Сумма длин медиан треугольника меньше его периметра.
Решение: Судя по "симметричному" виду задачи, это какая-то алгебраическая комбинация. Разбивать ее на 3 неравенства типа "медиана меньше стороны, к которой она проведена" - неверно, поскольку каждое такое неравенство по отдельности бывает неверно. Разобьем по-другому: пусть, скажем, M - середина стороны BC, AM - медиана (см. рис.). Тогда, оказывается, верно, что AM<(AB+AC)/2. Сложив такие неравенства для трех медиан, получим требуемое.
Как же доказать, что AM<(AB+AC)/2? Воспользуемся одним из типичных преобразования: сделаем центральную симметрию относительно точки M (см. рис.). Действительно получится параллелограмм - это можно доказать по любому признаку. Сумма AB+AC из равенства между AC и A1B будет равна длине ломаной ABA1, что больше, чем отрезок AMA1, равный 2AM. Делим обе части на 2 и получаем ч. т.д.

Лекция 5: Графы.

Понятие графа. Ребра и вершины.
Графом в математике называется картинка из точечек, соединенных палочками (более строгое определение существует, но на практике никогда не требуется). Эти точечки называются вершинами графа, а палочки (они могут быть и кривыми; некоторые графы вообще невозможно нарисовать так, чтобы все палочки были прямыми) - ребрами графа. Две вершины, соединенные ребром, называются соседними. Последовательность ребер, соединяющих две вершины, называется путем.
(!) Поскольку теория графов не входит в школьную программу по математике, то в условиях олимпиадных задач не бывает слова "граф". Однако задачи по теории графов легко узнаваемы - чаще всего это задачи про людей и знакомства (а также прочие виды отношений), либо про города и дороги (и прочие линии связи).
Ориентированный граф - это граф на ребрах которого расставляются стрелочки, и проводить пути разрешается только в направлении стрелочек. Типичные формулировки задач - про дороги с односторонним движением, либо про односторонние отношения между людьми.
Одинаковые по структуре графы называются изоморфными, при этом они могут рисоваться совершенно по-разному. Точное определение изоморфизма: вершины обоих графов можно занумеровать так, что две вершины в одном графе соседние тогда и только тогда, когда соседние две вершины с теми же номерами в другом графе. Например, изоморфизм графов, изображенных внизу, внешне неочевиден, но проверяется по определению.

Для изоморфизма ориентированных графов требуется также, чтобы направение ребер между вершинами с одинаковыми номерами было одинаковым.
(!) Возможны графы с некоторыми крайними случаями: существование в ориентированном графе 2-х ребер, соединяющих одну и ту же пару вершин в разных направлениях (встречается чаще всего); наличие в неориентированном графе нескольких ребер между одними и теми же двумя вершинами (но это можно легко побороть); наличие в графе "петель" - ребер, соединяющих вершину с самой собой. Всегда следует выяснять, какие из этих ситуаций могут присутствовать в данной задаче, и какие из них можете получить вы сами, проводя преобразования графа. В этой лекции мы будем предполагать отсутствие таких особенностей.

Степени вершин, число ребер и четность.
Степенью вершины в графе называется число выходящих из нее ребер. В ориентированном графе у каждой вершины есть 2 степени: входящая (число ребер, входящих в вершину) и исходящая (число ребер, выходящих из вершины). Мы говорим, что вершина графа четная, если ее степень четна, и что вершина нечетная - в противном случае (в графе на рис. наверху все вершины четные). Для ориентированного графа понятие четности вершины обычно не вводится.
В графе степени вершин и количество ребер связаны важными соотношениями:

Примеры:

Задача 1. В государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 5 дорог и города Горный, откуда выходит одна единственная дорога. Сколько всего дорог в государстве?
Решение: Сложим количества дорог, выходящих из всех городов: 98*2+5+1=202. Это число - количество концов всех дорог. Поскольку каждая дорога имеет 2 конца, то количество дорог будет вдвое меньше, а именно 101.

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

Задача 2. На остров Коневец завезли 13 телефонов. Настоятель хочет организовать такую схему телефонной связи, чтобы соединить каждый телефон ровно с 7-ю другими. Удастся ли ему это?
Решение: Посчитаем, сколько проводов нужно, чтобы осуществить такую схему. Концов проводов будет 13*7=91, а самих проводов - вдвое меньше, то есть... 45,5 штук. Это означает, что такая схема связи невозможна.

Утверждение. Число нечетных вершин любого графа четно (именно это свойство мешает построить сеть связи в предыдущей задаче).
Доказательство: Вспомним утверждение из лекции 1: сумма нескольких целых чисел четна тогда и только тогда, когда среди чисел четное число нечетных. Применим это к степеням вершин: сумма степеней вершин четна тогда и только тогда, когда нечетных вершин четное число. Но сумма степеней вершин всегда четна (она ровно вдвое больше числа ребер). Значит, и четных вершин всегда четное число ч. т.д.

Компоненты связности.
Назовем граф связным, если любые 2 вершины могут быть соединены путем из ребер. Несвязный граф состоит из нескольких кусков, каждый из которых связен. Такие куски называются компонентами связности. Любой связный граф состоит из одной компоненты связности - всего графа. Например, граф на рисунке сверху состоит из двух компонент связности: одна содержит вершины с номерами от 1 до 8, а вторая - вершину с номером 9. В ориентированном графы есть разные виды связности: односторонняя и двухсторонняя. Относительно последней граф тоже разбивается на компоненты связности.

Примеры:

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

(!) Следует обратить внимание на предложенный прием - рассмотреть компоненту связности как отдельный связный граф и применить какое-либо утверждение к этому графу.

Задача 4. На острове Коневец 13 привезенных телефонов соединили между собой, причем из каждого телефона выходит не меньше 6-ти проводов Доказать, что а)с любого телефона можно связаться с любым; б)это можно сделать, используя не более чем 1 телефон в качестве промежуточной станции.
Решение: Поскольку четность степеней вершин нам неизвестна, то соответствующим утвержднием мы пользоваться не будем. Зато, поскольку на степени вершин есть оценка снизу, то оценим снизу размер компонент связности. В любой компоненте связности есть хотя бы 1 вершина (1 телефон), а вместе с ней - все ее соседи (соединенный с ним проводами), не меньше 6 штук. Всего будет не меньше 7 вершин.
а) Если бы в графе было хотя бы 2 компоненты связности, то было бы не меньше 2*7=14 вершин. А раз вершин всего только 13, то компонента одна, т. е. граф связен, ч. т.д.
б) Нам надо доказать, что любые две вершины - либо соседи, либо имеют общего соседа. Это означает, что любые два "пучка" пересекаются (пучком будет называть множество из одной вершины - "центра пучка" - и всех ее соседей). Но в прошлом пункте мы оценивали компоненты связности именно пучком. Там мы доказали, на самом деле, что в любом пучке не менее 7 вершин, поэтому двух непересекающихся пучков в графе из 13 вершин быть не может, ч. т.д.