Методические указания по выполению домашнего задания по дисциплине Дискретная математика Тема «Алгоритмы на графах» - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
2638 Задания к контрольной работе по дисциплине «теория механизмов... 1 389.35kb.
Методические указания к практическому занятию по дисциплине «Математика»... 1 202.1kb.
Методические указания к практическим занятиям по дисциплине «Математика»... 1 233.42kb.
Методические указания к практическим занятиям по дисциплине «Математика»... 3 294.49kb.
Методические указания, контрольные задания и типовые примеры по теоретической... 8 994.88kb.
Методические указания разработаны на основании гос впо 653500 «Строительство» 2 404.4kb.
Характер и внешность человека 1 89.6kb.
Методические указания и контрольные задания по курсу «Математика. 2 453.02kb.
Методические указания по решению типовых задач, а также задания на... 3 1082.21kb.
Лабораторная работа №1 по дисциплине: Дискретная математика Группа 1 77.9kb.
Методические указания по написанию эссе по дисциплине «Региональная... 1 172.46kb.
Деревья Деревья. Свойства деревьев. Ориентированные, упорядоченные... 1 89.16kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Методические указания по выполению домашнего задания по дисциплине Дискретная математика - страница №1/1


Министерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования


«Московский государственный университет приборостроения и информатики»
Кафедра ИТ-6 «Управление и моделирование систем»







Утверждаю

Зав. кафедрой ИТ-6






_____________ /Мацнев А.П./




«____» ____________ 2012 г.




Методические указания по выполению
домашнего задания

по дисциплине Дискретная математика





Тема «Алгоритмы на графах»


Направления подготовки студентов

231000.62, 090303.65, 090900.62



















Москва, МГУПИ 2012 г.


Задание: Разработать алгоритм решения задачи (согласно приведенной таблице заданий) и соответствующую программу на языке высокого уровня по выбору студента. Провести оценку трудоемкости полученного алгоритма (программы) O(f(N)).

Программа должна позволять вводить (задавать каким-либо образом) структуру произвольного графа, согласно заданию, допускается консольный ввод и/или из файла. Разработка пользовательского интерфейса для графического отображения и построения графа и его весов в обязательном порядке не требуется, однако приветствуется и может быть выполнена студентом в рамках междисциплинарных проектах (например, с дисциплиной «Объектно-ориентированное программирование») или студент может воспользоваться сторонними библиотеками программ. Вывод результата (ответа) должен быть достаточен для интерпретации и его проверки.


Результаты представить в качестве печатного отчета, состоящего из следующего:

  1. Титул

  2. Задание. Вариант задания определить как две последние цифры студенческого билета.

  3. Привести полный листинг программы с выкладками, поясняющими ход получения оценки трудоемкости алгоритма.

  4. Контрольный пример, который должен содержать графическое изображение структуры графа (рисунок в любом виде/формате) и результат работы программы (скриншот) для соответствующего графа.

  5. Иметь при себе (flesh|/CD/DVD-ROM) электронную копию исходного кода и выполнимого файла программы для демонстрации работы программы во время защиты отчета на графе, предложенного преподавателем.





Алгоритм

Способ представления графа

Фамилия



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

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






Дана матрица весов дуг. Определить ВСЕ (т.е. не обязательно самые короткие) незамкнутые пути в орграфе заданной длины х (вводится с клавиатуры).

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






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

где p1(G) – цикломатическое число,  — число компонент связности графа, E|G| – число ребер, а V|G| – число вершин.



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






Методом Прима построить ОДМС и определить его стоимость

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






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

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






Определить все минимальные компоненты не взвешенного орграфа. Пояснение: Пусть K и K' - компоненты сильной связности графа G. Компонента K достижима из компоненты K’, если K= K' или существуют такие две вершины uK и vK, что вершина u достижима из вершины v. K строго достижима из K’, если KK’ и K достижима из K'. Компонента K называется минимальной, если она не является строго достижимой ни из какой компоненты. Примеры: http://www.intuit.ru/department/ds/discrmath/9/discrmath_9.html

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






Определить все непересекающиеся цепи между двумя произвольными узами графа.

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






Определить ВСЕ простые пути в орграфе.

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






Определить наличие всех циклов методом обхода в глубину на орграфе и на этой основе определить обхват графа (то есть цикл с минимальной стоимостью использованных дуг), причем цикл может включать лишь подмножество вершин графа.

Список дуг






