В моем сегодняшнем сообщении речь пойдет о недавно обнаруженном мной замечательном свойстве многоугольников.
Теорема 3. Граф пересечения двух многоугольников,образованный вершинами многоугольников, их точками пересечения и отрезками, которые их соединяют, является эйлеровым, если количество точек их пересечения не более, чем конечно.
Доказательство.
Если два многоугольник пересекаются, значит пересекаются какие-то их ребра.
Здесь возможны несколько случаев.
1) Пересечение двух отрезков образует отрезок. Как известно, на отрезке точек вовсе не конечное число, поэтому, согласно формулировке теоремы, такие многоугольники мы рассматривать не будем. Как видно из рисунка слева, они не всегда являются эйлеровыми графами.
2) Пересечение двух отрезков не образует отрезок. Тогда два отрезка могут пересекаться в какой-то точке. Если точка пересечения не является вершиной никакого из многоугольников, тогда все очевидно, в образованном графе она имеет степень 4. Если же она является вершиной только одного многоугольника, то и здесь, очевидно, полученная точка будет иметь степень 4 (т.к. в графе любого многоугольника степени всех вершин равны 2). Иначе, если она является вершиной обоих многоугольников, то степени просто суммируются, то есть степень полученной вершины равна 4.
Таким образом, во всех нужных нам случаях степени всех вершин остаются четными, следовательно, по критерию существования в графе эйлерового цикла, этот граф является эйлеровым. Теорема доказана.
Обобщим нашу теорему на большое количество многоугольников.
Теорема 4. Граф пересечения любого количества многоугольников,образованный вершинами многоугольников, их точками пересечения и отрезками, которые их соединяют, является эйлеровым, если для графа пересечения любых двух многоугольников из рассматриваемого набора можно утверждать, что они имеют не более, чем конечное число точек пересечения.
Доказательство.
Доказывать будем по индукции.
База. См. Теорема 3.
Предположение. Предположим для количества многоугольников K теорема верна.
Переход. Докажем, что для количества многоугольников K+1 теорема также верна.
Действительно, если граф при K многоугольниках эйлеровый, значит, степени его вершин четные числа. Понятно (см. опять же теорему 3), что при пересечении полученной конструкции с еще одним многоугольником подходящим нам образом, могут либо появляться новые вершины со степенью 4, либо степени старых вершин будут увеличиваться на 2. Таким образом, четность не изменится. Откуда следует, что граф будет эйлеровым и при K+1.
Теорема доказана.
Теорема 3. Граф пересечения двух многоугольников,образованный вершинами многоугольников, их точками пересечения и отрезками, которые их соединяют, является эйлеровым, если количество точек их пересечения не более, чем конечно.
Доказательство.
Если два многоугольник пересекаются, значит пересекаются какие-то их ребра.
Здесь возможны несколько случаев.
 |
| Пример для пункта 1. |
1) Пересечение двух отрезков образует отрезок. Как известно, на отрезке точек вовсе не конечное число, поэтому, согласно формулировке теоремы, такие многоугольники мы рассматривать не будем. Как видно из рисунка слева, они не всегда являются эйлеровыми графами.
2) Пересечение двух отрезков не образует отрезок. Тогда два отрезка могут пересекаться в какой-то точке. Если точка пересечения не является вершиной никакого из многоугольников, тогда все очевидно, в образованном графе она имеет степень 4. Если же она является вершиной только одного многоугольника, то и здесь, очевидно, полученная точка будет иметь степень 4 (т.к. в графе любого многоугольника степени всех вершин равны 2). Иначе, если она является вершиной обоих многоугольников, то степени просто суммируются, то есть степень полученной вершины равна 4.
Таким образом, во всех нужных нам случаях степени всех вершин остаются четными, следовательно, по критерию существования в графе эйлерового цикла, этот граф является эйлеровым. Теорема доказана.
Обобщим нашу теорему на большое количество многоугольников.
Теорема 4. Граф пересечения любого количества многоугольников,образованный вершинами многоугольников, их точками пересечения и отрезками, которые их соединяют, является эйлеровым, если для графа пересечения любых двух многоугольников из рассматриваемого набора можно утверждать, что они имеют не более, чем конечное число точек пересечения.
Доказательство.
Доказывать будем по индукции.
База. См. Теорема 3.
Предположение. Предположим для количества многоугольников K теорема верна.
Переход. Докажем, что для количества многоугольников K+1 теорема также верна.
Действительно, если граф при K многоугольниках эйлеровый, значит, степени его вершин четные числа. Понятно (см. опять же теорему 3), что при пересечении полученной конструкции с еще одним многоугольником подходящим нам образом, могут либо появляться новые вершины со степенью 4, либо степени старых вершин будут увеличиваться на 2. Таким образом, четность не изменится. Откуда следует, что граф будет эйлеровым и при K+1.
Теорема доказана.
Комментариев нет:
Отправить комментарий