Дискретная математика. Часть III. Теория графов

دسته بندی: نظریه نمودار
ویرایش:  
نویسندگان: Зарипова Э.Р.,  Кокотчикова М.Г.  
سری:  
 
ناشر:  
سال نشر:  
تعداد صفحات: 179 
زبان: Ukrainian 
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 3 مگابایت 

قیمت کتاب (تومان) : 59,000

آموزش. - M .: انتشارات دانشگاه RUDN، 2013. - 179 ص. — شابک 5-209-01493-2 این کتاب در ادامه درس ریاضیات گسسته است: «قسمت اول. ترکیبیات» و «قسمت دوم. منطق ریاضی».
نظریه گراف بخشی از علم ریاضیات گسسته است. ریاضیات گسسته از بخش های زیر تشکیل شده است: ترکیبات، منطق ریاضی، نظریه گراف عمومی، نظریه مجموعه ها و جبر عمومی، نظریه الگوریتم، نظریه خودکار و نظریه کدگذاری.
تهیه شده در گروه سیستم های مخابراتی. در نظر گرفته شده برای دانشجویان دوره های I، II رشته های تخصصی ریاضی و کامپیوتر موسسات آموزش عالی. مطالب. 14 سخنرانی):
نمودار. نمودارهای بدون جهت: مفاهیم اساسی. مسیرها، زنجیره‌ها، چرخه‌ها؛ اتصال؛ درختان و جنگل ها. گراف های جهت دار: مفاهیم اساسی; مسیرها، مسیرها، خطوط جهت دار؛ اتصال قوی درختان جهت دار. ویژگی های متریک نمودارها. نمایش ماتریسی نمودارها: ماتریس بروز برای غیر دیگراف، ماتریس مجاورت برای غیر دیگراف، ماتریس بروز برای دیگراف، ماتریس مجاورت برای دیگراف. فهرست مجاورت. درخت های پوشا را بسازید. الگوریتم کروسکال ساخت یک درخت پوشا برای یک نمودار متصل ساخت یک درخت پوشا حداقل با استفاده از الگوریتم کروسکال. ساخت درخت پوشا حداکثر با استفاده از الگوریتم کروسکال. ساخت یک درخت پوشا حداقل برای یک نمودار وزنی متصل با استفاده از الگوریتم پریم . ساختن یک درخت پوشا حداکثر با استفاده از الگوریتم Prim. پیدا کردن مسیری با کمترین طول در نمودار. الگوریتم دایکسترا. نمودارهای اویلر. الگوریتمی برای یافتن چرخه اویلر در گراف. گراف های همیلتونی. شباهت ها و تفاوت های گراف هامیلتونی و اویلر شرایط کافی برای وجود چرخه های همیلتونی. راه هایی برای جستجوی یک چرخه همیلتونی الگوریتمی برای یافتن یک چرخه همیلتونی در نمودار. پیدا کردن فاصله بین همه جفت رئوس. الگوریتم Warshall-Floyd. مشکل ساختن یک بسته شدن انتقالی یک رابطه باینری. الگوریتم ساخت یک بسته شدن متعدی یک رابطه باینری. جریان ها. شرایط وجود جریان. افزایش زنجیره. الگوریتم جستجوی یک زنجیره افزایشی. جریان را در طول زنجیره پیدا شده طبق قوانین افزایش دهید. جریان ها. یافتن حداکثر جریان یافتن حداقل جریان هزینه. مشکل پستچی برای نمودارها. الگوریتم یافتن مسیر بهینه پستچی برای نمودارها. وجوه ارزیابی.
فرهنگ لغت (واژه نامه) اصطلاحات و مفاهیم اساسی.
دستورالعمل های روشی برای معلم، دانش آموز، شنونده.
مجموعه کارها و تمرین ها.
کارگاه آزمایشگاهی نظم و انضباط.
شرح سیستم امتیاز دهی.
سوالاتی برای خودآزمایی و بحث در مورد موضوعات.
تکالیف برای کار مستقل در مورد موضوعات.
فهرست چکیده ها و/یا مقالات ترم در موضوعات.
تست تکالیف روی موضوعات (برای خودکنترلی فعلی و متوسط).
وظایف آموزشی.
لیست سوالات ارزیابی نهایی درس مجتمع آموزشی و روش شناسی رشته.
ادبیات © دانشگاه دوستی مردم روسیه، انتشارات، 2013
© E.R. زریپووا، ام.جی. کوکوچیکووا، 2013.