Определить радиус не взвешенного неориентированного графа методом обхода в ширину (радиусом графа будем называть наибольшее среди кратчайших расстояний от центра до достижимых от него узлов)

Список дуг






Определить число сильно связных компонент в орграфе

Список дуг






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

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






Вывести на экран все существующие пути в ациклическом орграфе

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






Дана матрица весов дуг. Определить ВСЕ (т.е. не обязательно самые короткие) незамкнутые пути в орграфе заданной длины х (вводится с клавиатуры).

Список смежности






Алгоритм

Способ представления графа

Фамилия



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

где p1(G) – цикломатическое число,  — число компонент связности графа, E|G| – число ребер, а V|G| – число вершин.



Список дуг






Методом Прима построить ОДМС и определить его стоимость

Список смежности






Определить k-связанность заданного неориентированного графа и вывести полученное число k на экран. (Граф называется k-связным, если между любой парой вершин v и w существует не менее k разных путей, таких, что, за исключением вершин v и w, ни одна из вершин, входящих в один путь, не входит ни в какой другой из этих путей).

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






Определить все минимальные компоненты не взвешенного орграфа. Пояснение: Пусть K и K' - компоненты сильной связности графа G. Компонента K достижима из компоненты K’, если K= K' или существуют такие две вершины uK и vK, что вершина u достижима из вершины v. K строго достижима из K’, если KK’ и K достижима из K'. Компонента K называется минимальной, если она не является строго достижимой ни из какой компоненты. Примеры: http://www.intuit.ru/department/ds/discrmath/9/discrmath_9.html

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






Определить все непересекающиеся цепи между двумя произвольными узами графа

Список смежности






Определить ВСЕ простые пути в орграфе.

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






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

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






Определить наличие всех циклов методом обхода в ширину на орграфе. Вывести все циклы (варианты обхода, образующие циклы). Подсчитать их общее количество.

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






Определить радиус взвешенного ориентированного графа (радиусом графа будем называть наибольшее среди кратчайших расстояний от центра до достижимых от него узлов)

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






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

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






Вывести на экран все существующие пути в ациклическом орграфе

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






Дана матрица весов дуг. Определить ВСЕ (т.е. не обязательно самые короткие) незамкнутые пути в орграфе заданной длины х (вводится с клавиатуры).

Список дуг






Методом Прима построить ОДМС и определить его стоимость

Список дуг






Алгоритм

Способ представления графа

Фамилия



Определить k-связанность заданного неориентированного графа и вывести полученное число k на экран. (Граф называется k-связным, если между любой парой вершин v и w существует не менее k разных путей, таких, что, за исключением вершин v и w, ни одна из вершин, входящих в один путь, не входит ни в какой другой из этих путей).

Список смежности






Определить все непересекающиеся цепи между двумя произвольными узами графа

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






Определить ВСЕ простые пути в орграфе.

Список смежности






Определить минимальное число красок, которыми можно раскрасить граф и вывести пример такой раскраски.

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






Определить минимальную компоненту не взвешенного орграфа. Пояснение: Пусть K и K' - компоненты сильной связности графа G. Компонента K достижима из компоненты K’, если K= K' или существуют такие две вершины uK и vK, что вершина u достижима из вершины v. K строго достижима из K’, если KK’ и K достижима из K'. Компонента K называется минимальной, если она не является строго достижимой ни из какой компоненты. Примеры: http://www.intuit.ru/department/ds/discrmath/9/discrmath_9.html

Список смежности






Определить наличие всех циклов методом обхода в ширину на орграфе и на этой основе определить обхват графа (то есть цикл с минимальной стоимостью использованных дуг), причем цикл может включать лишь подмножество вершин графа.

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






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

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






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

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






Вывести на экран все существующие пути в ациклическом орграфе

Список смежности






Методом Крускала построить ОДМС и определить его стоимость

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






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

где p1(G) – цикломатическое число,  — число компонент связности графа, E|G| – число ребер, а V|G| – число вершин.



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






Алгоритм

Способ представления графа

Фамилия



Определить все минимальные компоненты не взвешенного орграфа. Пояснение: Пусть K и K' - компоненты сильной связности графа G. Компонента K достижима из компоненты K’, если K= K' или существуют такие две вершины uK и vK, что вершина u достижима из вершины v. K строго достижима из K’, если KK’ и K достижима из K'. Компонента K называется минимальной, если она не является строго достижимой ни из какой компоненты. Примеры: http://www.intuit.ru/department/ds/discrmath/9/discrmath_9.html

