Центральный Дом Знаний - Асельдеров 3. М., Донец Г. А. Представление и восстановление графов

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 903

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

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

Асельдеров 3. М., Донец Г. А. 
АН УССР. Ин-т кибернетики им. В. М. Глушкова
Киев : Наук, думка, 1991.— 192 с— ISBN 5-12-002332-0 

Монография посвящена теоретическим и прикладным вопросам теории графов. Наряду с известными и общепринятыми способами представления графов предлагается способ задания графа с помощью некоторой квадратичной формы. Изложены элементы теории сложности алгоритмов для задач на графах. Освещены проблемы оптимального представления графов, Рассмотрены операции над графами, заданными как традиционными способами, так и своими формальными квадратичными формами. Дается некоторый подход к решению одной из классических проблем теории графов — проблеме восстановления графа по его полному допустимому набору подграфов, известной как гипотеза Улама. Для студентов вузов по специальности математика и прикладная математика, а также для научных работников и инженеров. Табл. 17. Ил. 80. Библиогр.; G. 185—186.


Оглавление:

Предисловие.......................... 3
Список условных обозначений ................. 4
ГЛАВА 1. Способы представления графов............ 5
1.1. Общее представление произвольных графов...... 5
1.2, Задание графов с помощью матриц   ......... 8
1.3. Двоичное представление графов    .......... 11
1.4, Бинарные отношения для графов.......... 14
1.5. Задание графа в виде формальной квадратичной формы 18
1.6, Аналитическое представление графов ....... 20
ГЛАВА 2. Проблемы оптимального представления графов   .... 28
2.1. Представление графов с помощью структур данных 28
2.2. Представление деревьев .............. 32
2.3. Оценка числа операций алгоритмов......... 35
2.4. Об оптимальной кодировке арифметических графов 37
ГЛАВА 3. Элементы теории сложности алгоритмов для задач на
' графах....................... 55
3.1. Основные понятия................. 55
3.2. Классы Р и NP................... 61
3.3. Полиномиальная  сводимость   и   JVP-полные задачи 67
3.4. Доказательство результатов об NP-полноте ..... 71
3.5. Применение теории iVP-полноты для анализа  задач 77
ГЛАВА 4. Операция над обыкновенными графами........ 85
4.1, Операции над вершинами и ребрами  ......... 85
ГЛАВА 5. Восстановление графов............... 95
5.1. Изоморфизм................... 95
5.2, Инварианты................... 97
5.3. Проблемы изоморфизма ....... 104
5.4. Проблемы восстановления. Существование и единственность ......................t ю7
5.5. Гипотеза Улама.........,........ юд
5.6. Алгоритм восстановления графов по допустимому набору 112
5.7. Теорема о существовании и единственности  ...... 146
5.8. Минимальные наборы подграфов ......., 177
Заключение..................... Ig4
Список литературы.................. 135
Loading

Календарь

«  Июнь 2019  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24