Решение задач с применением теории графов

Решение задач с применением теории графов

Содержание

Введение

Задание №1

Задание №2

Задание №3

Задание №4

Задание №5

Заключение

Список используемых источников

Введение

граф дискретная математика

Теория графов - раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E - подмножество V×V.

В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы проектирования интегральных схем и схем управления, исследования логических цепей, блок-схем программ, экономики и статистики, химии и биологии, теории расписаний и дискретной математики.

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

1 Задание №1

Формулировка задания

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

Матрица смежности представлена на рисунке 1.1.

Рисунок 1.1 - Матрица смежности исходного графа

Решение

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

Рисунок 1.2 - Графическое изображение исходного графа

Степени оператора прямого транзитивного замыкания для первой вершины:

G⁰(1) = {1};

G¹(1) = {1, 2, 8, 18};

G²(1) = {1, 2, 8, 18, 6, 12, 4, 16, 5, 14};

G³(1) = {1, 2, 8, 18, 6, 12, 4, 16, 5, 14, 3, 15, 10, 13, 17};

G⁴(1) = {1, 2, 8, 18, 6, 12, 4, 16, 5, 14, 3, 15, 10, 13, 17, 11, 7}.

Остальные степени оператора G находить не нужно, так как это не приводит к появлению во множестве G^k(1) новых вершин. Следовательно, прямое транзитивное замыкание

G⁺(1) =  = {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18}.

Степени оператора обратного транзитивного замыкания для первой вершины:

G^-1(1) = {1, 11, 12};

G^-2(1) = {1, 11, 12, 3, 13, 2, 4, 7, 14, 15};

G^-3(1) = {1, 11, 12, 3, 13, 2, 4, 7, 14, 15, 6, 17, 8, 5, 9, 16, 18, 10}.

Остальные степени оператора не находим по той же причине. Следовательно, обратное транзитивное замыкание

G^-(1) =={1,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}.

Таким образом, компонента связности для вершины 1

C₁ = G⁺(1)∩G^-(1) = {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18}.

После этих вычислений остается вершина 9, не вошедшая в компоненту. Не вычисляя G⁺(9) и G^-(9), можно заключить, что C₂ = {9}.

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

Рисунок 1.3 - Преобразования матрицы смежности

По приписанным столбцу и строке записываем прямое и обратное транзитивные замыкания вершины 1:

G⁺(1) = {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18};

G^-(1) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}.

Следовательно, компонента связности вершины 1

C₁= G⁺(1)∩G^-(1) = {1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18}.

Компонента связности вершины 9

C₉ = {9}.

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

Рисунок 1.4 - Граф, разложенный на сильно связанные подграфы

Задание №2

Формулировка задания.

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

Матрицы смежности и весов представлены на рисунках 2.1 и 2.2.

Рисунок 2.1 - Матрица смежности заданного графа

Рисунок 2.2 - Матрица весов заданного графа

Решение

Чтобы найти классы порядка, воспользуемся алгоритмом Демукрона. Снизу от матрицы смежности приписываем массив M, элементы которого получаются суммированием элементов в столбцах и являются полустепенями захода для вершин. Первые четыре элемента массива равны нулю, поэтому вершины 1, 2, 3 и 4 относим к первому уровню, а вместо нулей в массиве пишем *. Далее в матрице смежности складываем первые четыре строки и их сумму вычитаем из массива М. Затем в полученном массиве снова ищем нулевые элементы и так повторяем всю процедуру, пока не получим массив, полностью состоящий из *. Все преобразования массива до получения требуемого представлены на рисунке 2.3. В результате вычислений получили следующие классы порядка:

N₀ = {1, 2, 3, 4};

N₁ = {5, 6, 7, 8};

N₂ = {9, 10, 11, 13};

N₃ = {12, 14, 15};₄ = {16, 17};₅ = {18}.

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

Из вершины 1, принадлежащей нулевому уровню, к вершине 18, принадлежащей пятому уровню, ведут пути: 1, 16, 18; 1, 5, 10, 14, 16, 18; 1, 5, 10, 14, 17, 18; 1, 5, 13, 16, 18; 1, 5, 13, 14, 16, 18; 1, 5, 13, 14, 17, 18; 1, 5, 13, 17, 18; 1, 5, 13, 15, 18; 1, 5, 16, 18; 1, 5, 14, 16, 18; 1, 5, 14, 17, 18; 1, 5, 18; 1, 5, 15, 18. Их веса: 6, 33, 36, 19, 32, 35, 26, 36, 5, 23, 26, 4, 22.

