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

 

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

Содержание

Введение

Задание №1

Задание №2

Задание №3

Задание №4

Задание №5

Заключение

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

Введение

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

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

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

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

1 Задание №1

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

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

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

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

Решение

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

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

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

G0(1) = {1};

G1(1) = {1, 2, 8, 18};

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

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

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

Остальные степени оператора G находить не нужно, так как это не приводит к появлению во множестве Gk(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

C1 = 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), можно заключить, что C2 = {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

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

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

C9 = {9}.

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

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

Задание №2

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

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

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

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

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

Решение

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

N0 = {1, 2, 3, 4};

N1 = {5, 6, 7, 8};

N2 = {9, 10, 11, 13};

N3 = {12, 14, 15};4 = {16, 17};5 = {18}.

Рисунок 2.3 - Нахождение классов порядка

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

Из вершины 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(vi, vj) являются расстояниями (длинами путей) от вершины 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) в соответствующие степени:

A2(G) = ;3(G) = ;4(G) = ;5(G) = ;6(G) = .

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

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

A(G) = ;

A(G) = .

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

Вычислив по формуле A2(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.

e3

e2e1

e4

e8e9e5

e7e6

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

Остовные ребра для выбранного остова: e1, e2, e3, e4, e5, e6, e7.

Хорды: e8, e9.

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

Базисные разрезы: e2; e3; e7; e1e8; e6e8; e4e8e9; e5e8e9.

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

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

K = .

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

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

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

5 Задание №5

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

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

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

A(G) = .

Решение

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

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

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

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

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

1) e1, e3;

) e1, e5;

) e1, e6;

) e1, e7;

) e2, e5;

) e2, e6;

) e2, e7;

) e3, e4;

) e4, e6;

) e4, e7.

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

) e1, e2, e4, e6, e7;

2) e1, e2, e5, e6, e7;

) e1, e3, e4, e6, e7;

) e1, e3, e5, e6, e7.

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

) 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(Gp) = (1v2)(1v4)(2v3)(2v4)(3v5)(3v6)(3v7)(4v5)(5v6)(5v7)(6v7). (1)

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

f(Gp) = (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) двойственную:

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

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

(Gp) = (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 с.

Решение задач с применением теории графов Содержание Введение Задание №1 Задание №2 Задан

Больше работ по теме: