Зарегистрироваться
Восстановить пароль
FAQ по входу

Константинова Е.В. Комбинаторные задачи на графах Кэли

  • Файл формата pdf
  • размером 804,41 КБ
  • Добавлен пользователем
  • Отредактирован
Константинова Е.В. Комбинаторные задачи на графах Кэли
Новосибирск: НГУ, 2010. — 109 с. Курс лекций по теории графов, читаемых для студентов Новосибирского государственного университета на кафедре теоретической кибернетики.
Программа курса:
Введение.
Определения, понятия, примеры.
Группы.
Симметрическая группа Symn.
Гипероктаэдральная группа Bn.
Графы.
Регулярные и транзитивные графы.
Дистанционно-регулярные и -транзитивные графы.
Графы Кэли.
Простейшие примеры графов Кэли.
Основные свойства графов Кэли.
Граф Хэмминга: дистанционно-транзитивный граф Кэли.
Граф Джонсона: дистанционно-транзитивный граф, не являющийся графом Кэли.
Граф Кнезера: когда он является графом Кэли?
Граф Кэли на симметрической группе Symn.
Граф Кэли на гипероктаэдральной группе Bn.
Гамильтоновость графов Кэли.
Гамильтоновость гиперкуба и код Грея.
Комбинаторные условия для гамильтоновости.
Гипотезы Ловаса и Бабаи.
Гамильтоновость графов Кэли на произвольной конечной группе.
Гамильтоновость графов Кэли на симметрической группе.
Гамильтоновость Pancake графа.
Другие циклы Pancake графа.
Циклы длины шесть.
Циклы длины семь.
Определение диаметра графа Кэли.
Диаметр графов Кэли на абелевых и неабелевых группах.
Диаметр графов Кэли на симметрической и знакопеременной группах.
Pancake problem.
Верхняя оценка Гейтса и Пападимитроу на диаметр Pancake графа.
Нижняя оценка Гейтса и Пападимитроу на диаметр Pancake графа.
Улучшенные оценки Хейдари и Садбороу на диаметр Pancake графа.
Точные значения диаметра Pancake графа.
Burnt Pancake problem.
Улучшенные оценки на диаметр Burnt Pancake графа.
Точные значения диаметра Burnt Pancake графа.
Сортировка реверсалами.
Эффективное восстановление вершин в графе.
Граф Хэмминга Ln(q).
Граф Джонсона J(n,m).
Реверсальный граф Rn.
Перестановки и реверсалы.
Структурные свойства реверсального графа Rn.
Восстановление перестановок в реверсальном графе Rn.
Литература.
  • Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.
  • Регистрация