Из вершины 2, принадлежащей нулевому уровню, к вершине 18, принадлежащей пятому уровню, ведут пути: 2, 7, 12, 18; 2, 7, 17, 18; 2, 10, 14, 16, 18; 2, 10, 14, 17, 18; 2, 12, 18; 2, 14, 16, 18; 2, 14, 17, 18; 2, 17, 18; 2, 15, 18; 2, 5, 10, 14, 16, 18; 2, 5, 10, 14, 17, 18; 2, 5, 13, 16, 18; 2, 5, 13, 17, 18; 2, 5, 13, 14, 16, 18; 2, 5, 13, 14, 17, 18; 2, 5, 13, 15, 18; 2, 5, 16, 18; 2, 5, 14, 16, 18; 2, 5, 14, 17, 18; 2, 5, 18; 2, 5, 15, 18. Их веса: 29, 28, 18, 21, 15, 26, 29, 13, 17, 42, 45, 28, 35, 41, 44, 45, 14, 32, 35, 13, 31.

Из вершины 3, принадлежащей нулевому уровню, к вершине 18, принадлежащей пятому уровню, ведут пути: 3, 6, 16, 18; 3, 6, 17, 18; 3, 6, 11, 12, 18; 3, 6, 9, 17, 18; 3, 5, 10, 14, 16, 18; 3, 5, 10, 14, 17, 18; 3, 5, 13, 16, 18; 3, 5, 13, 14, 16, 18; 3, 5, 13, 14, 17, 18; 3, 5, 13, 17, 18; 3, 5, 13, 15, 18; 3, 5, 16, 18; 3, 5, 14, 16, 18; 3, 5, 14, 17, 18; 3, 5, 18; 3, 5, 15, 18. Их веса: 9, 13, 34, 23, 33, 36, 19, 32, 35, 26, 36, 5, 23, 26, 4, 22.

Из вершины 4, принадлежащей нулевому уровню, к вершине 18, принадлежащей пятому уровню, ведут пути: 4, 16, 18; 4, 17, 18; 4, 8, 11, 12, 18; 4, 8, 15, 18; 4, 8, 9, 17, 18; 4, 9, 17, 18. Их веса: 15, 7, 33, 37, 17, 15.

Оптимальный путь, отвечающий максимальному общему весу 45 - 2, 5, 13, 15, 18. Оптимальные пути, отвечающие минимальному общему весу 4 - 1, 5, 18; 3, 5, 18.

Изобразим граф, расположив его вершины по уровням класса порядка.

Рисунок 2.4 - Топологически сортированный граф

Задание №3

Формулировка задания.

Дана матрица смежности графа. Найти центр графа и отклонение от центра для каждой вершины. Используя матрицу смежности, рассчитать общее число путей длиной 1, 2, 3, 4, 5, 6, а также с помощью поименованной матрицы смежности получить и все элементарные пути, указанной длины (в каждой следующей поименованной матрице все неэлементарные пути следует опускать). Матрица смежности:

A(G) = .

Решение.

Изобразим данный граф.

Рисунок 3.1 - Исходный граф

Составим матрицу R, элементы которой r(v_i, v_j) являются расстояниями (длинами путей) от вершины i до вершины j. Получим:

R = .

Отклонения вершин от центра графа:

D(1) =  (0+3+1+2+2+1) = ;

D(2) =  (3+0+2+2+1+1) = ;

D(3) =  (1+4+1+3+3+2) = ;

D(4) =  (1+1+2+0+1+2) = ;

D(5) =  (2+1+1+2+0+1) = ;

D(6) =  (2+2+1+1+1+1) = .

В данном графе минимальное отклонение от центра у вершин 4 и 5. Следовательно, множество вершин {4, 5} - центр графа.

Просуммировав все элементы данной матрицы смежности A(G), получим количество путей длиной 1, равное 16.

Чтобы получить количество путей длиной 2, 3, 4, 5 и 6, возведем матрицу A(G) в соответствующие степени:

A²(G) = ;³(G) = ;⁴(G) = ;⁵(G) = ;⁶(G) = .

Теперь просуммируем все элементы каждой из получившихся матриц и получим соответственно: количество путей длиной 2, равное 44; количество путей длиной 3, равное 121; количество путей длиной 4, равное 326; количество путей длиной 5, равное 876; количество путей длиной 6, равное 2357.

Далее найдем все элементарные пути заданной длины. Для этого составим поименованную матрицу смежности и вспомогательную матрицу:

A(G) = ;

A’(G) = .

С помощью вспомогательной матрицы вычислим степени матрицы A(G). Так как в данном графе имеется 6 вершин, то максимальная степень поименованной матрицы для определения всех элементарных путей будет равна 5.

