Доклад: Теория Графов в химии и нерешённые задачи

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

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

Задача : Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу. Дорожки не могут проходить через колодцы и домики (рис.1).

Рис. 1. К задаче о домиках и колодцах.

Для решения этой задачи воспользуемся теоремой, доказанной Эйлером в 1752 году, которая является одной из основных в теории графов. Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

Теорема. Если многоугольник разбит на конечное число многоугольников так, что любые два многоугольника разбиения или не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство

В - Р + Г = 1, (*)

где В - общее число вершин, Р - общее число ребер, Г - число многоугольников (граней).

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

а) б)

Рис.2

Действительно, после проведения такой диагонали в новом разбиении будет В вершин, Р+1 ребер и количество многоугольников увеличится на единицу. Следовательно, имеем

В - (Р + 1) + (Г+1) = В – Р + Г.

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

Для этого будем последовательно убирать внешние ребра, уменьшая количество треугольников. При этом возможны два случая:

для удаления треугольника ABC требуется снять два ребра, в нашем случае AB и BC;

для удаления треугольника MKN требуется снять одно ребро, в нашем случае MN.

В обоих случаях равенство не изменится. Например, в первом случае после удаления треугольника граф будет состоять из В-1 вершин, Р-2 ребер и Г-1 многоугольника:

(В - 1) - (Р + 2) + (Г -1) = В – Р + Г.

Таким образом, удаление одного треугольника не меняет равенства .

Продолжая этот процесс удаления треугольников, в конце концов, мы придем к разбиению, состоящему из одного треугольника. Для такого разбиения В = 3, Р = 3, Г = 1 и, следовательно,

B - Р + Г= 1.

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

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

Приступим теперь к решению задачи о трех домиках и трех колодцах.

Решение. Предположим, что это можно сделать. Отметим домики точками Д1, Д2, Д3, а колодцы - точками К1, К2, К3 (рис. 1). Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются.

Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера В - Р + Г= 1.

Добавим к рассматриваемым граням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид В - Р + Г = 2, причем В = 6 и Р = 9.