Методические указания по дисциплине «Теория вероятностей и математическая статистика» к проведению самостоятельной работы

Автор публикации:

Дата публикации:

Краткое описание: ...


ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Дисциплина «Теория вероятностей и математическая статистика» является общепрофессиональной дисциплиной, формирующей базовый уровень знаний для освоения специальных дисциплин. Преподавание дисциплины имеет практическую направленность.

1.1. Программа учебной дисциплины является частью основной профессиональной образовательной программы по специальностям СПО 230115 «Программирование в компьютерных системах».


1.2. Место учебной дисциплины в структуре основной профессиональной образовательной программы: Математический и общий естественнонаучный цикл


1.3. Цели и задачи учебной дисциплины – требования к результатам освоения учебной дисциплины:


В результате освоения учебной дисциплины обучающийся должен уметь:


Применять стандартные методы и модели к решению вероятностных и статистических задач;

Пользоваться расчетными формулами, таблицами, графиками при решении статистических задач;

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

ОК-1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.

ОК-2. Организовывать собственную деятельность, определять методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.

ОК-3. Решать проблемы, оценивать риски и принимать решения в нестандартных ситуациях.

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

ОК-5. Использовать информационно-коммуникационные технологии для совершенствования профессиональной деятельности.

ОК-6. Работать в коллективе и команде, обеспечивать ее сплочение, эффективно общаться с коллегами, руководством, потребителями.

ОК-7. Ставить цели, мотивировать деятельность подчиненных, организовывать и контролировать их работу с принятием на себя ответственности за результат выполнения заданий.

ОК-8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознано планировать повышение квалификации.

ОК-9. Быть готовым к смене технологий в профессиональной деятельности.

ОК-10. Исполнять воинскую обязанность, в том числе с применением полученных профессиональных знаний (для юношей).

В результате освоения учебной дисциплины обучающийся должен знать:

Основные понятия комбинаторики;

Основы теории вероятностей и математической статистики;

Основные понятия теории графов.


ПК-1.1. Выполнять разработку спецификаций отдельных компонент.

ПК-1.2. Осуществлять разработку кода программного продукта на основе готовых спецификаций на уровне модуля.

ПК-2.4. Реализовывать методы и технологии защиты информации в базах данных.

ПК-3.4. Осуществлять разработку тестовых наборов и тестовых сценариев.


В рабочей программе учебной дисциплины предусмотрена самостоятельная внеаудиторная работа с целью:

  • систематизации и закрепления, полученных теоретических знаний и практических умений;

  • углубления и расширения теоретических знаний;

  • формирования умений использовать специальную литературу;

  • развития познавательных способностей и активности студентов;

  • творческой инициативы, самостоятельности, ответственности и организованности;

  • формирования самостоятельности мышления, способностей к саморазвитию, самосовершенствованию и самореализации;

  • развития исследовательских умений.

Согласно учебному плану данная дисциплина проводится в 4 и 5 семестрах. По итогам изученной дисциплины сдается экзамен. На изучение данной дисциплины отводится 120 часов, из которых на самостоятельную внеаудиторную работу отводится 40 часов.

Самостоятельная внеаудиторная работа для студентов проводится в виде заданий:

  • для овладения знаниями:

  • чтение текста и выписки из текста (учебника, дополнительной литературы);

  • учебно-исследовательская работа;

  • для закрепления и систематизации знаний:

  • работа с конспектом лекции (обработка текста);

  • для формирования умений:

  • решение задач.

Перечень заданий к самостоятельной внеаудиторной работе.

Раздел 1. Основные понятия комбинаторики (2 часа)

Раздел 2. Основы теории вероятностей и математической статистики (10 часов).

Раздел 3. ДИСКРЕТНЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ (ДСВ) (8 часов).

Раздел 4. НЕПРЕРЫВНЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ (НСВ) (6 часов)

Раздел 6. Выборочный метод. Статистические оценки параметров распределения (6 часов).

Раздел 7. Основные понятия теории графов (8 часа).

Итого 40 часов.


Раздел 1. Основные понятия комбинаторики (2 часа)

Тема 1.2. Основные теоремы комбинаторики.

Самостоятельная работа студента. Расчет количества выборок заданного типа в заданных условиях.



Задание: изучить теоретический материал по данной теме и решить следующие задачи.

Цель: выработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Данные методические указания, в котором представлены некоторые теоретические вопросы, рассмотрены примеры решения задач.

  2. Кочетков Е. С., Смерчинская С. О., Соколов В. В. Теория вероятностей и математическая статистика: учебник/ Е. С. Кочетков, С. О. Смерчинская, В. В. Соколов., М: Форум: ИФРА-М, 2006. – 240 с.

Алгоритм действий:

  1. Прочитать лекционный материал, записать теоретические вопросы из данного пособия.

  2. Рассмотреть примеры решения задач в данном пособии, записать их.

  3. Самостоятельно решить предложенные задачи.

  4. Оформить решения задач в соответствии с примерами.

Теоретические сведения.

Размещением с повторениями из n элементов по m или упорядоченной (n, m) – выборкой с возвращениями называется любой кортеж (a 1 , a 2 , …, a m ) элементов множества М, для которого [pic]

Поскольку в кортеж (a 1 , a 2 , …, a m ) на каждое место может претендовать любой из n элементов множества М, число размещений с повторениями Р(n, m)=n*n*….*n= n m

Р (n, m)= n m

Определим отношение эквивалентности на множестве размещений с повторениями из n элементов по m: (a 1 , a 2 , …, a m ) ~ ( b 1 , b 2 , ….., b m ) ⇔ для любого с [pic] число элементов a i , равных с, совпадает с числом элементов b i , равных с.

Сочетанием с повторениями из n элементов по m или неупорядоченной (n, m) – выборкой с возвращениями называется любой класс эквивалентности по отношению ~ множества размещений с повторениями из n элементов по m. Другими словами, сочетания с повторениями суть множества М, причем один и тот же элемент допускается выбирать повторно.

Число сочетаний с повторениями из n элементов по m обозначается через C(n, m) и вычисляется по формуле:

[pic]

Пусть М – множество мощности n, [pic] - разбиение множества М на k подмножеств, [pic] Кортеж (М 1 ,…, М к ) называется упорядоченным разбиением множества М.

