Любая из понравившихся вам тем в прикрепленном файле

Теорема. Если связный граф G допускает плоскую реализацию, то границы областей, на которые граф G разбивает плоскость, образуют базу независимых циклов.Доказательство.

Как будет доказано ниже, для плоского графа выполняется равенствоSo— Sx + S2 = 2, откуда v (G) = Sx — So + P =S2— 2+ 1 =S, — 1, и достаточно доказать лишь независимость циклов базы. Доказательство проведем индукцией по S2. Базис индукции. Если S2 = 2, то утверждение очевидно, так как база содержит всего один цикл. Индукционный шаг.Пусть теорема справедлива для всех графов СсS2 = п. Пусть G — связный граф с S2 = п + 1. Возьмем одно из ребер, лежащих на границе неограниченной области и не являющееся тупиком или перешейком. После удаления его получаем граф G' с S2 = п. Применяя предположение индукции и замечая, что цикл, содержащий выброшенное ребро, не зависит от остальных, завершаем индукционный шаг. Решение задач.

Задача 9bДокажите, что каждое дерево является двудольным графом; какие деревья являются полными двудольными графами? Решение задачи.

Используем следствие из теоремы.

Кенинга:

Теорема Кёнига 2 (о необходимых и достаточных условиях разбиения множества вершин графа на два независимых подмножества). Для того, чтобы граф был двудольным, необходимо и достаточно, чтобы он не содержал циклов нечетной длин.Доказательство. Необходимость. Пусть Γ — двудольный граф, C — один из его циклов длины k. Пройдем все ребра этого цикла в той последовательности, в какой они в нем расположены, начиная с некоторой вершины v. Так как концы каждого ребра лежат в разных долях, то k — четное число. Достаточность. Не теряя общности, можно рассматривать только связные графы. Пусть связный граф Γ не имеет циклов нечетной длины.

Рассмотрим произвольную вершину v0 и построим разбиение вершин графа Γ на два класса V1 и V2 следующим образом: к классу V1 отнесем вершину v0 и любую такую вершину u, что расстояние между u и v0 четное, к классу V2 отнесем любую такую вершину u, что расстояние между u и v0 нечетное. Остается показать, что любые две вершины из множества V1 или любые две вершины из множества V2 не смежны. Пусть, например, существуют две смежные вершины u и v, входящие в один класс. Тогда ни одна из них не совпадает с вершиной v0, так как вторая в этом случае принадлежала бы другому классу (расстояние между смежными вершинами равно 1). Пусть далее Z1 — кратчайшая цепь, соединяющая v0 и u, а Z2 — кратчайшая цепь соединяющая v0 и v. Обозначим через v1, v2,…, vp общие вершины, считая от вершины v0.

Поскольку Z1 и Z2 — кратчайшие цепи, то их части от вершины от вершины v0 до вершины v1 имеют одинаковые длины. То же самое можно сказать и о частях цепей Z1 и Z2 от любой вершины vi до вершины vi+1. Поэтому части цепей от вершины vp до вершин u и v имеют одинаковые четности. Но тогда объединение этих частей и ребра {u, v} является циклом нечетной длины, что запрещено условиями теоремы. Теорема доказана. Следствие из теоремы Кёнига. Любое дерево является связным двудольным графом. Действительно, дерево является связным ацикличным графом и, следовательно, не содержит циклов нечетной длины.

Деревья с цепями с длиной равными 2 являются полными двудольными графами. Задача 9сДокажите, что графы, соответствующиенасыщенным углеводородам (СпН2n+2) и спиртам (CnH2n+1OH), являются деревьями. Решение задачи.

Графом молекулы называется граф, вершинами которого являются атомы, а ребрами — соответствующие валентные связи между атомами. Докажем, что графом G молекулы насыщенного углеводорода является дерево. Предположим, что в графе G есть цикл C. Поскольку валентности атомов водорода равны 1, то цикл C может состоять только из атомов углерода. Разорвав некоторую связь между атомами углерода в цикле и соединив эти атомы с атомами водорода, мы получим соединение, в котором атомов водорода будет больше, чем в первоначальном соединении (рис.

1). Это противоречит тому, что граф G был графом насыщенного углеводорода. Пусть молекула насыщенного углеводорода содержит n атомов углерода и m атомов водорода. Граф молекулы является деревом, поэтому согласно лемме он имеет n + m вершин и n + m — 1 ребер. Воспользуемся леммой о рукопожатиях:

4 n + 1 m = 2 (n + m — 1).Отсюда получаем m = 2 n + 2. Это значит, что формула насыщенного углеводорода, имеющего n атомов углерода, имеет вид CnH2n + 2. При замещении атома водорода ОН, получаем такой же результат для спиртов.

Список использованных источников

1. Уилсон Р.

Введение

в теорию графов — М. Мир, I9772.

Белов В. В. Воробьев Е. М. Шаталов В. Е. Теория графов — М ВШ. 1976.

3. Березина Л. Ю. Графы и их применения. Пособие для учителей. — М. 1979.