Вычислив по формуле A²(G) = A(G) ∙ A’(G), получим следующие элементарные пути длиной 2: 1, 6, 3; 1, 6, 4; 1, 6, 5; 2, 5, 3; 2, 6, 3; 2, 6, 4; 2, 6, 5; 2, 5, 6; 3, 1, 6; 4, 5, 2; 4, 1, 3; 4, 5, 3; 4, 2, 5; 4, 1, 6; 4, 2, 6; 4, 5, 6; 5, 3, 1; 5, 6, 3; 5, 6, 4; 5, 2, 6; 6, 3, 1; 6, 4, 1; 6, 4, 2; 6, 5, 2; 6, 5, 3; 6, 4, 5.

Аналогично вычислим элементарные пути длиной 3: 1, 6, 4, 2; 1, 6, 5, 2; 1, 6, 5, 3; 1, 6, 4, 5; 2, 5, 3, 1; 2, 6, 3, 1; 2, 6, 4, 1; 2, 6, 5, 3; 2, 5, 6, 3; 2, 5, 6, 4; 2, 6, 4, 5; 3, 1, 6, 4; 3, 1, 6, 5; 4, 5, 3, 1; 4, 2, 5, 3; 4, 1, 6, 3; 4, 2, 6, 3; 4, 5, 6, 3; 4, 1, 6, 5; 4, 2, 6, 5; 4, 5, 2, 6; 4, 2, 5, 6; 5, 6, 3, 1; 5, 6, 4, 1; 5, 6, 4, 2; 5, 2, 6, 3; 5, 2, 6, 4; 5, 3, 1, 6; 6, 5, 3, 1; 6, 4, 5, 2; 6, 4, 1, 3; 6, 4, 5, 3; 6, 4, 2, 5.

Элементарные пути длиной 4: 1, 6, 4, 5, 2; 1, 6, 4, 5, 3; 1, 6, 4, 2, 5; 2, 6, 5, 3, 1; 2, 5, 6, 3, 1; 2, 5, 6, 4, 1; 2, 6, 4, 1, 3; 2, 5, 3, 1, 6; 3, 1, 6, 4, 2; 3, 1, 6, 5, 2; 3, 1, 6, 4, 5; 4, 2, 5, 3, 1; 4, 2, 6, 3, 1; 4, 5, 6, 3, 1; 4, 1, 6, 5, 2; 4, 1, 6, 5, 3; 4, 2, 6, 5, 3; 4, 5, 2, 6, 3; 4, 2, 5, 6, 3; 4, 5, 3, 1, 6; 5, 2, 6, 3, 1; 5, 2, 6, 4, 1; 5, 6, 4, 1, 3; 5, 3, 1, 6, 4; 6, 4, 5, 3, 1; 6, 4, 2, 5, 3.

Элементарные пути длиной 5: 1, 6, 4, 2, 5, 3; 2, 5, 6, 4, 1, 3; 2, 5, 3, 1, 6, 4; 3, 1, 6, 4, 5, 2; 3, 1, 6, 4, 2, 5; 4, 2, 6, 5, 3, 1; 4, 5, 2, 6, 3, 1; 4, 2, 5, 6, 3, 1; 4, 2, 5, 3, 1, 6; 5, 3, 1, 6, 4, 2; 5, 2, 6, 4, 1, 3; 6, 4, 2, 5, 3, 1.

Задание №4

Формулировка задания.

Дана матрица смежности графа. Построить для данного графа дополнительный и двойственный. Указать остовы (не менее 5), базисные циклы, базисные разрезы, найти ранг и цикломатическое число, подсчитать количество возможных остовов. Матрица смежности:

A(G) = .

Решение

Изобразим данный граф в планарной укладке.

Рисунок 4.1 - Исходный граф в планарной укладке

Изобразим отдельно двойственный и дополнительный графы.

Рисунок 4.2 - Двойственный граф G’

Рисунок 4.3 - Дополнительный граф

Изобразим один из остовов исходного графа G.

                                                    e₃

                                            e₂                  e₁

                                                                               e₄

                                               e₈                e₉                e₅

                                           e₇                    e₆

Рисунок 4.4 - Один из остовов исходного графа G

Остовные ребра для выбранного остова: e₁, e₂, e₃, e₄, e₅, e₆, e₇.

Хорды: e₈, e₉.

Базисные циклы: 125471, 2452.

Базисные разрезы: e₂; e₃; e₇; e₁e₈; e₆e₈; e₄e₈e₉; e₅e₈e₉.

Ранг графа G k=7, цикломатическое число графа l=2.