Число разбиений R(m 1 , m 2 ) вычисляется по формуле:

[pic]

В общем случае число R(m 1 , m 2 , ….m k ) упорядоченных разбиений ( М 1 , М 2 , ….М к ), для которых [pic] , равно [pic] , а число R(n, k) упорядоченных на k подмножеств вычисляется по формуле

[pic]

Число [pic]

Примеры решения задач.

Пример №1 Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4?

Решение: P(4, 3)=4 3 = 64. Ответ: 64.

Пример №2

Сколько существует вариантов бросания двух одинаковых кубиков?

Решение: Это число равно числу сочетаний с повторениями из 2 элементов по 6: [pic]

Ответ: 21.

Пример №3 .

В студенческой группе, состоящей из 25 человек, при выборе старосты за выдвинутую кандидатуру проголосовали 12 человек, против – 10, воздержались – 3. Сколькими способами могло быть проведено такое голосование?

Решение: Пусть М – множество студентов в группе, М 1 – множество студентов, проголосовавших за данную кандидатуру, М 2 – множество студентов, проголосовавших против, М 3 – множество студентов, воздержавшихся от голосования. Тогда [pic] ( M 1 , M 2 , M 3 ) – упорядоченное разбиение множества М. искомое число R(12, 10, 3) = [pic] .

Ответ: [pic] .

Пример №4.

Сколькими способами из группы в 25 человек можно составить 5 коалиций по 5 человек?

Решение: пусть Х – множество людей в группе, m i – число коалиций по i человек, где i – 1,…, 25. Тогда по условиям задачи [pic] / [pic] , и, следовательно, искомое число будет равно [pic]

Задачи для самостоятельного решения:

  1. Крокодил имеет 68 зубов. Доказать, что среди 16 17 крокодилов может не оказаться двух с одним и тем же набором зубов.

  2. Сколькими способами можно расставить белые фигуры на первой линии шахматной доски?

  3. Сколько существует вариантов, чтобы из букв слова «студент» составить всевозможные кортежи длиной 5?

  4. Сколько существует различных шестизначных телефонных номеров?

  5. Сколько нужно провести матчей в групповом этапе финала Кубка мира по футболу, если существует 32 команды, разбитые на 8 групп?

Критерии оценки:

  • «5» - если решено 5 задач.

  • «4» - если решено 4 задачи

  • «3» - если решено 3 задачи.

  • «2» - если решено 2 задачи.


Раздел 2. Основы теории вероятностей и математической статистики (10 часов).

Тема 2.1. Случайные события. Виды случайных событий.
Самостоятельная работа студента. Вычисление вероятностей событий по классической формуле определения вероятности.
Задание: изучить теоретический материал по данной теме и решить следующие задачи.
Цель: выработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Кочетков Е. С., Смерчинская С. О., Соколов В. В. Теория вероятностей и математическая статистика: учебник/ Е. С. Кочетков, С. О. Смерчинская, В. В. Соколов., М: Форум: ИФРА-М, 2006. 240 с.

  2. лекционный материал.

Алгоритм действий:

  1. Прочитать лекционный материал (лекции №5-9).

  2. Рассмотреть примеры решения задач в лекции.

  3. Самостоятельно решить предложенные задачи.

  4. Оформить решения задач в соответствии с примерами в лекции.

Задачи для самостоятельного решения:

  1. В учебнике №1 решить задачи №2.9-2.12 на странице 28.

  2. В учебнике №1 решить задачи №2.20.на странице 30.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 5-6 заданий.

  • «3» - если выполнены 4 задания.

  • «2» - если выполнено менее 4 заданий.


Тема 2.4. Полная вероятность.

Самостоятельная работа студента. Нахождение условных вероятностей.

Вычисление вероятностей сложных событий с помощью теорем умножения и сложения вероятностей.

Задание: изучить теоретический материал по данной теме и решить следующие задачи.

Цель: выработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Кочетков Е. С., Смерчинская С. О., Соколов В. В. Теория вероятностей и математическая статистика: учебник/ Е. С. Кочетков, С. О. Смерчинская, В. В. Соколов., М: Форум: ИФРА-М, 2006. 240 с.

Алгоритм действий:

  1. Прочитать лекционный материал .

  2. Рассмотреть примеры решения задач в лекции.

  3. Самостоятельно решить предложенные задачи.

  4. Оформить решения задач в соответствии с примерами в лекции.

Задачи для самостоятельного решения:

  1. В учебнике №1 решить задачи №2.22, 2.25,2.26 на страницах 30-31.

  2. В учебнике №1 решить задачи №2.22, 2.25,2.26 на страницах 30-31.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 3 задания.

  • «3» - если выполнены 2 задания.

  • «2» - если выполнено менее 2 заданий.


Тема 2.4. Полная вероятность

Самостоятельная работа студента. Нахождение условных вероятностей.

Вычисление вероятностей сложных событий с помощью теорем умножения и сложения вероятностей.

Вычисление вероятностей сложных событий с помощью формулы полной вероятности и формулы Байеса.

Задание: изучить теоретический материал по данной теме и решить следующие задачи.

Цель: выработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Кочетков Е. С., Смерчинская С. О., Соколов В. В. Теория вероятностей и математическая статистика: учебник/ Е. С. Кочетков, С. О. Смерчинская, В. В. Соколов., М: Форум: ИФРА-М, 2006. 240 с.

Алгоритм действий:

  1. Прочитать лекционный материал.

  2. Рассмотреть примеры решения задач в лекции.

  3. Самостоятельно решить предложенные задачи.

  4. Оформить решения задач в соответствии с примерами в лекции.

Задачи для самостоятельного решения:

  1. В учебнике №1 решить задачи №2.42-2.45 на странице 39.

  2. В учебнике №1 решить задачи №2.34, 2.38.

  3. В учебнике №1 решить задачи №4.32, 4.34, 4.36 нс странице №65-66.

  4. В учебнике №1 решить задачи №5.4, 5.6, 5.105.21 на странице 80-83.


Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 5-6 заданий.

  • «3» - если выполнены 4 задания.

  • «2» - если выполнено менее 4 заданий.



Тема 2.5. Схема Бернулли.

Самостоятельная работа студента. Вычисление вероятностей событий с помощью формулы Бернулли.

