Бесплатная библиотека - 1 338 003 изданий в библиотеке

Дискретная математика, Часть III, Теория графов, Зарипова Э.Р., Кокотчикова М.Г., 2013

Книга Дискретная математика, Часть III, Теория графов, Зарипова Э.Р., Кокотчикова М.Г., 2013

Дискретная математика, Часть III, Теория графов, Зарипова Э.Р., Кокотчикова М.Г., 2013.
 
   В пособии излагаются основы теории графов и алгоритмов на графах. Книга является продолжением курса дискретной математики: «Часть I. Комбинаторика» и «Часть II. Математическая логика».
Подготовлено на кафедре «Системы телекоммуникаций». Предназначено для студентов I, II курсов математических и компьютерных специальностей высших учебных заведений.

Построение минимального покрывающего дерева для связного взвешенного графа по алгоритму Прима.
Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году. Алгоритм очень похож на алгоритм Дейкстры. Так же этот алгоритм называется алгоритмом поиска соседа.
Будем считать, что в данном алгоритме букет будет только один, этот букет будет включать в себя вершины дерева. Вводится дополнительное множество E' (на начальном этапе совпадающее с отсортированным множеством ребер Е), из которого мы будем удалять рассмотренные ребра.
Оглавление
I. КОНСПЕКТ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ
Тема 1. Графы. Неориентированные графы: основные понятия: маршруты, цепи, циклы: связность: деревья и леса
Тема 2. Ориентированные графы: основные понятия: ориентированные маршруты, пути, контуры: сильная связность. Ориентированные деревья
Тема 3. Метрические характеристики графов. Матричное представление графов: матрица инцидентности для неорграфа. матрица смежности для неорграфа. матрица инцидентности для орграфа, матрица смежности для орграфа. Список смежности
Тема 4. Построение покрывающих деревьев. Алгоритм Краскала. Построение покрывающего дерева для связного графа. Построение минимального покрывающего дерева по алгоритму Краскала. Построение максимального покрывающего дерева по алгоритму Краскала
Тема 5. Построение минимального покрывающего дерева для связного взвешенного графа по алгоритму Прима. Построение максимального покрывающего дерева по алгоритму Прима
Тема 6. Поиск пути наименьшей длины в графе. Алгоритм Дейкстры
Тема 7. Эйлеровы графы. Алгоритм поиска эйлерова цикла в графе
Тема 7. Гамильтоновы графы. Сходство и различия гамильтоновых и эйлеровых графов. Достаточные условия существования гамильтоновых циклов. Способы поиска гамильтонова цикла. Алгоритм поиска гамильтонова цикла в графе
Тема 9. Поиск расстояния между всеми парами вершин. Алгоритм Уоршалла-Флойда
Тема 10. Задача построения транзитивного замыкания бинарного отношения. Алгоритм построения транзитивного замыкания бинарного отношения
Тема 11. Потоки. Условия существования потока. Увеличивающая цепь. Алгоритм поиска увеличивающей цепи. Увеличение потока вдоль найденной цепи по правилам
Тема 12. Потоки. Поиск максимального потока. Поиск потока минимальной стоимости
Тема 13. Задача почтальона для орграфов. Алгоритм поиска оптимального маршрута почтальона для орграфов
II. ФОНДЫ ОЦЕНОЧНЫХ СРЕДСТВ
1. Словарь (глоссарий) основных терминов и понятий
2. Методические указания для преподавателя, студента, слушателя
3. Сборник задач и упражнений
4. Лабораторный практикум по дисциплине
5. Описание балльно-рейтинговой системы
б. Вопросы для самопроверки и обсуждений по темам
7. Задания для самостоятельной работы по темам
8. Перечень рефератов и/или курсовых работ по темам
9. Тестовые задания по темам (для текущего и промежуточного самоконтроля)
10. Тренинговые задания
11. Перечень вопросов итоговой аттестации по курсу
III. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ
ЛИТЕРАТУРА.

Рейтинг: 4.8 баллов / 2537 оценок
Формат: Книга
Уже скачали: 12753 раз

