Теория графов

      Определение 2.12. Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза. 

      Определение 2.13. Длиной пути, проложенного на цикле, называется число ребер этого пути.

      Пример: на графе G (рис. 2.9) проложен простой цикл (A, B); (B, F); (F, C); (C, D); (D, E); (E, A) длина пути этого цикла равна 6. 

      Определение 2.14. Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B. 

      Определение 2.15.  Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным. 

      (РИСУНОК 2.10 и 2.11) 

      На  рисунке 2.10 изображен связный граф; на рисунке 2.11 – несвязный (т. к.  существует минимум одна пара несвязных  вершин – A и D).

      Определение 2.16. Деревом называется  связный граф, не содержащий циклов.

      Трехмерной  моделью графа-дерева служит, например, настоящее дерево с его замысловато разветвленной кроной; река и ее притоки также образуют дерево, но уже плоское – на поверхности земли (рис.2.12). 

      (РИСУНОК  2.12) 

      Определение 2.17. Несвязный граф, состоящий исключительно из деревьев, называется лесом.

     Пример: на рисунке 2.13 изображен лес, состоящий  из трех деревьев.  

      (РИСУНОК  2.13) 

     Определение 2.13.  Дерево, все n  вершин которого имеют номера от 1 до n, называют деревом с перенумерованными вершинами. 

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

§3.  ОСНОВНЫЕ ТЕОРЕМЫ  ТЕОРИИ ГРАФОВ. 

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

Теорема 3.1. Удвоенная  сумма степеней вершин любого графа равна   числу его ребер.  

     Доказательство. Пусть А₁, А₂, А₃, ..., A_n — вершины данного графа, a p(A₁), р(А₂), ..., p(A_n) – степени этих вершин. Подсчитаем число ребер, сходящихся в каждой вершине, и просуммируем эти числа. Это равносильно нахождению суммы степеней всех вершин. При таком подсчете каждое ребро будет учтено дважды (оно ведь всегда соединяет две вершины).

    Отсюда  следует: p(A₁)+р(А₂)+ ... +p(A_n)=0,5N, или 2(p(A₁)+р(А₂)+ ... +p(A_n))=N , где N — число ребер. ‡ 

    Теорема 3.2. Число нечетных вершин любого графа четно.

    Доказательство. Пусть a₁, a₂, a₃, …, a_k — это степени четных вершин графа, а b₁, b₂, b₃, …, b_m — степени нечетных вершин графа. Сумма a₁+a₂+a₃+…+a_k+b₁+b₂+b₃+…+b_m ровно в два раза превышает число ребер графа. Сумма a₁+a₂+a₃+…+a_k четная (как сумма четных чисел), тогда сумма b₁+b₂+b₃+…+b_m должна быть четной. Это возможно лишь в том случае, если m — четное, то есть четным является и число нечетных вершин графа. Что и требовалось доказать. ‡ 

Эта теорема  имеет немало любопытных следствий. 

Следствие 1. Нечетное число знакомых в любой компании всегда четно.

Следствие 2. Число вершин многогранника, в которых сходится нечетное число  ребер,  четно. 

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

Теорема 3.3. Во всяком графе с n вершинами, где n больше или равно 2, всегда найдутся две или более вершины с одинаковыми степенями.

    Доказательство. Если граф имеет n вершин, то каждая из них может иметь степень 0, 1, 2, ..., (n-1). Предположим, что в некотором графе все его вершины имеют различную степень, то есть, и покажем, что этого быть не может. Действительно, если р(А)=0, то это значит, что А — изолированная вершина, и поэтому в графе не найдется вершины Х со степенью р(Х)=n-1. В самом деле, эта вершина должна быть соединена с (n-1) вершиной, в том числе и с А, но ведь А оказалась изолированной. Следовательно, в графе, имеющем n вершин, не могут быть одновременно вершины степени 0 и (n-1). Это значит, что из n вершин найдутся две, имеющие одинаковые степени. ‡ 