Задание: изучить теоретический материал по данной теме и решить следующие задачи.

Цель: выработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Гмурман В.Е. Практические занятия по теории вероятностей и математической статистике - М., 2007..

  2. лекционный материал.

Алгоритм действий:

  1. Прочитать лекционный материал.

  2. Рассмотреть примеры решения задач в лекции.

  3. Самостоятельно решить предложенные задачи.

  4. Оформить решения задач в соответствии с примерами в лекции.

Задачи для самостоятельного решения:

  1. В учебнике №1 решить задачи №114-118 на странице 38-39.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 4 задания.

  • «3» - если выполнены 3 задания.

  • «2» - если выполнено менее 3 заданий.



Тема 2.5. Схема Бернулли.

Самостоятельная работа студента. Вычисление вероятностей событий с помощью локальной и интегральной формул Муавра-Лапласа.


Задание: изучить теоретический материал по данной теме и решить следующие задачи.

Цель: выработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Гмурман В.Е. Практические занятия по теории вероятностей и математической статистике - М., 2007.397с.

Алгоритм действий:

  1. Прочитать лекционный материал.

  2. Рассмотреть примеры решения задач в лекции.

  3. Самостоятельно решить предложенные задачи.

  4. Оформить решения задач в соответствии с примерами в лекции.

Задачи для самостоятельного решения:

  1. В учебнике №1 решить задачи №122, 123,126,127,128 на странице 40-42.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 4 задания.

  • «3» - если выполнены 3 задания.

  • «2» - если выполнено менее 3 заданий.



Тема 2.5. Схема Бернулли.

Самостоятельная работа студента. Подготовиться к контрольному тестированию по разделам 1, 2.
Вопросы

  1. Определение случайного события. Операции над случайными событиями. Несовместные события. Полная группа событий.

  2. Определения вероятности (классическое, статистическое, геометрическое). Свойства вероятности.

  3. Гипергеометрическая формула. Условная вероятность, зависимые события.

  4. Независимые события, формулы для вероятностей объединения и пересечения независимых событий. Независимость в совокупности.

  5. Формулы полной вероятности и Байеса.

  6. Схема независимых испытаний, формула Бернулли

  7. Формула Пуассона.

  8. Локальная формула Муавра-Лапласа.

  9. Функция Лапласа, ее свойства. Интегральная формула Муавра-Лапласа.

  10. Следствия из интегральной формулы Муавра-Лапласа (отклонение относительной частоты появления события от его вероятности, закон больших чисел).



Раздел 3. ДИСКРЕТНЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ (ДСВ) (8 часа).

Тема 3.1. Понятие ДСВ. Распределение ДСВ. Функции от ДСВ.

Самостоятельная работа студента. Запись распределения ДСВ, заданной содержательным образом. Запись распределения функции от одной ДСВ и функции от двух независимых ДСВ.

Задание: изучить теоретический материал по данной теме и решить предложенные задачи.

Цель: отработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. / В. Е. Гмурман.- М.: Высшая школа, 2005. 479 с.

Алгоритм действий:

  1. Записать примеры решения задач №164, 170, 172 на странице 52-54.

  2. Решить самостоятельно следующие задачи 167, 168, 169.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 4 задания.

  • «3» - если выполнены 3 задания.

  • «2» - если выполнено менее 3 заданий.


Тема 3.1. Понятие ДСВ. Распределение ДСВ. Функции от ДСВ.

Самостоятельная работа студента. Изучение понятия биномиального распределения и понятия геометрического распределения.

В учебнике записать вопросы теории, решить задачи.

Задание: решить предложенные задачи.

Цель: отработать умения решать задачи по данной теме.

Рекомендуемая литература:

1.Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. / В. Е. Гмурман.- М.: Высшая школа, 2005. 479 с.

Алгоритм действий:

  1. Записать примеры решения задач №176, 179, 172 на странице 56-59.

  2. Решить самостоятельно следующие задачи 175, 180, 181.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 4 задания.

  • «3» - если выполнены 3 задания.

  • «2» - если выполнено менее 3 заданий.





Тема 3.2. Характеристики ДСВ и их свойства

- математическое ожидание ДСВ

- дисперсия и среднее квадратическое отклонение ДСВ.

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

Задание: решить предложенные задачи.

Цель: отработать умения решать задачи по данной теме.

Рекомендуемая литература:

1.Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. / В. Е. Гмурман.- М.: Высшая школа, 2005. 479 с.

Алгоритм действий:

  1. Записать примеры решения задач №188, 189, 192 на странице 64.

  2. Решить самостоятельно следующие задачи 190, 191, 193.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 4 задания.

  • «3» - если выполнены 3 задания.

  • «2» - если выполнено менее 3 заданий.


Тема 3.2. Характеристики ДСВ и их свойства

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

Задание: решить предложенные задачи.

Цель: отработать умения решать задачи по данной теме.

Рекомендуемая литература:

1.Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. / В. Е. Гмурман.- М.: Высшая школа, 2005. 479 с.

Алгоритм действий:

  1. Записать примеры решения задач №195, 196, 197 на странице 67-68.

  2. Решить самостоятельно следующие задачи 198, 200, 201, 193.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 4 задания.

  • «3» - если выполнены 3 задания.

  • «2» - если выполнено менее 3 заданий.









Раздел 4. НЕПРЕРЫВНЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ (НСВ) (6 часов)

Тема 4.1. Понятие НСВ. Равномерно распределенная НСВ. Геометрическое определение вероятности.

Самостоятельная работа студента. Вычисление вероятностей для равномерно распределенной НСВ и для случайной точки, равномерно распределенной в плоской фигуре. Вычисление вероятностей для простейших функций от двух независимых равномерно-распределенных величин X и Y методом перехода к точке M(X,Y) в соответствующем прямоугольнике


Задание: обобщить теоретический материал по данной теме и решить предложенные задачи.

Цель: выработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. / В. Е. Гмурман.- М.: Высшая школа, 2005. 479 с.

Алгоритм действий:

  1. Записать примеры решения задач №275, 277, 280 на странице 97-98.

  2. Решить самостоятельно следующие задачи 276, 278, 279 на странице 97-98.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 4 задания.

  • «3» - если выполнены 3 задания.

  • «2» - если выполнено менее 3 заданий.


