Продолжение факультатива на тему "Теория графов"

         В теории графов существуют несколько видов математических задач на исследование свойств  плоских графов.

        Плоским графом называется множество точек плоскости - вершин,

соединенных между собой линиями - ребрами, лежащими в этой же плоскости, причем никакие два ребра не пересекаются.

        Условимся представлять себе ребра в виде эластичных нитей, которые могут удлиняться, укорачиваться и как угодно изгибаться, оставаясь в плоскости. Это позволяет любой граф изображать по-разному.

       Например, на рисунке изображён один и тот же граф, имеющий четыре

вершины и шесть рёбер, изображён тремя способами. 

                      ЗАДАЧА О ГРАФОПОСТРОИТЕЛЕ

Эйлер сформулировал задачу о графопостроителе следующим образом:

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

           Л. Эйлер показал:

 1. Если все вершины плоского или пространственного графа чётным, то задача разрешима (нечётной (чётной) вершиной графа называется вершина, из которой выходит нечётное (чётное) число рёбер).

 2. Если две вершины нечётны, то, выйдя из одной нечётной вершины, можно вернуться в другую, не проходя ни по одному из рёбер дважды.

 3. Если нечётных вершин 2k, то существует k путей, начинающихся и заканчивающихся в нечётных вершинах.

       На рисунке показан граф, который можно обвести, не отрывая карандаша от бумаги. У данного графа шесть вершин и каждая из них четная. Откуда же начинать вычерчивание?