Алгоритмы обработки орграфов, остовное дерево для неориентированного взвешенного графа, потроение минимального остовного дерева по алгоритмам: Борувки, Ярника (Прима) и Крускала

Среда программирования: Visual C# .NET 2015

Название работы: Алгоритмы обработки орграфов, остовное дерево для неориентированного взвешенного графа, потроение минимального остовного дерева по алгоритмам: Борувки, Ярника (Прима) и Крускала

Вид работы: Лабораторная работа

Описание: Лабораторная работа № 1
Задание
Написать программу, которая для неориентированного графа, заданного множеством вершин и ребер (данные находятся во входном файле):
1. Строит и выводит на экран списки смежности и матрицу смежности
2. Определяет:
• степени всех вершин и выводит список вершин с их степенями;
• изолированные вершины и выводит их список;
• висячие вершины и выводит их список;
• висячие ребра и выводит их список;
• вершины, в которых имеются петли, и выводит список таких вершин с кратностями петель;
• кратные ребра и выводит их список с кратностями
3. Приводит исходный граф к форме простого графа: удаляет петли и для кратных ребер оставляет только одно ребро. Для преобразованного графа выводит списки смежности
4. Определяет количество компонент связности преобразованного графа и выводит на экран состав каждой компоненты в форме списка входящих в компоненту вершин
5. Для каждой не тривиальной компоненты связности строит остовное дерево двумя способами: с помощью алгоритма поиска в глубину (DFS) и с помощью алгоритма поиска в ширину (BFS)
Отчет о работе должен содержать:
1. Исходный код программы
2. Скриншоты результатов работы
3. Рисунки: исходного графа, преобразованного простого графа с выделением компонент связности и остовных деревьев

Лабораторная работа № 2 «Алгоритмы обработки орграфов»
Задание
1. С использованием исходных данных лаб. работы № 1 и разработанного программного обеспечения построить орграф, соответствующий максимальной связной компоненте заданного графа (максимальной считается компонента связности с максимальным количеством вершин).
2. Для построенного орграфа выполнить следующее:
• для каждой вершины вывести значения полустепени исхода и полустепени захода;
• вывести список вершин-источников и список вершин-стоков;
• для каждой вершины вывести список достижимых из нее вершин;
• на основе анализа списков достижимости определить компоненты сильной связности (или доказать их отсутствие);
• проверить орграф на ацикличность.
3. Выполнить топологическую сортировку ациклического орграфа, заданного в исходном файле к лаб. работе № 2. Изобразить орграф в линейном виде с учетом топологического упорядочения. Изобразить орграф в ярусно-параллельной форме.
Отчет о работе должен содержать:
1. Исходный код программы
2. Скриншоты результатов работы
3. Графический иллюстративный материал.
Пример.
1. Исходный файл:
10
4 1
6 5
4 5
6 3
4 3
6 10
4 10
1 9
5 9
4 9
5 2
1 2
5 7
1 8
2. Результат топологического упорядочения:
Кол-во вершин: 10
Кол-во ребер: 14
Списки смежности:
1 : 9 2 8
2 :
3 :
4 : 1 5 3 10 9
5 : 9 2 7
6 : 5 3 10
7 :
8 :
9 :
10 :
4 6 10 1 3 5 7 8 9 2
Ярусно-параллельная форма:

Лабораторная работа № 3 «Алгоритмы обработки орграфов, часть 2»
Задание
1. Разработать программу, приводящую заданный ациклический орграф (DAG) к ярусно-параллельной форме. Использовать исходные данные к лаб. работе № 2.
2. Разработать программу, отыскивающую компоненты сильной связности в заданном орграфе (см.исходные данные к лаб. работе № 3). Программа должна быть построена на основе алгоритма Kosaraju-Sharir.
3. Модифицировать программу из п.2 таким образом, чтобы она позволяла для заданного орграфа получать его метаграф. Показать, что метаграф является DAG.
Отчет о работе должен содержать:
1. Исходные коды программы
2. Скриншоты результатов работы
3. Графический иллюстративный материал.
Пример.
1. Исходный файл:
8
1 2
2 3
3 4
4 3
5 1
2 5
5 6
2 6
6 7
7 6
3 7
8 7
4 8
8 4
Исходный граф:
Выделение сильных компонент:
Метаграф:

Лабораторная работа № 4 «Минимальные остовные деревья»
Задание
Построить минимальное остовное дерево для заданного неориентированного взвешенного графа.
Формат входного файла: первая строка – количество вершин графа, вторая и последующие строки – ребра графа в формате «вершина-вершина-вес».
1. Разработать и реализовать 3 программы потроения минимального остовного дерева по алгоритмам: Борувки, Ярника (Прима) и Крускала.
Отчет о работе должен содержать:
1. Исходные коды программ
2. Скриншоты результатов работы
3. Графический иллюстративный материал.
Пример.
1. Исходный файл:
10
1 2 6
1 3 3
1 4 9
2 3 4
2 5 2
2 6 9
3 5 2
3 4 9
3 7 9
4 7 8
4 10 18
5 6 9
5 7 8
6 7 7
6 8 4
6 9 5
7 9 9
7 10 10
8 9 1
8 10 4
9 10 3
Исходный граф и его минимальное остовное дерево:

Год: 2017

Данный заказ (лабораторная работа) выполнялся нашим сайтом в 2017-м году, в рамках этого заказа была разработана программа в среде программирования Visual C# .NET 2015. Если у Вас похожее задание на программу, которую нужно написать на Visual C# .NET 2015, либо на другом языке программирования, пожалуйста заполните форму, приведённую ниже, после чего Ваше задание в первую очередь рассмотрит наш программист, выполнявший в 2017-м году этот заказ, если он откажется, то Ваше задание оценят другие наши программисты в течение 48-и часов, если оценка нужна срочно, просим Вас оставить пометку об этом - напишите в тексте задания фразу "СРОЧНЫЙ ЗАКАЗ".

Тел.: +79374242235 Viber: +79374242235 Telegram: kursovikcom ВКонтакте: kursovikcom WhatsApp +79374242235 E-mail: info@kursovik.com Skype: kursovik.com