Тема 4.3. Нормальное распределение. Показательное распределение. Самостоятельная работа студента. Подготовиться к контрольному тестированию по разделам 3, 4.

Раздел 6. Выборочный метод. Статистические оценки параметров распределения (6 часов).

Тема 6.1. Выборочный метод.

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

Задание: обобщить теоретический материал по данной теме и решить предложенные задачи.

Цель: выработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. / В. Е. Гмурман.- М.: Высшая школа, 2005. 479 с.

Алгоритм действий:

  1. Записать примеры решения задач №439, 441, 443на странице 151-153.

  2. Решить самостоятельно следующие задачи 440, 442, 444 на странице 150-153.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 4 задания.

  • «3» - если выполнены 3 задания.

  • «2» - если выполнено менее 3 заданий.


Тема 6.3. Интервальные оценки параметров распределения.

Самостоятельная работа студента. Интервальное оценивание математического ожидания нормального распределения при известной дисперсии. Интервальное оценивание математического ожидания нормального распределения при неизвестной дисперсии.

Задание: обобщить теоретический материал по данной теме и решить предложенные задачи.

Цель: выработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. / В. Е. Гмурман.- М.: Высшая школа, 2005. 479 с.

Алгоритм действий:

  1. Записать примеры решения задач №450, 452, на странице 157-158.

  2. Решить самостоятельно следующие задачи 454, 456, 458 на странице 159-160.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 2 задания.

  • «3» - если выполнены 1 заданиe.

  • «2» - если выполнено менее 1 задания.


Тема 6.3. Интервальные оценки параметров распределения.

Самостоятельная работа студента. Интервальное оценивание математического ожидания нормального распределения при неизвестной дисперсии.

Интервальное оценивание вероятности события.


Задание: обобщить теоретический материал по данной теме и решить предложенные задачи.

Цель: выработать умения решать задачи по данной теме.

Рекомендуемая литература:

  1. Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. / В. Е. Гмурман.- М.: Высшая школа, 2005. 479 с.

Алгоритм действий:

  1. Записать примеры решения задач № 501, 506, на странице 174-176

  2. Решить самостоятельно следующие задачи 502, 503, 504, 505,507 на странице 174-176.

Критерии оценки:

  • «5» - если выполнены все задания.

  • «4» - если выполнены 4 задания.

  • «3» - если выполнены 3 задания.

  • «2» - если выполнено менее 3 заданий.


Раздел 7. Основные понятия теории графов (8 часов).

Тема 7.1. Неориентированные графы.

Самостоятельная работа студента. Проверить граф на двудольность. Эйлеровы графы. Методика нахождения эйлерова цикла в эйлеровом графе

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

Рекомендуемая литература:

  1. Спирина М. С., Спирин П.А. Дискретная математика. М.: Академия. 2013. 340с..

Задание:

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

Требование к программе:

  1. С клавиатуры вводится матрица смежности графа. (количество вершин графа вводится дополнительно).

  2. С клавиатуры вводится номер вершины.

  3. На экран выводится степень данной вершины.

Примечание: так как граф неориентированный, то матрица смежности должна быть симметричной относительно главной диагонали. Поэтому предусмотреть ввод элементов только выше главной диагонали. Элементы ниже главной диагонали должны заполняться автоматически.

Контрольные вопросы:

  1. Дайте определение графа.

  2. Перечислите способы задания графа. Какой способ наиболее экономичный?

  3. Дайте определение степени вершин

  4. Сформулируйте теорему о сумме степеней вершин графа.

Ответы на контрольные вопросы предоставить в письменном виде в отдельной тетради.

В тетради должно быть записано:

  1. Число.

  2. Тема лабораторной работы.

  3. Задания.

  4. Блок схема алгоритма. Математическая модель. Текст программы.

  5. Ответы на вопросы.

Критерии оценки:

Оценка «5» - ставится, если студент выполнил задачу, и ответил на все контрольные вопросы.

Оценка «4» - ставится, если студент верно выполнил задачу, но алгоритм нерационален.

Оценка «3» ставится, если студент решил задачу с одной ошибкой и верно ответил на контрольные вопросы.

Оценка «2» ставится, если студент не решил задачу или ответил только на контрольные вопросы.


Тема 7.2. Ориентированные графы.

Самостоятельная работа студента. Построение графов по заданным характеристикам. Определение характеристик графов

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

Рекомендуемая литература:

  1. Спирина М. С., Спирин П.А. Дискретная математика. М.: Академия. 2013. 340с..

Задание: Написать программу: Нахождение кратчайших путей. Алгоритм Дейкстры

Нахождение кратчайших путей. Алгоритм Дейкстры

Для начала рассмотрим алгоритм Фалкерсона (графический способ упорядочивания элементов):

1. Найти вершины графа, в которые не входит не одна дуга. Они образуют первую группу. Пронумеровать вершины группы в произвольном порядке.

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

Теперь рассмотрим алгоритм нахождения кратчайшего пути между двумя заданными вершинами в ориентированном графе. Пусть G = {S, U, Ω } – ориентированный граф со взвешенными дугами. Обозначим s-вершину – начало пути и t-вершину - конец пути.

Алгоритм Дейкстры содержит одно ограничение - веса дуг должны быть положительными. Сам алгоритм состоит из двух этапов. На первом находится длина кратчайшего пути, на втором строится сам путь от вершины s к вершине t.

Этап 1. Нахождение кратчайшего пути.

Шаг 1. Присвоение вершинам начальных меток.

Полагаем d(s)=0* и считаем эту метку постоянной (постоянные метки помечаются сверху звёздочкой). Для остальных вершин xi [pic] S, xi ≠s полагаем d(xi) = ∞ и считаем эти метки верными. Пусть x” = s, x” – обозначение текущей вершины.

Шаг 2. Изменение меток.

Для каждой вершины xi с временной меткой, непосредственно следующей за вершиной x”, меняем ее метку в соответствии со следующим правилом: dнов.(xi) = min{dстар.(xi), d(x”)+ω(x”, xi)}.(1. 6. 1)

Шаг 3. Превращение метки из временной в постоянную.

Из всех вершин с временными метками выбираем вершину xj* с наименьшим значением метки

d(xj*) = min {d(xj) / xj [pic] S, d(xj) – временная}. (1. 6. 2)

