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

Задача 2. В королевстве каждый город соединен с каждым дорогой. Может ли сумасшедший король ввесте на дорогах одностороннее движение так, чтобы выехав из любого города, в него нельзя было вернуться?.
Решение: Тут мы имеем дело с другим видом задач: введением ориентации (с заданными свойствами) на обычном графе. Попробуем придумать простенькие примеры (см. рис.).

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

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

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

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

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

Задача 4. Докажите, что в полном ориентированном графе есть вершина, из которой можно добраться до любой другой.
Решение: Как и говорилось ранее, индукция по числу вершин. База - 1 вершина - очевидна.
Переход: от N вершин к N+1 вершине. Возьмем полный ориентированный граф с N+1 вершиной - и одну вершину (A) выкинем. По предположению индукции, в оставшемся графе есть вершина B, из которой можно доехать до всех остальных. Если откуда-то ведет ребро в A, то из B можно доехать и до A, то есть B - та самая вершина, которую мы ищем. Иначе, из A ведут ребра во все вершины, и искомой вершиной будет A. В любом случае, такая есть, ч. т.д.

Задача 5. Докажите, что в полном ориентированном графе с тремя и более вершинами можно поменять направление одного ребра так, чтобы сделать его сильно связным (если он исходно не сильно связный).
Решение: База - 3 вершины. Если граф не сильно связный, то он изоморфен примеру с 3-мя вершинами к задаче 2. А там можно развернуть одно ребро так, чтобы получить ориентированный цикл длины 3.
Переход: опять же, давайте удалим вершину, сделаем оставшийся граф сильно связным (по предположению индукции) и вернем вершину на место. Чтобы после возвращения граф сохранил сильную связность, удаленная вершина должна иметь как входящие, так и выходящие ребра. А если такой вершины нет??? Тогда рассмотрим вершину A, из которой все ребра выходят (очевидно, что откуда-то ребра должны выходить), и любые другие вершины B и C. В B и C ведут ребра из A, поэтому в них все ребра входят. Но как же быть с ребром BC??? Оно должно выходить из одной из этих вершин?! Значит, такое невозможно, ч. т.д.

Лекция 14: Геометрия - 2.

Еще о неравенствах. В лекции "Геометрия", доказывая неравенство треугольника, мы использовали факт: в треугольнике против большего угла лежит большая сторона. Это неравенство, обратное к нему ("против большей стороны лежит больший угол") и само неравенство треугольника - вот и все фундаментальные факты из геометрических неравенств. Их доказательство можно легко найти в школьном учебнике геометрии.
Более того, можно экспериментально заменить, что чем сильнее отличаются стороны треугольника, тем сильнее отличаются противолежащие углы. Точно это формулируется в теореме синусов: стороны треугольника пропорциональны синусам противолежащих углов. Ее доказательство тоже можно найти в школьном учебнике геометрии, уже в программе 9 класса. Но для неравенств она не особо нужна ;-)

Задача 1. В треугольнике ABC медиана AM больше половины стороны BC. Докажите, что ^BAC острый.
Решение: В треугольниках ABM и ACM стороны BM и CM равны BC/2 и меньше AM, поэтому меньше и противолежащие углы: ^ABM>^BAM, ^ACM>^CAM. Сложим эти два неравенства, заметив, что сумма углов в правой части - ^BAC. Получаем для треугольника ABC: ^B+^C>^A, откуда ^A<(^A+^B+^C)/2=90 градусов, т. е. острый, ч. т.д. (Никогда не надо забывать, что сумма углов треугольника - 180 градусов!)
Упражнение. Доказать, что в треугольнике ABC ^BAC прямой, если медиана AM равна BC/2 и тупой, если AM<BC/2. (Тогда будет верно и обратное соответствие: если ^BAC острый, то AM>BC/2 и т. п.)

Задача 2. Центры трех непересекающихся окружностей лежат на одной прямой. Четвертая окружность касается этих трех. Докажите, что ее радиус больше радиуса одной из них.
Решение: Обозначим центры первых трех окружностей (в порядке расположения на прямой) A, B и C, а их радиусы - RA, RB и RC соответственно. Центр четвертой окружности и ее радиус обозначим D и и RD. Теперь воспользуемся неравенством треугольника для ACD: AD+CD>AC. Очевидно, что если окружности касаются, то у них расстояние между центрами равно сумме радиусов, откуда AD+CD=RA+RD+RC+RD=RA+RC+2RD. У непересекающихся окружностей (тоже очевидно) расстояние между центрами больше суммы радиусов, откуда AC=AB+BC>RA+RB+RC+RB=RA+RC+2RB. Теперь имеем RA+RC+2RD>RA+RC+2RB, то есть RD>RB, ч. т.д.

Движения плоскости: основные свойства. Движением называется отображение плоскости (или пространства) в себя, сохраняющее расстояния. Основные виды движений: параллельный перенос, поворот, осевая и центральная симметрия (см. рис., слева направо). На самом деле, осевая симметрия - это поворот на 180 градусов, и ее правильнее считать частным случаем поворота. Кроме того, разнообразие движений не исчерпывается этими четырьмя типами (но исчерпывается композициями трех разнотипных - см. ниже).

1. Осевая симметрия (см. рис. слева), то есть зеркальное отражение, в отличие от других движений, меняет ориентацию плоскости. Если (см. рис.) посмотреть из A вдоль отрезка AB, то точка C будет справа, а если из A' вдоль отрезка A'B' - то C' будет уже слева. Это изменение и есть изменение ориентации. Множеством неподвижных точек (т. е. точек, переходящих в себя) при осевой симметрии является прямая, относительно которой мы отражаем, называемая ось симметрии. Симметрия однозначно определяется своей осью
2. Поворот (см. рис. в центре) и центральная симметрия, не меняют ориентацию плоскости. Множество неподвижных точек поворота - это одна точка, вокруг которой производится поворот - центр поворота (или, соответственно центр симметрии). Поворот однозначно определяется своим центром и углом поворота.
3. Параллельный перенос (см. рис. справа) не меняет ориентацию плоскости и не имеет неподвижных точек. Он однозначно определяется вектором, то есть направленным отрезком, на который сдвигаются точки при переносе (если вы не знакомы с векторами, проще думать, что перенос определяется направлением и расстоянием, на которые переносятся точки).

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

Утверждение. Движение переводит треугольник в равный ему треугольник.
Доказательство: Возьмем треугольник ABC и точки A', B', C', в которые его вершины переходят при движении. Мы уже знаем, что точки A', B' и C' тоже образуют треугольник, и стороны ABC переходят в стороны A'B'C'. Поскольку движение сохраняет расстояния, то стороны этих треугольников соотвественно равны, и тогда сами треугольники равны, (3-й признак равенства из школьного учебника) ч. т.д.
Следствие. Движение сохраняет углы (т. е. любой угол переходит в равный ему)
Действительно, отложим на сторонах угла две точки и рассмотрим треугольник, образованный ими и вершиной. Он переходит при движении в равный треугольник, а искомый угол - в равный ему соответственный угол, ч. т.д.
Следствие. Движение переводит многоугольник в равный ему многоугольник, а ломаную - в равную ей ломаную.
Действительно, многоугольник (ломаная) однозначно определяется длинами своих сторон (звеньев) и углами между ними. Движение сохраняет и то, и другое (см. опр-ние и пред. следствие).