Элементы теории графов, Домнин Л.Н., 2004
Элементы теории графов, Домнин Л.Н., 2004.
Книга является учебным пособием и состоит из пяти разделов. В первом даны основные понятия и определения теории графов, рассмотрены виды графов и способы их описания. Второй раздел посвящен вопросу о связности ориентированных графов. Важнейший вид графов деревья рассмотрен в третьем разделе. Разобраны задачи описания и пересчета деревьев, а также задача о кратчайшем остове. Четвертый раздел посвящен вопросам пересчета и перечисления путей в графах. Здесь же приведены различные варианты задачи о кратчайшем пути и алгоритмы ее решения. В пятом разделе рассматриваются фундаментальные, эйлеровы и гамильтоновы циклы. Разбираются условия существования и алгоритмы поиска таких циклов в графе.
Пособие подготовлено, но материалам курса лекций, но теории графов, читаемого автором для студентов специальности "Прикладная математика" Пензенского государственного университета. Может быть использовано студентами других специальностей при изучении соответствующих разделов дискретной математики.
Содержание
1 Основные понятии теории графой
1.1 Определение графа.
1.2 Подграфы.
1.3 Виды графов.
1.1 Матрицы графой.
1.5 Диаметр, радиус и центр графа.
1.6 Ориентированные графы.
1.7 Маршруты, цепи и простые цепи.
2 Связность и орграфах
2.1 Основные понятия.
2.2 Компоненты связности.
2.3 Конденсация орграфа.
2.1 Отыскание сильных компонент.
2.5 Матрицы достижимостей.
2.6 Получение матрицы достижимостей.
2.7 Алгоритм Уоршолла.
2.8 База графа.
3.Деревья
3.1 Основные понятия.
3.2 Описание деревьев.
3.3 Задачи с деревьями.
3.3.1 Перечисление остовных деревьев.
3.3.2 Пересчет остовных деревьев.
M.I Задача о кратчайшем остове графа.
3.1.1 Алгоритм Краскала.
3.1.2 Алгоритм Прима.
4 Пути и маршруты и графах
1.1 Существование путей.
4.2 Пересчет маршрутов и путей.
1.3 Перечисление маршрутов и путей.
1.1 Задачи о кратчайших путях.
4.4.1 Графы с дугами единичной длины.
1.1.2 Графы со взвешенными дугами (ребрами).
4.4.3 Ациклические орграфы.
5 Циклы
5.1 Фундаментальные циклы и разрезы.
5.2 Эйлеровы циклы.
5.2.1 Определение и условия существования.
5.2.2 Алгоритм поиска эйлерова цикла.
5.2.3 О количестве эйлеровых графов.
5.2.4 Задача почтальона.
5.3 Гамильтоновы циклы.
5.3.1 Определение и условия существования.
5.3.2 Методы поиска гамильтоновых циклов.
5.4 Задача коммивояжера.
5.4.1 Применение и методы решения.
5.4.2 Метод ветвей и границ.
| Рейтинг: | 4.8 баллов / 2537 оценок |
| Формат: | Книга |
| Уже скачали: | 12770 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Язык разговора
Автор: Алан Гарнер, Аллан Пиз Издательство: Эксмо-Пресс Год: 2007 Cтраниц: 224 Формат: doc Размер: 1,5 мб ISBN: 5-04-004541-7 Качество: Хорошее Язык: русский Описание: Разговаривать умеет . . .
-
Фокусы языка
Автор: Роберт Дилтс Издательство: Питер Год: 2002 Cтраниц: 320 Формат: doc Размер: 1.7 мб ISBN: 5-272-00155-9 Качество: Хорошее Язык: русский Описание: В книге крупнейшего специалиста по н . . .
-
Умейте постоять за себя
Автор: Альберти Р. Е., Эммонс М. Л. Издательство: Cтраниц: 31 Формат: doc Размер: 1 мб Качество: Отличное Язык: русский Описание: Мы, авторы настоящей книги убеждены, что индивидуум стоит б . . .
-
Big Porn Inc: Exposing the Harms of the Global Pornography Industry
Название: Big Porn Inc: Exposing the Harms of the Global Pornography IndustryАвтор: Reist Melinda Tankard, Bray AbigailЖанр: Культурология, Обществознание, социологияОписание:The unprecedented mainstr . . .
-
Структура магии. Том 2. Книга о коммуникации и изменениях
Автор: Ричард Бэндлер, Джон ГриндерИздательство: Прайм-ЕврознакГод: 2004Cтраниц: 224Формат: docРазмер: 1,30 mbISBN: 5-93878-152-3Качество: ХорошееЯзык: русскийОписание:"Структура магии" на протяжении . . .
-
The Host
Название: The HostАвтор: Stephenie MeyerЖанр: ТриллерОписание:In this tantalizing SF thriller, planet-hopping parasites are inserting their silvery centipede selves into human brains, curing cancer, e . . .
-
Der Himmel kennt keine G?nstlinge
Название: Der Himmel kennt keine G?nstlingeАвтор: Erich Maria RemarqueЖанр: Современная прозаОписание:Zwei ungew?hnliche Menschen versuchen, f?r kurze Zeit einen Ausnahmezustand des Gl?cks zu verwirkl . . .
-
The Phantom of the Opera
Название: The Phantom of the OperaАвтор: Gaston LerouxЖанр: Остросюжетные любовные романыОписание:THE PHANTOM OF THE OPERA follows the life of an eccentric, physically deformed genius who terrorizes t . . .
-
Kookaburra Technical manual. Series 1, no.7: Messerschmitt Me 262 Described Part 2
Название: Kookaburra Technical manual. Series 1, no.7: Messerschmitt Me 262 Described Part 2Автор: Kenneth A. MerrickИздательство: Kookaburra Technical PublicationsГод: 1972Страниц: 27Формат: PDF в RA . . .
-
Kookaburra Technical manual. Series 1, no.6: Messerschmitt Me 262 Described Part 1
Название: Kookaburra Technical manual. Series 1, no.6: Messerschmitt Me 262 Described Part 1Автор: Kenneth A. MerrickИздательство: Kookaburra Technical PublicationsГод: 1972Страниц: 27Формат: PDF в RA . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Элементы теории графов, Домнин Л.Н., 2004. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.