Превращаем эту метку в постоянную и полагаем x” = xj*.

Шаг 4. Проверка на завершение первого этапа.

Если x” = t, то d(x”) – длина кратчайшего пути от s до t. В противном случае происходит возвращение ко второму шагу.

Этап 2. Построение кратчайшего пути.

Шаг 5. Последовательный поиск дуг кратчайшего пути.

Среди вершин, непосредственно предшествующих вершине x” c постоянными метками, находим вершину xi, удовлетворяющую соотношению d(x”) = d(xi) + ω(xi, x”).(1. 6. 3)

Включаем дугу (xi, x”) в искомый путь и полагаем x” = xi.

Шаг 6. Проверка на завершение второго этапа.

Если x” = s, то кратчайший путь найден – его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае возвращаемся к пятому шагу.

Пример 8: Задана весовая матрица Ω графа G. Найти минимальный путь из вершины x1 в вершину x6 по алгоритму Дейкстры.


[pic] [pic]

Рис. 1


На рисунке 1. изображён сам граф по данной матрице весов. Поскольку на данном графе есть цикл между вершинами x2, x3 и x5, то вершины графа нельзя упорядочить по алгоритму Фалкерсона. На рисунке графа временные и постоянные метки указаны над соответствующей вершиной. Итак, распишем подробно работу алгоритма Дейкстры по шагам.

Этап 1.

Шаг 1. Полагаем d(x1) = 0*, x” = x1, d(x2) = d(x3) = d(x4) = d(x5) = d(x6) = ∞.

1-ая итерация.

Шаг 2. Множество вершин, непосредственно следующих за x” = x1 со временными метками S” = {x2, x4, x5}. Пересчитываем временные метки вершин: d(x2) = min{∞, 0*, + 9} = 9, d(x4) = min{∞, 0* + 6} = 6, d(x5) = min{∞, 0* + 11} = 11.

Шаг 3. Одна из временных меток превращается в постоянную min{9, ∞, 6, 11, ∞} = 6* = d(x4), x” = x4.

Шаг 4. x” = x4 ≠ t = x6, происходит возвращение на второй шаг.

2-ая итерация.

Шаг 2. S” = {x2, x3, x5}, d(x2) = min{9, 6* + 5} = 9, d(x3) = min {∞, 6* + 7} = 13, d(x5) = min{11, 6* + 6} = 11.

Шаг 3. min{d(x2), d(x3), d(x5), d(x6)} = min{9, 13, 11, ∞} = 9* = d(x2), x” = x2.

Шаг 4. x2 ≠ x6, возвращение на второй шаг.

3-я итерация.

Шаг 2. S” ={x3}, d(x3) = min{13, 9* + 8} = 13.

Шаг 3. min{d(x3), d(x5), d(x6)} = min{31, 11, ∞} = 11* = d(x5), x” = x5.

Шаг 4. x5 ≠ x6, возвращение на второй шаг.

4-ая итерация.

Шаг 2. S”={x6}, d(x6) = min{∞, 11* + 4} = 15.

Шаг 3. min {d(x3), d(x6)} = min{13, 15} = 13* = d(x3), x” = x3.

Шаг 4. x3 ≠ x6, возвращение на второй шаг.

5-ая итерация.

Шаг 2. S” = {x6}, d(x6) = min{15, 13* + 9} = 15.

Шаг 3. min{d(x6)} = min{15} = 15*, x” = x6.

Шаг 4. x6 = t = x6, конец первого этапа.

Этап 2.

Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x6 с постоянными метками S” = {x3, x5}. Проверим для этих двух вершин выполнение равенства dнов.(xi) = min{dстар.(xi), d(x”) + ω(x”, xi)}:


d(x”) = 15 = 11* + 4 = d(x5) + ω(x5, x6),

d(x”) = 15 ≠ 13* + 9 = d(x3) + ω(x3, x6).

Включаем дугу (x5, x6) в кратчайший путь. x” = x5.

Шаг 6. x” ≠ s = x1, возвращение на пятый шаг.

2-ая итерация.

Шаг 5. S” = {x1, x4}.

d(x”) = 11 = 0* + 11 = d(x1) + ω(x1, x5),

d(x”) = 11 ≠ 6* + 6 = d(x4) + ω(x4, x5).

Включаем дугу (x1, x5) в кратчайший путь. x” = x1.

Шаг 6. x” = s = x1, завершение второго этапа.

Итак, кратчайший путь от вершины x1 до вершины x6 построен. Его длина (вес) равна 15, сам путь образует следующая последовательность дуг: μ = (x1, x5) - (x5, x6).

Критерии оценки:

Оценка «5» - ставится, если студент выполнил задачу.

Оценка «4» - ставится, если студент частично выполнил задачу.

Оценка «3» ставится, если студент выполнил задачу с поправками .

Оценка «2» ставится, если студент не выполнил задание .



Тема 7.2. Ориентированные графы.

Самостоятельная работа студента. Построение графов по заданным характеристикам. Определение характеристик графов

Цель: Отработать навыки написания программы, построение двудольного графа.

Рекомендуемая литература:

  1. Спирина М. С., Спирин П.А. Дискретная математика. М.: Академия. 2013. 340с..

Задание: Написать программу: построение двудольного графа

