Матрицы в теории графов

    Решение задачи 9:

    а) n = 4,

     

    

    А² = А³ = А⁴ = 
 
 
 

      

    А² + А² + А⁴ = 
 

    На диагонали присутствуют нулевые элементы, следовательно, граф имеет контур. 

     б)  

    А² = А³ = А⁴ =   
 
 

    

    К =  
 

     

    На  диагонали присутствуют ненулевые  элементы, следовательно, граф имеет  контур. 

    Задача 10: По заданной матрице весов Ω графа G найти величину минимального пути и сам путь от вершины s = x₁ до вершины t = x₆ по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами: 

    

 
 
 
 
 
 
 
 

    Решение задачи 10:

    Построим  граф по данной матрице (Рис. 2. 9).

     Рис. 2. 9

    В данном графе нет цикла, поэтому  упорядочим его с помощью алгоритма  Фалкерсона.

    Вершина х₁ не содержит входящий дуг, отнесем ее к первой группе. Вычеркнем все дуги, исходящие из х₁, получим граф без трёх рёбер (х₁ – х₂, х₁ – х₄, х₁ – х₅). В нём опять находим одну вершину, в которую не заходит ни одна дуга. Это вершина х₄ (вторая группа). Вычеркнем дуги, исходящие из вершины х₄. получим граф только с четырьмя рёбрами (х₂ – х₃, х₃ – х₆, х₅ – х₃, х₅ – х₂). Появилась ещё одна вершина х₅ (группа 3), в которую не входят рёбра, вычеркнем исходящие из неё дуги. Получим вершину х₂, которая входит в группу 4, х₃ – в группу 5 и х₆ – в группу 6.

    Получен упорядоченный граф (Рис. 2. 10):

     Рис. 2. 10 

    Этап 1.

    Шаг 1. Полагаем, что d(x₁) = 0*, x” = x₁.

    d(x₂) = d(x₃) = d(x₄) = d(x₅) = d(x₆) = ∞.

    1-ая  итерация

    Шаг 2. Множество вершин, непосредственно следующих за х = х₁ с временными  метками S” = {x₂, x₄, x₅}. Пересчитываем временные метки этих  вершин: d(x₂) = min{∞, 0*+11} = 11, d(x₄) = min{∞, 0*+14} = 14, d(x₅) = min{∞, 0*+15} = 15.

    Шаг 3. Одна из временных  меток превращается в постоянную. min{11, ∞, 14, 15, ∞} = 11* = d(x₂), x” = x2.

    Шаг 4. x” = x₂ ≠ x₆, происходит возвращение на второй шаг.

    2-ая  итерация

    Шаг 2. S” = {x₃}, d(x₃) = min{11, 11*+13} = 11.

    Шаг 3. min{11} = 11* = d(x₃), x” = x3.

    Шаг 4. x₃ ≠ x₆, происходит возвращение на шаг 2.

    3-я  иетерация

    Шаг 2. S” = {x₆}, d(x₆) = min{29, 11*+11+14} = 29.

    х₆=x₆, конец первого этапа.

    Этап 2.

    Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x₆ с постоянными метками. S”={x₃, x₅}. Проверим для этих двух вершин выполнение равенства

    d(x”) = d(x_i) + ω(x_i, x”).

    d(x”) = 29 = 15*+14 = d(x₅) + ω(x₅, x₆),

    d(x”) = 29 ≠ 23*+14 = d(x₃) + ω(x₃, x₆).

    Включаем  дугу (x₅, x₆) в кратчайший путь; x” = x₅.

    Шаг 6. x” ≠ x₁, переходим на шаг 5.

    2-ая  итерация

    Шаг 5. S” = {x₁, x₄},

    d(x”) = 15 = 0*+15 = d(x₁) + ω(x₁, x₅),

    d(x”) = 15 ≠ 14+9 = d(x₄) + ω(x₄, x₅).

    Включаем  дугу (x₁, x₅) в кратчайший путь. x” = x₁.

    Шаг 6. x” = x₁. Завершение второго этапа.

    Итак, кратчайший путь из вершины х₁ в х₆ построен. Его длина (вес) равна 29. Сам путь образует следующая последовательность дуг: μ_min = (х₁, х₅)-(х₅, х₆). 