Теорема 3.4. Если в графе с n вершинами (n больше или равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.

     Доказательство  данной теоремы мы опускаем. Остановимся  лишь на некотором ее пояснении. Содержание этой теоремы хорошо разъясняется задачей: группа, состоящая из n школьников, обменивается фотографиями. В некоторый момент времени выясняется, что двое совершили одинаковое число обменов. Доказать, что среди школьников есть либо один еще не начинавший обмена, либо один уже завершивший его. 

      Теорема 3.5. Если у графа все простые циклы четной длины, то он не содержит ни одного цикла четной длины.

      Рисунок 3.1 поясняет условие теоремы. На изображенном графе все 5 простых циклов четные.   

(РИСУНОК  3.1) 

      Суть  теоремы в том, что на этом графе  невозможно найти цикл (как простой, так и непростой) нечетной длины, то есть содержащий нечетное число ребер.   

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

Теорема 3.7. Для того чтобы на связном графе можно было бы проложить цепь АВ, содержащую все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечетными вершинами этого графа.

     Доказательство  этой теоремы очень интересно и характерно для теории графов. Его также следует считать конструктивным (обратите внимание на то, как •использована при этом теорема 3.6). Для доказательства к исходному графу присоединяем ребро (А, В); после этого все вершины графа станут четными. Этот новый граф удовлетворяет всем условиям теоремы 3.6, и поэтому в нем можно проложить эйлеров цикл Ψ. И если теперь в этом цикле удалить ребро (А, В), то останется искомая цепь АВ. ‡ 

     На  этом любопытном приеме основано доказательство следующей теоремы, которую следует считать обобщением теоремы 3.7. 

Теорема 3.8. Если данный граф является связным и имеет 2k вершин нечетной степени, то в нем можно провести k различных цепей, содержащих все его ребра в совокупности ровно по одному разу. 

Теорема 3.9. Различных деревьев с n перенумерованными вершинами можно построить n^n-2.

     По  поводу доказательства этой теоремы  сделаем одно замечание. Эта теорема  известна, в основном, как вывод  английского математика А. Кэли (1821—1895). Графы-деревья издавна привлекали внимание ученых. Сегодня двоичные деревья используются не только математиками, а и биологами, химиками, физиками и инженерами (подробнее об этом – в параграфе 6). 

     Теорема 3.10. Полный граф с пятью вершинами не является плоским.

     Доказательство. Воспользуемся формулой Эйлера: В-Р+Г=2, где В — число вершин плоского графа, Р — число его ребер, Г — число граней. Формула Эйлера справедлива для плоских связных графов, в которых ни один из многоугольников не лежит внутри другого. На рисунке 3.2, а изображен граф, к которому формула не применима — заштрихованный многоугольник находится внутри другого. Справа приведено изображение графа, к которому формула применима.  

(РИСУНОК  3.2)

     Эту формулу можно доказать методом  математической индукции. Это доказательство мы опускаем. Заметим только, что формула справедлива и для пространственных многогранников. Пусть все пять вершин графа соединены друг с другом (рис. 3.2). Замечаем, что на графе нет ни одной грани, ограниченной только двумя ребрами. Если через φ₁ обозначить число таких граней, то φ₂=0. Далее рассуждаем от противного, а именно: предположим, что исследуемый граф плоский. Это значит, что для него верна формула Эйлера. Число вершин в данном графе В=5, число ребер Р=10, тогда число граней Г=2-В+Р=2-5+10=7.

     Это число можно представить в  виде суммы: Г=φ₁+φ₂+φ₃+…,  где φ₃ –  число граней, ограниченных тремя ребрами, φ₄ — число граней, ограниченных четырьмя ребрами и т. д.

     С другой стороны, каждое ребро является границей двух граней, а поэтому число граней равно 2Р, в то же время 2Р=20=3φ₃+4φ₄+... . Умножив равенство Г=7=φ₃+ φ₄ + φ₅ + … на три, получим ЗГ=21=3( φ₃ + φ₄ + φ₅ + …).

     Ясно, что (3φ₃+3φ₄+3φ₅+…) < (3φ₃+4φ₄+ 5φ₅+…) или 3Г<2Р, но по условию, 2Р=20, а ЗГ=21; поэтому вывод, полученный при введенном нами предположении (граф плоский), противоречит условию. Отсюда заключаем, что полный граф с пятью вершинами не является плоским. ‡ 

Теорема 3.11. (Теорема Понтрягина-Куратовского) Граф является плоским тогда и только тогда, когда он не имеет в качестве подграфа полного графа с пятью вершинами. 

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

§4.  ЗАДАЧИ НА  ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ. 

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

Задача 4.1. Необходимо составить фрагмент расписания для одного дня с учетом следующих обстоятельств:

1. учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок;
2. учитель литературы может дать один, либо второй, либо третий урок;
3. математик готов дать либо только первый, либо только второй урок;
4. преподаватель физкультуры согласен дать только последний урок.

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

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

     (РИСУНОК  4.1) 

     Данная  задача является классическим примером удачного использования теории графов. В настоящее время  существует программа "Расписание 3.0" компьютерной фирмы ЛинTex, в которой она решена с использованием современных технологий.