Лабораторная работа 3 Дискретная математика - Поиск компонент связности графа
-
Категории:
ДО СИБГУТИ, Работа Лабораторная, Дискретная математика
-
Добавлен:
27.10.2024
-
Размер:
268 KB
-
Покупок:
3
-
Добавил:
SOKOLOV
Написать сообщение
Скачать
Состав работы
|
|
|
|
Labrabs3.exe
|
|
Labrabs3.pas
|
Лабораторная работа №3.docx
|
Необходимые программы
Работа представляет собой zip архив с файлами (распаковать онлайн), которые открываются в программах:
- Microsoft Word
Описание
Лабораторная работа № 3 Поиск компонент связности графа.
Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа (по материалам главы 3, п. 3.2.3 и 3.4). При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину по материалам п. 3.4.3).
Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т.е. изменять исходный граф без выхода из программы. Предусмотреть также возможность изменения количества вершин.
При выполнении работы разрешается (даже рекомендуется!) использовать матрицу бинарных отношений из лабораторной работы №1.
Вход программы: число вершин графа и матрица смежности.
Выход: разбиение множества вершин на подмножества, соответствующие компонентам связности.
Дополнительно:
Заданный граф рассматривать как ориентированный. Выполнять поиск компонент сильной связности.
Описание работы
Программа работает с неориентированным графом. Для поиска компонент связности введем массив состояний вершин графа, в котором будем отмечать уже просмотренные вершины. Если вершина просмотрена, то в соответствующий элемент массива записываем значение True. В основном цикле поиска компонент связности перебираем все вершины по порядку.
Если вершина еще не просмотрена, т.е. пока не вошла ни в какую компоненту связности, то запускаем алгоритм поиска всей компоненты связности, начиная с этой вершины, т.е. поиска компоненты связности, в которую входит эта вершина. Все вершины компоненты связности определяем путем поиска в глубину, используя для этого рекурсию. При этом все вершины, принадлежащие этой компоненте связности, помечаем как просмотренные. После нахождения очередной вершины текущей компоненты связности выводим номер вершины на экран.
Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа (по материалам главы 3, п. 3.2.3 и 3.4). При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину по материалам п. 3.4.3).
Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т.е. изменять исходный граф без выхода из программы. Предусмотреть также возможность изменения количества вершин.
При выполнении работы разрешается (даже рекомендуется!) использовать матрицу бинарных отношений из лабораторной работы №1.
Вход программы: число вершин графа и матрица смежности.
Выход: разбиение множества вершин на подмножества, соответствующие компонентам связности.
Дополнительно:
Заданный граф рассматривать как ориентированный. Выполнять поиск компонент сильной связности.
Описание работы
Программа работает с неориентированным графом. Для поиска компонент связности введем массив состояний вершин графа, в котором будем отмечать уже просмотренные вершины. Если вершина просмотрена, то в соответствующий элемент массива записываем значение True. В основном цикле поиска компонент связности перебираем все вершины по порядку.
Если вершина еще не просмотрена, т.е. пока не вошла ни в какую компоненту связности, то запускаем алгоритм поиска всей компоненты связности, начиная с этой вершины, т.е. поиска компоненты связности, в которую входит эта вершина. Все вершины компоненты связности определяем путем поиска в глубину, используя для этого рекурсию. При этом все вершины, принадлежащие этой компоненте связности, помечаем как просмотренные. После нахождения очередной вершины текущей компоненты связности выводим номер вершины на экран.
Дополнительная информация
2024
зачет
Новожилов
зачет
Новожилов
Похожие материалы
Лабораторная работа №3«Дискретная математика» Поиск компонент связности графа
Anza
: 17 июня 2019
Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа (по материалам главы 3, п. 3.2.3 и 3.4). При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину по материалам п. 3.4.3).
Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т.е
Anza
: 17 июня 2019
60 руб.
Поиск компонент связности графа
ty4ka
: 23 сентября 2020
Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа (по материалам главы 3, п. 3.2.3 и 3.4). При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину по материалам п. 3.4.3).
Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т.
ty4ka
: 23 сентября 2020
200 руб.
Поиск компонент связности графа
ty4ka
: 23 сентября 2020
Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа (по материалам главы 3, п. 3.2.3 и 3.4). При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину по материалам п. 3.4.3).
Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т.е
ty4ka
: 23 сентября 2020
200 руб.
Дискретная математика. Лабораторная работа № 5. Поиск компонент связности графа
nik200511
: 2 июля 2013
Постановка задачи, описание входных данных программы и ее результатов
Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа. При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину).
Пользователю должна быть предоставлена возможность редактировать исходную матри
nik200511
: 2 июля 2013
23 руб.
Дискретная математика. Лабораторная работа № 5. Поиск компонент связности графа
РешуВашуРаботу
: 7 марта 2012
Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа (по материалам главы 3, п. 3.2.3 и 3.4). При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину по материалам п. 3.4.3).
Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т
РешуВашуРаботу
: 7 марта 2012
350 руб.
Лабораторная работа № 5 по дисциплине: Дискретная математика. Поиск компонент связности графа
zhekaersh
: 4 марта 2012
Описание программы
После запуска программы, на экран выводится меню с выбором действий:
1 – Задать порядок графа
2 – Добавить ребра
3 – Удалить ребра
4 – Поиск компонент связности
5 – Выход
Выбрав первый пункт меню, необходимо ввести количество вершин графа (от 1 до 20), если оно уже было задано, то произойдет добавление новых, либо удаление уже имеющихся вершин. Во втором и третьем пунктах меню программы происходит добавление/удаление ребер графа путем указания смежных вершин, при этом учи
zhekaersh
: 4 марта 2012
100 руб.
Лабораторная работа №5. Поиск компонент связности графа. Дискретная математика; 4 вариант
Norff
: 11 апреля 2020
Задание
Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа (по материалам главы 3, п. 3.2.3 и 3.4). При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину по материалам п. 3.4.3).
Пользователю должна быть предоставлена возможность редактировать исходную матр
Norff
: 11 апреля 2020
30 руб.
Лабораторная работа №5 по дисциплине: Дискретная математика Поиск компонент связности графа (общий вариант)
Учеба "Под ключ"
: 1 октября 2016
Задание
Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа (по материалам главы 3, п. 3.2.3 и 3.4). При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности.
Выбор алгоритма поиска компонент связности – произвольный. Например, приветствуется использование одного из видов обхода (поиск в глубину или поиск в ширину по материалам п. 3.4.3).
Пользователю должна быть предоставлена возможность редактировать исходную мат
Учеба "Под ключ"
: 1 октября 2016
250 руб.
Другие работы
Гидромеханика ПетрГУ 2014 Задача 5 Вариант 46
Z24
: 9 марта 2026
Определить направление движения реальной жидкости и вид местного сопротивления в наклонном трубопроводе при следующих исходных данных для сечений 1-1 и 2-2: геометрические высоты сечений z1, z2; манометрические давления р1, р2; диаметры трубопровода d1 = 200 мм, d2 = 120 мм; расход жидкости Q, кинематический коэффициент вязкости жидкости ν = 10⸱10-6 м²/с, которому соответствует жидкость с плотностью ρ = 850 кг/м³.
Z24
: 9 марта 2026
200 руб.
Эволюция религии в контексте глобализации
Elfa254
: 7 января 2014
Рубеж XX-XXI вв. стал временем активного развития процесса глобализации. В современном мире можно наблюдать формирование единой экономической, политической и социальной системы. Вслед за ними начались изменения и в духовной сфере жизни общества. Процесс глобали - зации затронул мировоззрение людей, культуру, традиции. Вторжение в эту сферу вызвало неоднозначные реакции во всем мире, в котором веками формировались уникальные особенности многочисленных цивилизаций. Наиболее остро проявились пробле
Elfa254
: 7 января 2014
20 руб.
Расчет крана на пневмоходу с высотой подъема максимальной 30 м
Aronitue9
: 12 марта 2012
Пневмоколесные стреловые краны характеризуются мобильностью и большой свободой перемещения по твердым и естественным покрытиям дорог.
Выпускают краны грузоподъемностью 16 - 100 т, ходовая часть которых выполняется в зависимости от грузоподъемности трех и четырехосной на сдвоенных пневматических шинах. Ходовая рама опирается на задние колеса через балансиры, передняя не приводная ось шарнирно соединена с рамой. Механизм передвижения пневмоколесных кранов выполняют:
1)Бездифференциальный.
2)Диф
Aronitue9
: 12 марта 2012
42 руб.
Зачетная работа по дисциплине: Цифровая обработка сигналов. Билет №10
Учеба "Под ключ"
: 6 сентября 2017
Билет №10
1. Этапы расчета ЦФ по аналоговому прототипу.
2. Расчет шумов работы ЦФ.
3. Задача.
Дана
H(Z)=(1+0,7*Z^(-1)+0,8*Z^(-2))/(1-0,6**Z^(-1)+0,9*Z^(-2))
Запрограммировать 1813ВЕ1.
Список использованных источников
Учеба "Под ключ"
: 6 сентября 2017
600 руб.
