400

Лабораторная работа №1 по дисциплине: Дискретная математика. Вариант №24

ID: 204406
Дата закачки: 06 Ноября 2019
Продавец: IT-STUDHELP (Напишите, если есть вопросы)
    Посмотреть другие работы этого продавца

Тип работы: Работа Лабораторная
Форматы файлов: Microsoft Word
Сдано в учебном заведении: ТУСУР

Описание:
Цель лабораторной работы
Изучить основные понятия, определения и терминологию теории графов, классы графов, способы задания графа, простейшие операции на графах, числовые характеристики графа и способы их вычисления.

Задание 1. По матрицам (рис. 2 и 3) построить диаграммы графов, определив предварительно вид данных матриц.

Задание 2. Методами поиска «в глубину» и «в ширину» найти наибольший минимальный маршрут между вершинами графа (рис. 1).

Задание 3. Для каждой пары вершин графа (рис. 1) аналитическим способом вычислить количество маршрутов длины, равной 4, и выделить те пары вершин, для которых их количество ≥ 3, но не более 10. Выписать эти маршруты для какой-либо из выделенных пар. В описании маршрутов указывать вершины и ребра, входящие в него.

Задание 4. Построить матрицу метрики графа (рис. 1).
Для этого для матрицы связности R найдём S^1=R+E, затем каждый шаг будем получать 〖S^i〗^\'=S^(i-1) S, для всех ячеек, которые являются нулевыми в S^(i-1) и ненулевыми в S^i\' зададим значение i, прочие скопируем из S^(i-1) в S^i. Если S^(i-1)=S^i, то завершаем алгоритм, находя матрицу метрики M, копируя туда все ненулевые ячейки из S^i, а вместо нулевых задавая ∞, m_ii=0.

Задание 5. С помощью алгоритма Магу – Вейсмана выполнить правильную раскраску вершин графа с минимальным количеством цветов.

Задание 6. Определить число вершинного покрытия графа (рис. 1).
На основании
x_1 x_4 x_5 x_8+x_1 x_4 x_5 x_7+x_1 x_3 x_5 x_8+x_1 x_3 x_5 x_7+x_1 x_3 x_5 x_6+x_1 x_5 x_6+x_2 x_4 x_8+x_2 x_4 x_7+x_2 x_8+x_2 x_7+x_6
из предыдущего задания, имеем число вершинного покрытия равным 4.

Задание 7. Определить, содержит ли граф (рис. 1) эйлерову цепь или эйлеров цикл.
Ответ обосновать.

Задание 8. Аналитическим способом определить число компонент связности графа. 9



Комментарии: Помогу с вашим вариантом, другой работой или дисциплиной.
E-mail: sneroy20@gmail.com

Размер файла: 211,8 Кбайт
Фаил: (.docx)
-------------------
Обратите внимание, что преподаватели часто переставляют варианты и меняют исходные данные!
Если вы хотите, чтобы работа точно соответствовала, смотрите исходные данные. Если их нет, обратитесь к продавцу или к нам в тех. поддержку.
Имейте ввиду, что согласно гарантии возврата средств, мы не возвращаем деньги если вариант окажется не тот.
-------------------

Скачать

Добавить в корзину

Занесено в корзину

    Скачано: 6         Коментариев: 1

Есть вопросы? Посмотри часто задаваемые вопросы и ответы на них.
Опять не то? Мы можем помочь сделать!

Некоторые похожие работы:

К сожалению, точных предложений нет. Рекомендуем воспользоваться поиском по базе.