Домашнее задание Графы (100 вар) условие

№

Алгоритм

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

Фамилия

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

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

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

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

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

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

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

Список дуг

Методом Флойда найти самое длинное среди минимальных расстояние между двумя узлами

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

Методом Флойда найти самое длинное среди минимальных расстояние между двумя узлами

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

Методом Флойда найти самое длинное среди минимальных расстояние между двумя узлами

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

Методом Флойда найти самое длинное среди минимальных расстояние между двумя узлами

Список дуг

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

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

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

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

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

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

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

Список дуг

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

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

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

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

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

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

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

Список дуг

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

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

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

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

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

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

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

Список дуг

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

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

№

Алгоритм

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

Фамилия

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

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

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

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

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

Список дуг

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

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

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

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

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

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

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

Список дуг

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

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

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

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

№

Алгоритм

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

Фамилия

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

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

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

Список дуг

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

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

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

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

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

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

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

Список дуг

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

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

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

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

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

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

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

Список дуг

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

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

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

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

№

Алгоритм

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

Фамилия

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

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

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

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

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

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

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

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

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

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

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

Список дуг

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

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

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

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

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

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

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

Список дуг

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

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

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

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

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

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

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

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

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

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

№

Алгоритм

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

Фамилия

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

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

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

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

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

Список дуг

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

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

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

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

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

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

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

Список дуг

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

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

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

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

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

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

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

Список дуг

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

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

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

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

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

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

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

Список дуг

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

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

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

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

№

Алгоритм

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

Фамилия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определить величину минимального разреза сети.

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

Определить величину минимального разреза сети.

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

Определить величину минимального разреза сети.

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

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

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

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

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

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

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

№

Алгоритм

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

Фамилия

Методом обхода в ширину вычислить цикломатическую сложность графа

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

Методом обхода в ширину вычислить цикломатическую сложность графа

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

Методом обхода в ширину вычислить цикломатическую сложность графа

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

Методом обхода в ширину вычислить цикломатическую сложность графа

Список дуг

Методом обхода в глубину вычислить цикломатическую сложность графа

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

Методом обхода в глубину вычислить цикломатическую сложность графа

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

Методом обхода в глубину вычислить цикломатическую сложность графа

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

Методом обхода в глубину вычислить цикломатическую сложность графа

Список дуг

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

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

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

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

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

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