Реферат - Обзор алгоритмов на графах

Реферат

формат docx
размер 85.39 КБ
добавлен 25 ноября 2011 г.

Россия, Нижний Новгород, НГТУ им. Алексеева, 2011 год, 20 страниц.
В работе дается описание основных алгоритмов на графах и их применение в различных областях.
Методы систематического обхода вершин графа.
Алгоритм поиска в глубину.
Алгоритм поиска в ширину.
Остовное дерево наименьшего веса. Задача Штейнера.
Алгоритм Прима.
Алгоритм Краскала.
Задача плоской укладки.
Гамма-алгоритм.
Задача раскраски графа.
Метод неявного перебора.
Приближенный алгоритм.
Нахождение кратчайших путей.
Алгоритм Дейкстры.
Алгоритм Флойда.
Эйлеровы графы.
Задача о наибольшем потоке.
Алгоритм Форда-Фалкерсона.

Похожие разделы

Смотрите также

Асельдеров З.М., Донец Г.А. Представление и восстановление графов

формат djvu
размер 4.8 МБ
добавлен 29 июля 2010 г.

Монография посвящена теоретическим и прикладным вопросам теории графов. Наряду с известными и общепринятыми способами представления графов предлагается способ задания графа с помощью некоторой квадратичной формы. Изложены элементы теории сложности алгоритмов для задач на графах. Рассмотрены операции на графами, заданными как традиционными способами, так и своими формальными квадратичными формами. Даётся некоторый подход к решению одной из классич...

Волченская Т.В., Князьков В.С. Компьютерная математика:Часть 2. Теория графов

формат pdf
размер 967.87 КБ
добавлен 18 декабря 2009 г.

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

Галкина В.А. Дискретная математика. Комбинаторная оптимизация на графах. Гелиос АРВ, 2003

формат djvu
размер 1.48 МБ
добавлен 19 января 2011 г.

В учебном пособии систематически излагается материал, входящий в федеральный компонент дисциплины "Дискретная математика" Государственных образовательных стандартов группы специальностей "Информационная безопасность". Рассмотрены основы теории графов, основные постановки и методы решения оптимизационных задач на графах. Особое внимание уделено вопросам построения алгоритмов приближенного решения оптимизационных задач и оценкам сложности. Для...

Контрольная - Оптимальные задачи на графах

Контрольная работа

формат doc
размер 315.82 КБ
добавлен 07 февраля 2011 г.

Тема: графы. Нахождение кратчайшего пути в графах. Алгоритм Дейкетра. Определить максимальный поток из P(0) в P(7).

Лекции по дискретной математике. Глава 4 Часть 2

Статья

формат doc
размер 540 КБ
добавлен 16 января 2012 г.

ВГКС, Минск, Петрович А.В, 2011, 21 стр. Задача коммивояжёра(Проблема путешествующего купца) Кратчайшие пути во взвешенных графах и орграфах

Лекции по теории графов

Статья

формат doc
размер 704.15 КБ
добавлен 21 октября 2009 г.

Препод. Уразбахтин, УГАТУ. Содержание: Графы. Определение. Достижимость и связность в графах. Знаковые графы и теория структурного баланса. Раскраски. Кратчайшие пути в графах. Размещение центров и медиан в графах. Деревья.

Липский В. Комбинаторика для программистов

формат djvu
размер 1.15 МБ
добавлен 29 января 2009 г.

М, Мир., 1988 г. Первая глава данной книги содержит изложение наиболее классических разделов комбинаторики (перестановки, разбиения множеств и чисел, биномиальные коэффициенты, производящие функции, и т.д.), а также многие — необязательно классические — алгоритмы генерирования упомянутых комбинаторных объектов. Во второй главе представлены основные методы, используемые при конструировании алгоритмов на графах, в особенности методы систематическог...

Ответы на экзамен. 2 семестр

pottee

формат doc
размер 313.26 КБ
добавлен 16 декабря 2009 г.

Преподаватель Завьялова Е. А. Определениее графа. Основ. хар-ки. виды графов, Связность, Эйлеровы графы, Циклы Гамильтона, Изоморфизм графов, Метрические характеристики графов, Планарные графы, Раскраска графов, Паросочетания, Экстремальные пути в нагруженных ориентировочных графах, Сети, Фундаментальная система циклов графа, Операции над графами, Вычислительная сложность алгоритмов (Дейкстры, Прима, Краскала), МТ.

Хаггарти Р. Дискретная математика для программистов. 2-е дополненное издание

формат djvu
размер 4.43 МБ
добавлен 14 сентября 2010 г.

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

Шпора на экзамен по ДМ. 2 семестр

pottee

формат docx
размер 88.77 КБ
добавлен 16 декабря 2009 г.

Преподаватель Завьялова Е. А. Определение графа. Основ. хар-ки. виды графов, Связность, Эйлеровы графы, Циклы Гамильтона, Изоморфизм графов, Метрические характеристики графов, Планарные графы, Раскраска графов, Паросочетания, Экстремальные пути в нагруженных ориентировочных графах, Сети, Фундаментальная система циклов графа, Операции над графами, Вычислительная сложность алгоритмов (Дейкстры, Прима, Краскала), МТ.