Список дуг






Определить ВСЕ простые пути в орграфе.

Список дуг






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

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






Определить минимальное число красок, которыми можно раскрасить граф и вывести пример такой раскраски.

Список смежности






Определить наличие всех циклов методом обхода в ширину на орграфе и на этой основе определить обхват графа (то есть цикл с минимальной стоимостью использованных дуг), причем цикл может включать лишь подмножество вершин графа.

Список смежности






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

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






Пусть дана сеть (узел а – исток, b–сток). Определить все разрезы сети.(на основе определения понятия разреза)

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






Транзитивная редукция ориентированного графа G = (V, Е) определяется как произвольный граф G' — (V, Е'), имеющий то же множество вершин, но с минимально возможным числом дуг (E’  E), транзитивное замыкание которого совпадает с транзитивным замыканием графа G, (причем если граф G ацикличен, то его транзитивная редукция единственна). Реализуйте программу транзитивной редукции графа.

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






Вывести на экран все существующие пути в ациклическом орграфе

Список дуг






Дана матрица весов дуг. Определить и вывести все циклы в орграфе, заданной длины х (вводится с клавиатуры)

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






Методом Крускала построить ОДМС и определить его стоимость

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






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

где p1(G) цикломатическое число,  — число компонент связности графа, E|G| – число ребер, а V|G| – число вершин.



Список смежности






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

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






Алгоритм

Способ представления графа

Фамилия



Определить базу (хотя бы одну, но по возможности все базы) орграфа G. Пояснение:. Подмножество вершин WV называется порождающим, если из вершин W можно достичь любую вершину графа. Подмножество вершин WV называется базой графа, если оно является порождающим, но никакое его собственное подмножество порождающим не является (т.е. может быть W1, W2, … : W1W2=, но из каждого Wi достижимы остальные вершины). Примеры: http://www.intuit.ru/department/ds/discrmath/9/discrmath_9.html

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






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

Список смежности






Определить минимальное число красок, которыми можно раскрасить граф и вывести пример такой раскраски.

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






Определить наличие всех циклов методом обхода в ширину на орграфе. Вывести все циклы (варианты обхода, образующие циклы). Подсчитать их общее количество.

Список дуг






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

Список смежности






Пусть дана сеть (узел а – исток, b–сток). Определить все разрезы сети. (на основе определения понятия разреза)

Список смежности






Транзитивная редукция ориентированного графа G = (V, Е) определяется как произвольный граф G' — (V, Е'), имеющий то же множество вершин, но с минимально возможным числом дуг (E’  E), транзитивное замыкание которого совпадает с транзитивным замыканием графа G, (причем если граф G ацикличен, то его транзитивная редукция единственна). Реализуйте программу транзитивной редукции графа.

Список смежности






Дана матрица весов дуг. Определить и вывести все циклы в орграфе, заданной длины х (вводится с клавиатуры)

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






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

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






Методом Крускала построить ОДМС и определить его стоимость

Список смежности






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

где p1(G) – цикломатическое число,  — число компонент связности графа, E|G| – число ребер, а V|G| – число вершин.



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






Алгоритм

Способ представления графа

Фамилия



Определить базу (хотя бы одну, но по возможности все базы) орграфа G. Пояснение:. Подмножество вершин WV называется порождающим, если из вершин W можно достичь любую вершину графа. Подмножество вершин WV называется базой графа, если оно является порождающим, но никакое его собственное подмножество порождающим не является (т.е. может быть W1, W2, … : W1W2=, но из каждого Wi достижимы остальные вершины). Примеры: http://www.intuit.ru/department/ds/discrmath/9/discrmath_9.html

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






Определить в орграфе сильно связные компоненты, подсчитать их число и вывести состав (номера узлов) каждой сильно связной компоненты.

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






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

Список дуг






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

Список дуг






Пусть дана сеть (узел а – исток, b–сток). Определить все разрезы сети. (на основе определения понятия разреза)

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






Дана матрица весов дуг. Определить и вывести все циклы в орграфе, заданной длины х (вводится с клавиатуры)

Список смежности






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

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






Методом Крускала построить ОДМС и определить его стоимость

Список дуг






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

где p1(G) – цикломатическое число,  — число компонент связности графа, E|G| – число ребер, а V|G| – число вершин.



Список дуг






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

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






Алгоритм

Способ представления графа

Фамилия