Матрица Кирхгофа графа G:

K = .

Чтобы найти количество возможных остовов для графа G, необходимо найти какое-либо алгебраическое дополнение матрицы Кирхгофа. Вычислив алгебраическое дополнение K₂₂, получили возможное количество остовов равное 11.

Один из возможных остовов мы указали в начале задания. Укажем еще 4 возможных остова.

Рисунок 4.5 - Примеры возможных остовов

5 Задание №5

Формулировка задания.

Матрица смежности:

A(G) = .

Решение

Изобразим двудольный граф G.

Рисунок 5.1 - Двудольный граф

Изобразим реберный граф Gр.

Рисунок 5.2 - Реберный граф

Максимальные паросочетания для двудольного графа G:

1) e₁, e₃;

) e₁, e₅;

) e₁, e₆;

) e₁, e₇;

) e₂, e₅;

) e₂, e₆;

) e₂, e₇;

) e₃, e₄;

) e₄, e₆;

) e₄, e₇.

Минимальные реберные покрытия для двудольного графа G:

) e₁, e₂, e₄, e₆, e₇;

2) e₁, e₂, e₅, e₆, e₇;

) e₁, e₃, e₄, e₆, e₇;

) e₁, e₃, e₅, e₆, e₇.

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

) 1, 3;

) 1, 5;

) 1, 6;

) 1, 7;

) 2, 5;

) 2, 6;

) 2, 7;

) 3, 4;

) 4, 6;

) 4, 7.

Минимальные вершинные покрытия являются дополнениями к максимальным вершинным независимым множествам:

) 2, 4, 5, 6, 7;

) 2, 3, 4, 6, 7;

) 2, 3, 4, 5, 7;

) 2, 3, 4, 5, 6;

) 1, 3, 4, 6, 7;

) 1, 3, 4, 5, 7;

) 1, 3, 4, 5, 6;

) 1, 2, 5, 6, 7;

) 1, 2, 3, 5, 7;

) 1, 2, 3, 5, 6.

Найдем минимальные вершинные покрытия реберного графа с помощью КНФ. Для данного графа КНФ имеет вид:

f(G_p) = (1v2)(1v4)(2v3)(2v4)(3v5)(3v6)(3v7)(4v5)(5v6)(5v7)(6v7). (1)

Преобразуем f(G_p), раскрывая скобки и используя закон поглощения:

f(G_p) = (1v24)(2v34)(3v567)(6v7) = (12v134v24v234)(35v3467v567v4567) (6v7) = (12v134v24)(356v357v3467v567) = 12356 v 12357 v 123467 v 12567 v v13456 v 13457 v 13467 v 134567 v 23456 v 23457 v 23467 v 24567. (2)

Для проверки по принципу двойственности составим для функции (2) двойственную:

(G_p) = (1v2v3v5v6)(1v2v3v5v7)(1v2v3v4v6v7)(1v2v5v6v7)(1v3v4v5v6) (1v3v4v5v7)(1v3v4v6v7)(1v3v4v5v6v7)(2v3v4v5v6)(2v3v4v5v7)(2v3v4v6v7) (2v4v5v6v7). (3)

Преобразуем функцию (3), используя тождества поглощения и идемпотентности. Получим:

(G_p) = (1v2v3v5v6)(1v2v3v5v7)(1v2v3v4v6v7)(1v2v5v6v7)(1v3v4v5v6) (1v3v4v5v7)(1v3v4v6v7)(1v3v4v5v6v7)(2v3v4v5v6)(2v3v4v5v7)(2v3v4v6v7) (2v4v5v6v7) = (1v2v3v5v67)(1v5v6v23v24v37v47)(1v3v4v7v56)(2v3v4v5v67) (2v4v6v7v35) = (1v5v23v24v26v36v37v67) (3v4v12v15v27v57v67v56) (2v4v6v7v35) = (12v13v14v15v35v45v57v67v56v23v24v36v37)(2v4v6v7v35) = =12v14v23v24v35v36v37v45v56v57v67 (4)

Так как функция (4) является двойственной для функции (1), значит вершинные покрытия были найдены верно.

Заключение

В данной работе были решены конкретные задачи с применением теории графов.

Главной задачей было практическое закрепление научно-теоретических материалов теории графов и получение навыков применения полученных знаний для решения конкретных задач.

Все поставленные цели и задачи были решены в данной работе.

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

Список используемых источников

1.      Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: Высш. школа, 1976. - С. 392.

.        Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.

.        Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384с.

.        Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.

5.  Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с.

6.      Харари Ф. Теория графов. - М.: КомКнига, 2006. - 296 с.