Учебное пособие. — М.: Изд-во РУДН, 2013. — 179 с. — ISBN 5-209-01493-2 В пособии излагаются основы теории графов и алгоритмов на графах. Книга является продолжением курса дискретной математики: «Часть I. Комбинаторика» и «Часть II. Математическая логика».
Теория графов является частью науки дискретной математики. Дискретная математика состоит из следующих разделов: комбинаторика, математическая логика, общая теория графов, теория множеств и общая алгебра, теория алгоритмов, теория автоматов и теория кодирования.
Подготовлено на кафедре «Системы телекоммуникаций». Предназначено для студентов I, II курсов математических и компьютерных специальностей высших учебных заведений. Содержание.
Интерактивное оглавление
Конспект лекций по дисциплине (всего 14 лекций):
Графы. Неориентированные графы: основные понятия; маршруты, цепи, циклы; связность; деревья и леса. Ориентированные графы: основные понятия; ориентированные маршруты, пути, контуры; сильная связность. Ориентированные деревья. Метрические характеристики графов. Матричное представление графов: матрица инцидентности для неорграфа, матрица смежности для неорграфа, матрица инцидентности для орграфа, матрица смежности для орграфа. Список смежности. Построение покрывающих деревьев. Алгоритм Краскала. Построение покрывающего дерева для связного графа. Построение минимального покрывающего дерева по алгоритму Краскала. Построение максимального покрывающего дерева по алгоритму Краскала. Построение минимального покрывающего дерева для связного взвешенного графа по алгоритму Прима. Построение максимального покрывающего дерева по алгоритму Прима. Поиск пути наименьшей длины в графе. Алгоритм Дейкстры. Эйлеровы графы. Алгоритм поиска эйлерова цикла в графе. Гамильтоновы графы. Сходство и различия гамильтоновых и эйлеровых графов. Достаточные условия существования гамильтоновых циклов. Способы поиска гамильтонова цикла. Алгоритм поиска гамильтонова цикла в графе. Поиск расстояния между всеми парами вершин. Алгоритм Уоршалла-Флойда. Задача построения транзитивного замыкания бинарного отношения. Алгоритм построения транзитивного замыкания бинарного отношения. Потоки. Условия существования потока. Увеличивающая цепь. Алгоритм поиска увеличивающей цепи. Увеличение потока вдоль найденной цепи по правилам. Потоки. Поиск максимального потока. Поиск потока минимальной стоимости. Задача почтальона для орграфов. Алгоритм поиска оптимального маршрута почтальона для орграфов. Фонды оценочных средств.
Словарь (глоссарий) основных терминов и понятий.
Методические указания для преподавателя, студента, слушателя.
Сборник задач и упражнений.
Лабораторный практикум по дисциплине.
Описание балльно-рейтинговой системы.
Вопросы для самопроверки и обсуждений по темам.
Задания для самостоятельной работы по темам.
Перечень рефератов и/или курсовых работ по темам.
Тестовые задания по темам (для текущего и промежуточного самоконтроля).
Тренинговые задания.
Перечень вопросов итоговой аттестации по курсу. Учебно-методический комплекс по дисциплине.
Литература © Российский университет дружбы народов, Издательство, 2013
© Э.Р. Зарипова, М.Г. Кокотчикова, 2013.