Графы G1 (V1, E1) и G2 (V2, E2) называются изоморфными, если существует биекция f: V1V2, такая, что выполнено (v1, v2) E (f (v1), f (v2) E2. При этом f называется изоморфизмом графов G1 и G2. Изоморфизм графа G на себя называется автоморфизмом.

Пример 1. Следующие графы имеют только тождественные автоморфмы

Пример 2. Следующий граф имеет, кроме тождественного, автоморфизмы (1,3), (2,4), (13) (24).

Широко известна так называемая проблема изоморфизма графов, в которой для любых двух графов требуется установить, изоморфны они или нет. Для знакомства с результатами по данной проблеме следует обратиться к приведенному списку литературы.

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

Пусть G1 + (V1, E1), G2 = (V2, E2) - два графа.

Объединение графов G1 и G2 есть граф, у которого V = V1 V2,Е = E1 Е2.

Соединение графов G1+G2 есть граф, у которого

V = V1 V2, Е = E1 Е2 { (v1, v2) } для всех v1V1, v2V2

Прямое произведение графов есть граф, у которого V = V1V2, ( (c1,v2), (v1,v2)) E (v1,v1) E и (v2,v2) E2

Пример. Пусть даны графы отображений f1 V1Vi, f2: V2V2. Тогда прямое произведение соответствует отображению

f1 f2: V V2 V1 V2 где f1 f2 (v1,v2) = (f1, (v1), f2 (v2))

Пусть f1 и f2 имеют и начальных вершин соответственно. Тогда f1 f2 будет иметь

Некоторые классы графов допускают характеристическое описание. В качестве примера приведем критерий двудольности графа (Кёниг, 1936 г.)

Теорема. Для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины.

Пусть G = (V, Е) - двудольный граф, С - один из его циклов длины k. Фиксируем вершину v1 С и проходим цикл, начиная с v1. Пусть это вершины v1, v2,., vk. Поскольку концы каждого ребра лежат в разных долях, то k - четное число.

Пусть G = (V, Е) - связный и все его циклы четной длины. Определим разбиение V = V1V2 следующим образом: Фиксируем произвольную вершину v1V и включаем ее в V1. Теперь включаем uV1 d (u, v1) - четное число. Остальные вершины включаем в V2.

Покажем, что граф G двудольный. Пусть, напротив, существует ребро (v', v"), где v', v" V1. Следовательно, d (v1, v'), d (v1, v") - четны. Ребро (v', v") дает цикл нечетной длины, содержащий путь от v1 к v', ребро (v', v"), путь от v" к v1. Аналогично показываем, что нет ребер (v', v"), v', v" V2.

Критерии оценки:

Оценка «5» - ставится, если студент выполнил задачу.

Оценка «4» - ставится, если студент частично выполнил задачу.

Оценка «3» ставится, если студент выполнил задачу с поправками .

Оценка «2» ставится, если студент не выполнил задание .



Тема 7.2. Ориентированные графы.

Самостоятельная работа студента. Построение графов по заданным характеристикам. Определение характеристик графов

Цель: Отработать навыки написания программы, построение графов по заданным характеристикам. Алгоритм нахождения максимального пути

Рекомендуемая литература:

  1. Спирина М. С., Спирин П.А. Дискретная математика. М.: Академия. 2013. 340с..

Задание:Написать программу нахождения максимального пути



Для нахождения максимального пути граф G (сеть) должен быть ациклическим, ибо в противном случае может оказаться, что длины некоторых путей не ограничены сверху. Если Gn – ациклический граф, то для любых двух его вершин xi ≠ xj выполняется одно из двух условий:

1. xi предшествует xj, xi [pic] Sпредш (xj);

2. xi следует за xj, xi [pic] Sслед (xj);

3. нет пути между xi и xj.,

Первое и второе условия одновременно не выполнимы из-за требуемой ацикличности графа.

Перед вычислением максимального пути в орграфе необходимо упорядочить вершины графа по алгоритму Фалкерсона.

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

Пусть dj – длина максимального пути от вершины x1 до вершины xj, тогда величина dj удовлетворяет следующим рекуррентным соотношениям (1.):


[pic]


Соотношения (1.) позволяют легко вычислить длины максимальных путей от s = x1 до вершин, достижимых из вершины s. Сами пути могут быть построены методом последовательного возвращения (второй этап в алгоритме Дейкстры).

Пример 9: Граф (рис. 2) задан матрицей весов Ω. Найти максимального пути из вершины x1 в x6 и сам этот путь.


[pic] [pic]

Рис. 2

Этот граф ациклический, поэтому возможно упорядочение его вершин по алгоритму Фалкерсона. Сделаем это графическим способом (рис. 1.13), переобозначив две вершины: x4 назовём x [pic] , а x3 – x [pic] , и применим рекуррентные формулы (1.)


[pic]

Рис. 3


Этап 1.


d1 = 0,

d2 = max (d1 + 4) = 4,

d [pic] = max (d1 + 6, d2 + 8) = max (0 + 6, 4 + 8) = 12,

d [pic] = max (d [pic] + 8, d2 + 7) = max (12 + 8, 4 + 7) = 20,

d5 = max (d [pic] + 7, d [pic] + 9, d2 + 6) = max (20 + 7, 12 + 9, 4 + 6) = 27,

d6 = max (d5 + 3, d [pic] + 5) = max (27 + 3, 20 + 5) = 30.


Итак, длина максимального пути их x1 в x6 равна 30.

Этап 2.


x6 : d6 = 30 = d5 + 3 = 27 +3 – включаем дугу (x5, x6) в максимальный путь, d6 = 30 ≠ d [pic] + 5 = 20 + 5.

x5 : d5 = 27 ≠ d [pic] + 7 = 20 + 7 – включаем дугу (x [pic] , x5) в максимальный путь,

d5 = 27 ≠ d [pic] + 9 = 12 + 9, d5 = 27 ≠ d2 + 6 = 4 +6.

x [pic] : d [pic] = 20 = d [pic] + 8 = 12 + 8 – включаем дугу (x [pic] , x [pic] ) в максимальны путь,

d [pic] = 20 ≠ d2 + 7 = 4 +7.

x [pic] : d [pic] = 12 = d2 + 8 = 4 + 8 – включаем дугу (x2, x [pic] ) в максимальный путь,

d [pic] = 12 ≠ d1 +6 = 0 + 6.

x2 : d2 = 4 = d1 +4 = 0 + 4 – включаем дугу (x1, x2) в максимальный путь.


Итак, искомый путь таков: μmax=(x1, x2)-(x2, x [pic] )-(x [pic] , x [pic] )-( x [pic] , x5)-(x5, x6) или в первоначальных обозначениях μmax=(x1, x2)-(x2, x4)-(x4, x3)-(x3, x5)-(x5, x6)

Критерии оценки:

Оценка «5» - ставится, если студент выполнил задачу.

Оценка «4» - ставится, если студент частично выполнил задачу.

Оценка «3» ставится, если студент выполнил задачу с поправками .

Оценка «2» ставится, если студент не выполнил задание .



Тема 7.2. Ориентированные графы.

Самостоятельная работа студента. Подготовиться к контрольному тестированию по разделам 5, 6, 7.

Цель: Отработать навыки решения задач

Рекомендуемая литература:

  1. Спирина М. С., Спирин П.А. Дискретная математика. М.: Академия. 2013. 340с..

Задание: Применение способов задания графов.

Задача 1. Для графов, изображённых на рисунке 2.1, составить матрицы смежности вершин, смежности дуг и инциденций.


[pic]

Рис. 2.1


Решение задачи 1.

[pic]


Задача 2: По матрице смежности построить наглядное изображение графа.


[pic]

Решение задачи 2:


[pic]

Рис. 2.2


Задача 3: Показать, что графы изоморфны (Рис. 2. 3).


[pic]

Рис. 2.3


Решение задачи 3: Воспользуемся теоремой и рассмотрим матрицы смежности графов. Заметим, что они равны, следовательно графы являются изоморфными.


[pic]


= А (матрица смежности первого и второго графов)

Задача 4. Доказать, что графы на рисунке 2. 4 не изоморфны.

[pic]


Решение задачи 4: Построим матрицы смежности вершин для данных графов.


[pic]


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

Задача 5: Найти матрицу достижимости С для данного графа


[pic]

Рис. 2.5


Решение задачи 5:

Находим матрицу смежности данного графа (рис. 2.5), Р. Затем находим Р2, Р3 и Р4. Складываем данные матрицы и матрицу Е. Находим матрицу достижимости графа:

[pic]


Задача 6. Найти матрицы сильных компонент связи для графа, изображённого на рисунке 2. 6.


[pic]


Решение задачи 6: Находим матрицу смежности графа, возводим её в степени от 2 до 5. Находим матрицу В, и затем матрицу достижимости и контрдостижимости. Затем, путем перемножения последних двух матриц, получаем матрицу, по которой определяем сильные компоненты связи.


[pic]

По матрице F можно сказать, что граф содержит три сильные компоненты связности. Первая сильная компонента состоит из вершины x1, вторая сильная компонента из вершины x2 и третья – из вершин x3, x4, x5.

Задача 7: Найти матрицы сильных компонент связи для графа, изображённого на рисунке 2. 7.


[pic]

Рис. 2.7


Решение задачи 7: Решение аналогично предыдущему заданию.


[pic]


Задача 8. Найти ранг графа, приведённого на рисунке 2. 8.


[pic]


Решение задачи 8: Ранг графа равен рангу его матрицы смежности. Следовательно, построим матрицу смежности данного графа и найдём её ранг, приводя матрицу к ступенчатому виду.

[pic]


Ранг полученной матрицы смежности равен 5, тогда и rangG = 5.

Задача 9: Определить, имеют ли контуры орграфы с матрицами смежности


[pic]


Решение задачи 9:

а) n = 4,


[pic]


На диагонали присутствуют нулевые элементы, следовательно, граф имеет контур.


[pic]

На диагонали присутствуют ненулевые элементы, следовательно, граф имеет контур.

Задача 10: По заданной матрице весов Ω графа G найти величину минимального пути и сам путь от вершины s = x1 до вершины t = x6 по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами:


[pic]


Решение задачи 10:

Построим граф по данной матрице (Рис. 2. 9).


[pic]


В данном графе нет цикла, поэтому упорядочим его с помощью алгоритма Фалкерсона.

Вершина х1 не содержит входящий дуг, отнесем ее к первой группе. Вычеркнем все дуги, исходящие из х1, получим граф без трёх рёбер (х1 – х2, х1 – х4, х1 – х5). В нём опять находим одну вершину, в которую не заходит ни одна дуга. Это вершина х4 (вторая группа). Вычеркнем дуги, исходящие из вершины х4. получим граф только с четырьмя рёбрами (х2 – х3, х3 – х6, х5 – х3, х5 – х2). Появилась ещё одна вершина х5 (группа 3), в которую не входят рёбра, вычеркнем исходящие из неё дуги. Получим вершину х2, которая входит в группу 4, х3 – в группу 5 и х6 – в группу 6.

Получен упорядоченный граф (Рис. 2. 10):


[pic]

Рис. 2.10


Этап 1.

Шаг 1. Полагаем, что d(x1) = 0*, x” = x1.


d(x2) = d(x3) = d(x4) = d(x5) = d(x6) = ∞.


1-ая итерация

Шаг 2. Множество вершин, непосредственно следующих за х = х1 с временными метками S” = {x2, x4, x5}. Пересчитываем временные метки этих вершин: d(x2) = min{∞, 0*+11} = 11, d(x4) = min{∞, 0*+14} = 14, d(x5) = min{∞, 0*+15} = 15.

Шаг 3. Одна из временных меток превращается в постоянную. min{11, ∞, 14, 15, ∞} = 11* = d(x2), x” = x2.

Шаг 4. x” = x2 ≠ x6, происходит возвращение на второй шаг.

2-ая итерация

Шаг 2. S” = {x3}, d(x3) = min{11, 11*+13} = 11.

Шаг 3. min{11} = 11* = d(x3), x” = x3.

Шаг 4. x3 ≠ x6, происходит возвращение на шаг 2.

3-я иетерация

Шаг 2. S” = {x6}, d(x6) = min{29, 11*+11+14} = 29.

х6=x6, конец первого этапа.

Этап 2.

Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x6 с постоянными метками. S”={x3, x5}. Проверим для этих двух вершин выполнение равенства


d(x”) = d(xi) + ω(xi, x”).

d(x”) = 29 = 15*+14 = d(x5) + ω(x5, x6),

d(x”) = 29 ≠ 23*+14 = d(x3) + ω(x3, x6).


Включаем дугу (x5, x6) в кратчайший путь; x” = x5.

Шаг 6. x” ≠ x1, переходим на шаг 5.

2-ая итерация

Шаг 5. S” = {x1, x4},


d(x”) = 15 = 0*+15 = d(x1) + ω(x1, x5),

d(x”) = 15 ≠ 14+9 = d(x4) + ω(x4, x5).


Включаем дугу (x1, x5) в кратчайший путь. x” = x1.

Шаг 6. x” = x1. Завершение второго этапа.

Итак, кратчайший путь из вершины х1 в х6 построен. Его длина (вес) равна 29. Сам путь образует следующая последовательность дуг: μmin = (х1, х5)-(х5, х6).

Задача 11: Найти величину максимального пути и сам путь между вершинами s = x1 и t = x6 (матрица из задачи 10)

Решение задачи 11:

Этап 1


d1 = 0,

d4 = max{d1+14} = 14

d5 = max{d4+9, d1+15} = max{15, 23} = 23

d2 = max{d1+11, d4+7, d5+11} = max{11, 21, 34} = 34

d3 = max{d2+13, d4+11, d5+10} = max{47, 25, 33} = 47

d6 = max{d3+13, d5+14} = max{60, 37} = 60.


Итак, длина максимального пути из х1 в х6 равна 60.

Этап 2


*x6 : d6 = 60 = x3+13 – включаем дугу (х3, х6) в максимальный путь, d6 = 60 ≠ d5+14=37.

*x3 : d3 = 47 = d2+13 = 34+13 – включаем дугу (x2, x3) в максимальный путь,

d3 = 47 ≠ d4+11 = 25,

d3 = 47 ≠ d5+10=33.

*x2 : d2 = 34 = d5+11 – включаем дугу (х5, х2) в максимальный путь,

d2 = 34 ≠ d1+11,

d2 = 34 ≠ d4+7.

*x5 : d5 = 23 = d1+15 – включаем дугу (x1, x5) в максимальный путь,

d5 = 23 ≠ d4+9.

*x4 : d4 = 14 = d1+14 = 0+14 – включаем дугу (х1, х4) в максимальный путь.


итак, искомый путь таков:μmax = (x1, x4)-(x4, x5)-(x5, x2)-(x2, x3)-(x3, x6)

Задача 12: По заданной матрице весов Ω графа G найти величину минимального пути и сам путь от вершины s = x1 до вершины t = x6 по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами:

[pic]


Решение задачи `12:

Нарисуем граф (Рис. 2.11) по данной матрице, упорядочим его вершины по алгоритму Фалкерсона. Получим граф, изображённый на рисунке 2. 12.


[pic]

Рис. 2.11


[pic]

Рис. 2.12


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

Этап 1

Шаг 1. Полагаем, что d(x1) = 0*, x” = x1.


d(x2) = d(x3) = d(x4) = d(x5) = d(x6) = ∞.


1-ая итерация

Шаг 2. Множество вершин, непосредственно следующих за х = х1 с временными метками S” = {x2, х3}. Пересчитываем временные метки этих вершин: d(x2) = min{∞, 0*+8} = 8, d(x3) = min{∞, 0*+10} = 10.

Шаг 3. Одна из временных меток превращается в постоянную. min{8, ∞, 10} = 8* = d(x2), x” = x2.

Шаг 4. x” = x2 ≠ x6, происходит возвращение на второй шаг.

2-ая итерация

Шаг 2. S” = {x3, х4, х5}, d(x3) = min{10, 8*+10} = 10,

d(x4) = min{∞, 8*+9} = 17, d(x5) = min{∞, 8*+12} = 20.

Шаг 3. min{10, 17, 20} = 10* = d(x3), x” = x3.

Шаг 4. x3 ≠ x6, происходит возвращение на шаг 2.

3-я итерация

Шаг 2. S” = {x4, х5, x6}, d(x4) = min{17, 10*+10} = 17, d(x5) = min{20, 10*+12} = 20, d(x6) = min{∞, 10*+7} = 17.

х6 = х6, конец первого этапа

Этап 2

Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x6 с постоянными метками. S”={x3, x4, х5}. Проверим для этих двух вершин выполнение равенства d(x”) = d(xi) + ω(xi, x”). В итоге включаем дугу (x1, x3) в кратчайший путь, затем таким же образом дугу (х3, х6).

Итак, кратчайший путь из вершины х1 d х6 построен. Его длина (вес) равна 17. Сам путь образует следующая последовательность дуг: μ=(х1, х3)-(х3, х6).

Задача 13: Используя матрицу из задачи 8, построить максимальный путь из вершины х1 в вершину х6.

Решение задачи 13:

Этап 1


d1 = 0,

d2 = max{d1+8} = 8

d3 = max{d1+10, d2+10} = max{10, 18}=18

d4 = max{d2+9, d3+10} = max{17, 28} = 28

d5 = max{d3+12, d4+9, d2+12} = max{30, 37, 20} = 37

d6 = max{d3+7, d4+13, d5+11} = max{25, 41, 48} = 48.


Итак, длина максимального пути из х1 в х6 равна 48.

Этап 2


*x6 : d6 = 48 = d5 + 11 – включаем дугу (х5, х6) в максимальный путь.

*x5 : d5 = 37 = d4+9 – включаем дугу (x4, x5) в максимальный путь,

*x4 : d4 = 28 = d3+10 – включаем дугу (х3, х4) в максимальный путь,

*x3 : d3 = 18 = d2+10 – включаем дугу (x2, x3) в максимальный путь,

*x2 : d2 = 8 = d1+8 – включаем дугу (х1, х2) в максимальный путь.


Итак, искомый путь таков:μmax = (x1, x2)-(x2, x3)-(x3, x4)-(x4, x5)-(x5, x6).

Контрольные вопросы:

  1. Дайте определение графа.

  2. Дать определения дерева.

  3. Дать определение остова.

  4. Дать определение минимального остова.

3. условия реализации УЧЕБНОЙ дисциплины


3.1. Информационное обеспечение обучения

Основные источники:

  1. Спирина М.С. Теория вероятностей и математическая статистика - М., 2013. 351с.

  2. Гмурман В.Е. Теория вероятностей и математическая статистика - М., 2007. 327с.

  3. Гмурман В.Е. Практические занятия по теории вероятностей и математической статистике - М., 2007.378с.

  4. Спирина М. С., Спирин П.А. Дискретная математика. М.: Академия. 2013. 340 с.


Дополнительные источники:

1. Валуцэ И.И. Математика для техникумов. [Текст]: учебное пособие/И.И. Валуцэ, Дилигул Г.Д. – 2-е изд., перераб. и доп. – М.: Наука, 1989. 576 с.: ил.

2. Богомолов Н.В. Практические задания по математике [Текст]: учеб. пособие/Н.В.Богомолов – 7-е изд., стер.-м.: Высш. Шк., 2004 495с.

Дидактические материалы:

  • тесты к урокам

  • поурочное планирование

  • раздаточный материал по темам курса

  • задания к практическим работам

  • тетради учащихся с записями лекций.




28
Читать полностью »