Определить базу (хотя бы одну, но по возможности все базы) орграфа G. Пояснение:. Подмножество вершин WV называется порождающим, если из вершин W можно достичь любую вершину графа. Подмножество вершин WV называется базой графа, если оно является порождающим, но никакое его собственное подмножество порождающим не является (т.е. может быть W1, W2, … : W1W2=, но из каждого Wi достижимы остальные вершины). Примеры: http://www.intuit.ru/department/ds/discrmath/9/discrmath_9.html

Список смежности






Определить в орграфе сильно связные компоненты, подсчитать их число и вывести состав (номера узлов) каждой сильно связной компоненты.

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






Определить величину минимального разреза сети основе определения разреза – т.е. перебором сочетаний дуг, определяя, что этот набор дуг есть допустимый разрез и находя минимум на стоимостях разрезов графа.

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






Определить наличие всех циклов методом обхода в глубину на орграфе. Вывести все циклы (варианты обхода, образующие циклы). Подсчитать их общее количество.

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






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

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






Орграф G' = (V, Е') называется минимальным эквивалентным орграфом для орграфа G = (V, Е), если Е' — наименьшее подмножество множества Е (E’  E) такое что транзитивные замыкания обоих орграфов G и G' совпадают (причем если граф G ацикличен, то для него существует только один минимальный эквивалентный орграф). Написать программу нахождения минимального эквивалентного орграфа.

Список смежности






Дана матрица весов дуг. Определить и вывести все циклы в орграфе, заданной длины х (вводится с клавиатуры)

Список дуг






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

Список смежности






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

где p1(G) – цикломатическое число,  — число компонент связности графа, E|G| – число ребер, а V|G| – число вершин.



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






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

Список смежности






Алгоритм

Способ представления графа

Фамилия



Определить базу (хотя бы одну, но по возможности все базы) орграфа G. Пояснение:. Подмножество вершин WV называется порождающим, если из вершин W можно достичь любую вершину графа. Подмножество вершин WV называется базой графа, если оно является порождающим, но никакое его собственное подмножество порождающим не является (т.е. может быть W1, W2, … : W1W2=, но из каждого Wi достижимы остальные вершины). Примеры: http://www.intuit.ru/department/ds/discrmath/9/discrmath_9.html

Список дуг






Определить величину минимального разреза сети основе определения разреза – т.е. перебором сочетаний дуг, определяя, что этот набор дуг есть допустимый разрез и находя минимум на стоимостях разрезов графа.

Список смежности






Определить наличие всех циклов методом обхода в глубину на орграфе. Вывести все циклы (варианты обхода, образующие циклы). Подсчитать их общее количество.

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






Определить радиус не взвешенного неориентированного графа методом обхода в ширину(радиусом графа будем называть наибольшее среди кратчайших расстояний от центра до достижимых от него узлов)

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






Определить число сильно связных компонент в орграфе

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






Орграф G' = (V, Е') называется минимальным эквивалентным орграфом для орграфа G = (V, Е), если Е' — наименьшее подмножество множества Е (E’  E) такое что транзитивные замыкания обоих орграфов G и G' совпадают (причем если граф G ацикличен, то для него существует только один минимальный эквивалентный орграф). Написать программу нахождения минимального эквивалентного орграфа.

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






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

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






Дана матрица весов дуг. Определить ВСЕ (т.е. не обязательно самые короткие) незамкнутые пути в орграфе заданной длины х (вводится с клавиатуры).

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






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

Список дуг






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

где p1(G) – цикломатическое число,  — число компонент связности графа, E|G| – число ребер, а V|G| – число вершин.



Список смежности






Методом Прима построить ОДМС и определить его стоимость

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






Алгоритм

Способ представления графа

Фамилия



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

Список смежности






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

Список дуг






Определить величину минимального разреза сети основе определения разреза – т.е. перебором сочетаний дуг, определяя, что этот набор дуг есть допустимый разрез и находя минимум на стоимостях разрезов графа.

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






Определить внешний не взвешенного неориентированного графа методом обхода в ширину (радиусом графа будем называть наибольшее среди кратчайших расстояний от центра до достижимых от него узлов)

Список смежности






Определить наличие всех циклов методом обхода в глубину на орграфе и на этой основе определить обхват графа (то есть цикл с минимальной стоимостью использованных дуг), причем цикл может включать лишь подмножество вершин графа.

Список смежности






Определить число сильно связных компонент в орграфе

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






Определить число сильно связных компонент в орграфе

Список смежности