Похожие Книги

Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!

  • Книга Баллады о Ричарде Длинные Руки

    Баллады о Ричарде Длинные Руки

    Название: Баллады о Ричарде Длинные РукиАвтор: Гай Юлий ОрловскийСерия или выпуск: Баллады о Ричарде Длинные РукиИздательство: ЭксмоISBN: 978-5-699-45922-3Год издания: 2010Страниц: 480Язык: РусскийФ . . .

  • Книга АЗБУКА МОРЗЕ

    АЗБУКА МОРЗЕ

    Азбука Морзе Хотите почувствовать себя в роли радиста или просто увлекаетесь азбукой Морзе , тогда эта программа должна привлечь Ваше внимение, она эмулирует терминал для передачи сигналов с помощью . . .

  • Книга Elite Series 34: Afrikakorps 1941-43

    Elite Series 34: Afrikakorps 1941-43

    Название: Elite Series 34: Afrikakorps 1941-43Автор: Gordon Williamson, Ronald VolstadИздательство: Osprey PublishingISBN: 1855321300Год издания: 1998Страниц: 67Язык: АнглийскийФормат: pdfКачество: . . .

  • Книга Campaign 26: Vicksburg 1863. Grant clears the Mississippi

    Campaign 26: Vicksburg 1863. Grant clears the Mississippi

    Название: Campaign 26: Vicksburg 1863. Grant clears the MississippiАвтор: Alan HankinsonИздательство: Osprey PublishingISBN: 1855323532Год издания: 1993Страниц: 97Язык: АнглийскийФормат: pdfКачество . . .

  • Книга Курс практической психологии, или Как научиться работать и добиваться успеха

    Курс практической психологии, или Как научиться работать и добиваться успеха

    Название: Курс практической психологии, или Как научиться работать и добиваться успехаАвтор: Кашапов Р. Р.Серия или выпуск: Практическая психологияИздательство: ACT-ПрессISBN: 978-5-462-00624-1Год и . . .

  • Журнал Радио №12 (декабрь 2010)

    Радио №12 (декабрь 2010)

    Название: Радио №12 (декабрь 2010)Автор: РадиоГод издания: 2010Страниц: 68Язык: РусскийФормат: DjVuКачество: хорошееРазмер: 7,7 МбОписание: «Радио» - ежемесячный научно-технический журнал для радиолю . . .

  • Книга Темная сторона медали

    Темная сторона медали

    Название: Темная сторона медалиАвтор: Сергей МусанифФормат: DOCРазмер: 1,51 мбКачество: ОтличноеЯзык: РусскийГод издания: 2006Содержание:Легко быть героем, когда в твой успех верят миллионы людей, вол . . .

  • Книга Мировая \"холодная война\"

    Мировая \"холодная война\"

    Автор:Анатолий УткинНазвание: Мировая \"холодная война\"Издательство: Алгоритм, ЭксмоГод: 2005Формат: rtf Размер: 6,35 мбС точки зрения западного мира, Россия была хороша, сражаясь против Германии в ф . . .

  • Книга Радзинский Эдвард - Иоанн Мучитель(Аудиокнига)

    Радзинский Эдвард - Иоанн Мучитель(Аудиокнига)

    Описание: "Иоанн Мучитель" повествует о невыносимо долгих для Руси годах правления первого русского царя, которого потомки будут называть Иваном Грозным, а современники - Иоанном Мучителем. Он очень . . .

  • Аудиокнига Спрэг де Камп Лайон, Прэтт Флетчер - Ревущая труба (аудиокнига)

    Спрэг де Камп Лайон, Прэтт Флетчер - Ревущая труба (аудиокнига)

    Созданный Л. Спрэгом де Кампом и Флетчером Прэттом образ мага-самоучки Гарольда Ши принес им всемирную известность. Роман "Ревущая труба" и его продолжения, посвященные приключениям этого героя, откры . . .

Вы не зарегистрированы!

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

Войти Регистрация

Отзывы читателей

Ой!

К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Дискретная математика, Часть III, Теория графов, Зарипова Э.Р., Кокотчикова М.Г., 2013. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.