Задача 11: Найти величину максимального пути и сам путь между вершинами s = x₁ и t = x₆ (матрица из задачи 10)

    Решение задачи 11:

    Этап 1

    d₁ = 0,

    d₄ = max{d₁+14} = 14

    d₅ = max{d₄+9, d₁+15} = max{15, 23} = 23

    d₂ = max{d₁+11, d₄+7, d₅+11} = max{11, 21, 34} = 34

    d₃ = max{d₂+13, d₄+11, d₅+10} = max{47, 25, 33} = 47

    d₆ = max{d₃+13, d₅+14} = max{60, 37} = 60.

    Итак, длина максимального пути из х₁ в х₆ равна 60.

    Этап 2

    *x₆ : d₆ = 60 = x₃+13 – включаем дугу (х₃, х₆) в максимальный путь, d₆ = 60 ≠ d₅+14=37.

    *x₃ : d₃ = 47 = d₂+13 = 34+13 – включаем дугу (x₂, x₃) в максимальный путь,

    d₃ = 47 ≠ d₄+11 = 25,

    d₃ = 47 ≠ d₅+10=33.

    *x₂ : d₂ = 34 = d₅+11 – включаем дугу (х₅, х₂) в максимальный путь,

    d₂ = 34 ≠ d₁+11,

    d₂ = 34 ≠ d₄+7.

    *x₅ : d₅ = 23 = d₁+15 – включаем дугу (x₁, x₅) в максимальный путь,

    d₅ = 23 ≠ d₄+9.

    *x₄ : d₄ = 14 = d₁+14 = 0+14 – включаем дугу (х₁, х₄) в максимальный путь.

    итак, искомый путь таков:μ_max = (x₁, x₄)-(x₄, x₅)-(x₅, x₂)-(x₂, x₃)-(x₃, x₆)  

    Задача 12: По заданной матрице весов Ω графа G найти величину минимального пути и сам путь от вершины s = x₁ до вершины t = x₆ по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами:

   

    Решение задачи `12:

    Нарисуем  граф (Рис. 2.11) по данной матрице, упорядочим его вершины по алгоритму Фалкерсона. Получим граф, изображённый на рисунке 2. 12. 

     Рис. 2.11 
 
 

      
 
 
 
 
 
 
 

    Рис. 2.12 

    Для нахождения минимального пути используем алгоритм Дейкстры.

    Этап 1

    Шаг 1. Полагаем, что d(x₁) = 0*, x” = x₁.

    d(x₂) = d(x₃) = d(x₄) = d(x₅) = d(x₆) = ∞.

    1-ая  итерация

    Шаг 2. Множество вершин, непосредственно следующих за х = х₁ с временными  метками S” = {x₂, х₃}. Пересчитываем временные метки этих  вершин: d(x₂) = min{∞, 0*+8} = 8, d(x₃) = min{∞, 0*+10} = 10.

    Шаг 3. Одна из временных меток превращается в постоянную. min{8, ∞, 10} = 8* = d(x₂), x” = x₂.

    Шаг 4. x” = x₂ ≠ x₆, происходит возвращение на второй шаг.

    2-ая  итерация

    Шаг 2. S” = {x₃, х₄, х₅}, d(x₃) = min{10, 8*+10} = 10,

    d(x₄) = min{∞, 8*+9} = 17, d(x₅) = min{∞, 8*+12} = 20.

    Шаг 3. min{10, 17, 20} = 10* = d(x₃), x” = x₃.

    Шаг 4. x₃ ≠ x₆, происходит возвращение на шаг 2.

    3-я  итерация

    Шаг 2. S” = {x₄, х₅, x₆}, d(x₄) = min{17, 10*+10} = 17, d(x₅) = min{20, 10*+12} = 20, d(x₆) = min{∞, 10*+7} = 17.

    х₆ = х₆, конец первого этапа

    Этап 2

    Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x₆ с постоянными метками. S”={x₃, x₄, х₅}. Проверим для этих двух вершин выполнение равенства  d(x”) = d(x_i) + ω(x_i, x”). В итоге включаем дугу (x₁, x₃) в кратчайший путь, затем таким же образом дугу (х₃, х₆).

    Итак, кратчайший путь из вершины х₁ d х₆ построен. Его длина (вес) равна 17. Сам путь образует следующая последовательность дуг: μ=(х₁, х₃)-(х₃, х₆). 

Задача  13: Используя матрицу из задачи 8, построить максимальный путь из вершины х₁ в вершину х₆.

Решение задачи 13:

    Этап 1

    d₁ = 0,

    d₂ = max{d₁+8} = 8

    d₃ = max{d₁+10, d₂+10} = max{10, 18}=18

    d₄ = max{d₂+9, d₃+10} = max{17, 28} = 28

    d₅ = max{d₃+12, d₄+9, d₂+12} = max{30, 37, 20} = 37

    d₆ = max{d₃+7, d₄+13, d₅+11} = max{25, 41, 48} = 48.

    Итак, длина максимального пути из х₁ в х₆ равна 48.

    Этап 2

    *x₆ : d₆ = 48 = d₅ + 11 – включаем дугу (х₅, х₆) в максимальный путь.

    *x₅ : d₅ = 37 = d₄+9 – включаем дугу (x₄, x₅) в максимальный путь,

    *x₄ : d₄ = 28 = d₃+10 – включаем дугу (х₃, х₄) в максимальный путь,

    *x₃ : d₃ = 18 = d₂+10 – включаем дугу (x₂, x₃) в максимальный путь,

    *x₂ : d₂ = 8 = d₁+8 – включаем дугу (х₁, х₂) в максимальный путь.

    Итак, искомый путь таков:μ_max = (x₁, x₂)-(x₂, x₃)-(x₃, x₄)-(x₄, x₅)-(x₅, x₆).

    ЗАКЛЮЧЕНИЕ 

    В данной курсовой работе я рассмотрела  основные виды матриц из теории графов: латинская матрица, матрица смежности, инцидентности, достижимости и контрдостижимости, связности. С помощью матриц смежности и инциденций научилась определять, являются ли графы изоморфными. Рассмотрены теоремы по данному пункту.

    Так же рассмотрены некоторые метрические  характеристики графа, такие как  ранг, расстояние, радиус и другие.

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

    В практической части курсовой работы представлен ряд упражнений по данной теме.

    Цель  и задачи, которые ставились вначале  данной работы, выполнены. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    СПИСОК  ЛИТЕРАТУРЫ 

     

1. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер. с англ. – М.: Издательский дом «Вильямс», 2003.
2. Баврин И. И. Дискретная математика. – М.: Высш. шк., 2007.
3. Нефёдов В. Н., Осипова В. А. Курс дискретной математики. – М.:Изд-во МАИ, 1992.
4. Новиков С.А. Дискретная математика для программистов – СПб.: Питер, 2001.
5. Оре О. Графы и их применение. – М.: Мир,1973.
6. Редькин Н. П. Дискретная математика. – СПб.: Издательство «Лань», 2003.
7. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
8. Шапорев. С. Д. Дискретная математика. Курс лекций и практических занятий. – СПБ.: БХВ-Петербург, 2007.
9. Харари Ф. Теория графов. – М.: Мир, 1973.