Графы и их применение

      

     Граф  G₁´ G₂ изображен на рис. 5.

     Операция  декартова произведения обладает следующими свойствами.

     1. G₁´G₂ = G₂´G₁

     2. G₁´(G₂´G₃) = (G₁´G₂)´G₃.

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

     Пусть G₁(X,E₁) и G₂(Y,E₂) – два графа, имеющие  n_x и n_y  вершин соответственно. Результирующий граф G₁´G₂ имеет n_x×n_y вершин, а его матрица смежности вершин - квадратная матрица размером (n_x×n_y)´ (n_x ×n_y). Обозначим через a_ab = a_(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z_a=(x_iy_j) c z_b=(x_ky_l). Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

     a_ab = a_(ij)(kl) = K_ik×a_2,jl Ú K_jl×a_1,ik,     

     где a_1,ik, a_2,jl – элементы матрицы смежности вершин графов G₁ и G₂ соответственно;

     K_ik – символ Кронекера, равный 1, если i=k, и нулю, если i¹k . 

     Произведение графов.  Пусть G₁(X,E₁) и G₂(Y,E₂) - два графа. Произведением G₁×G₂ графов G₁ и G₂ называется граф с множеством вершин X´Y, а дуга из вершины (x_i,y_j) в вершину (x_k,y_l) существует тогда и только тогда, когда существуют дуги (x_i,x_k) Î E₁ и (y_j,y_l) Î E₂.

     Выполнение  операции произведения рассмотрим на примере графов, изображенных на рис. 6. Множество вершин Z результирующего графа определяется как декартово произведение множеств X´Y. Множество Z содержит следующие элементы: z₁=(x₁y₁), z₂₌(x₁y₂), z₃=(x₁y₃), z₄=(x₂y₁), z₅=(x₂y₂), z₆=(x₂y₃).

     Определим множество дуг результирующего  графа. Для удобства рассмотрения составим таблицу, в первом столбце которой указываются дуги графа G₁, во втором – дуги графа G₂, а в третьем и четвертом – дуги результирующего графа. 

     Результирующий  граф G_1×G₂ изображен на рис. 6.

     

     Операция  произведения обладает следующими свойствами.

     1. G₁×G₂ = G₂×G₁.

     2. G₁×(G₂×G₃) = (G₁×G₂)×G₃.

     Рассмотрим  выполнение операции произведения графов в матричной форме.

     Пусть G₁(X,E₁) и G₂(Y,E₂) – два графа, имеющие n_x и n_y  вершин соответственно. Результирующий граф G₁×G₂ имеет n_x×n_y вершин, а его матрица смежности вершин - квадратная матрица размером (n_x×n_y)´ (n_x ×n_y). Обозначим через a_ab = a_(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z_a=(x_iy_j) c z_b=(x_ky_l). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

     a_ab =a_(ij)(kl) = a_1,ik Ù a_2,jl,     

     де  a_1,ik, a_1,ik – элементы матрицы смежности вершин графов G₁ и G₂ соответственно. 
 
 
 
 
 

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

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

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

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

    Теорема 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. Во всяком графе с n вершинами, где n больше или равно 2, всегда найдутся две или более вершины с  оди­наковыми степенями.

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

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

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

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

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

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

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

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

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

    Пусть все пять вершин графа соединены друг с другом. Замечаем, что на графе нет ни одной грани, ограниченной только двумя ребрами. Если через φ1 обозначить число таких граней, то φ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; поэтому вывод, полученный при введенном нами предположении (граф плоский), противоречит условию. Отсюда заключаем, что полный граф с пятью вершинами не является плоским.

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