Максименко А.Н. Графы многогранников и сводимость задач комбинаторной оптимизации

Дисертация

формат pdf
размер 531.72 КБ
добавлен 15 мая 2011 г.

Максименко А.Н. Графы многогранников и сводимость задач комбинаторной оптимизации

- Ярославль, - ЯГУ, - 2004, – 92 стр. Диссертация на соискание ученой степени кандидата физико-математических наук. Специальность: 01.01.09 - дискретная математика и математическая кибернетика. (На правах рукописи). Научный руководитель: доктор физико-математических наук, профессор В. А. Бондаренко.

Содержание.
Сложность в комбинаторной оптимизации.
Некоторые сведения из теории сводимости задач.
Многогранники задач.
Конусное разбиение и аффинная сводимость.
Конусное разбиение.
Аффинная сводимость.
Труднорешаемые задачи.
Задача клика.
Задача 2-выполнимость.
Задача разрез.
Задача трехмерное сочетание.
Задачи рюкзак и разбиение.
Задача коммивояжер.
Задача гамильтонов контур .
Задача гамильтонов цикл.
Задача коммивояжера с условием "неравенство треугольника".
Задача длиннейший путь.
Полиномиально разрешимые задачи.
Задача о кратчайшем пути.
Задачи о паросочетаниях.

Стоимость данного файла составляет 5 баллов

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

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

Алексеев В.Е., Таланов В.А. Графы и алгоритмы

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

Содержание. Начальные понятия теории графов. Определение графа. Графы и бинарные отношения. Откуда берутся графы. Число графов. Смежность, инцидентность, степени. Некоторые специальные графы. Графы и матрицы. Взвешенные графы. Изоморфизм. Инварианты. Операции над графами. Локальные операции. Подграфы. Алгебраические операции.

Бренстед А. Введение в теорию выпуклых многогранников

формат djvu
размер 7.05 МБ
добавлен 26 октября 2010 г.

М.: Мир, 1988. - 240 с. Монография датского математика, отражающая результаты, подученные за последние годы в комбинаторной теории выпуклых многогранников. В ней представлены соотношения Дена-Соммервилля, теоремы Макмюллена и Барнетта о максимальном и минимальном числе граней. Изложение отличается математической строгостью. В книге много упражнений и задач; она доступна для первого ознакомления с предметом. Для математиков разных специальностей,...

Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация

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

М.: Наука, 1981. - 344 с. Книга посвящена комбинаторной теории многогранников. Наряду с классическими результатами представлена новая проблематика, порожденная задачами оптимизации. Устанавливаются и исследуются связи многогранников с графами и проективными геометриями, излагаются способы построения выпуклых оболочек допустимых областей в задачах целочисленного программирования. Детально изложены результаты о многогранниках транспортной задачи. Р...

Кофман А. Введение в прикладную комбинаторику

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

-Пер. с франц. - М.: Наука, 1975. - 480 с. Развитие вычислительной техники и исследования операций вызвало повышенный интерес к комбинаторной математике. Оно привело, с одной стороны, к постановке новых комбинаторных задач, а с другой стороны, дало эффективные способы их решения с помощью электронных цифровых вычислительных машин. В предлагаемой книге известного французского математика и педагога А. Кофмана излагаются основы прикладной комбинат...

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

Статья

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

ВГКС, Минск, Петрович А.В, 2011, 28 стр. Подструктуры графа. Эйлеровы графы. Гамильтоновы графы. Понятие почти все графы. Планарные графы. Раскраска графов. Совершенные графы.

Носов В.А. Комбинаторика и теория графов

формат pdf
размер 1.02 МБ
добавлен 07 декабря 2008 г.

Описаны множества, перечисления, введение в теорию графов: Эйлеровы графы, Гамильтоновы графы, кратчайшие пути, деревья, планарные графы, раскраски графов, потоки в сетях.

Поттосин Ю.В. Дискретная математика и теория проектирования цифровых устройств и систем

формат pdf
размер 1.22 МБ
добавлен 03 апреля 2010 г.

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

Сергиенко И.В. Математические модели иметоды решения задач дискретной оптимизации

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

Изд-во: Киев: Наукова Думка Год: 1988 Второе издание, дополненное и переработанное Страниц: 472 ISBN: 5-12-009339-6 В монографии рассмотрены математические модели, эффективные методы и программное обеспечение решения задач дискретной оптимизации. Значительное внимание уделено формализованному описанию ряда практических задач, повышению эффективности методов решения задач за счет максимального учета их специфики. Изучены методы точного и приближе...

Татт У. Теория графов

формат pdf
размер 3.91 МБ
добавлен 27 декабря 2011 г.

М. : Мир, 1988.— 424 с., ил. Монография канадского математика, содержащая перспективные методы и конструкции современной теории графов (связность, факторизация, раскраска, планарность и др.). Многие результаты принадлежат автору, активно работающему в области комбинаторной теории. Книга вышла в известной серии «Энциклопедия математики и ее приложений», ряд томов которой издан на русском языке. Книгу можно использовать как справочное пособие по...

Татт У. Теория графов

формат pdf
размер 20.47 МБ
добавлен 07 июня 2010 г.

Москва "Мир", 1988 г. , 424 стр. Монография канадского математика, содержащая перспективные методы и конструкции современной теории графов (связность, факторизация, раскраска, планарность и др.). Многие результаты принадлежат автору, активно работающему в области комбинаторной теории. Книга вышла в известной серии «Энциклопедия математики и ее приложений», ряд томов которой издан на русском языке. Книгу можно использовать как справочное пособие...