Написать две программы Тема: Графы

Лабораторная №1

3.1 Получить задание в виде одного из двух способов матричного представления графа:

матрица инцидентности

1.2 Составить алгоритм программы, реализующей перевод из заданного способа матричного представления графа в другой, учитывая при этом исходный тип графа (неориентированный, ориентированный, смешанный).

1.3 Создать программу, реализующую перевод из заданного способа матричного представления графа в другой. Предусмотреть консольный ввод исходных данных и вывод результатов работы программы на экран.

Лабораторная №2

2.1 Получить в виде исходного ориентированного графа.

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

2.3 Составить блок-схему программы, реализующей алгоритм топологической сортировки с произвольной нумерацией вершин графа.

2.4 Создать программу, реализующую метод динамического программирования и алгоритм топологической сортировки вершин. Исходный граф задается в виде матрицы смежности, вводимой построчно с помощью консоли. Указание: для определения вершин, входящих в множество Г-1(xi) используйте j-й столбец матрицы смежности.

СОДЕРЖАНИЕ ОТЧЕТА ПО РАБОТЕ

1 Исходное задание и цель работы.

4.2 Блок-схема программы по п.3.2.

4.3 Блок-схема программы по п.3.3.

4.3 Распечатка текста программы по п.3.4.

4.4 Контрольный пример и результаты машинного расчета.

4.5 Выводы по работе.