Блинный график - Pancake graph - Wikipedia

Блинный график
Блинный граф P4 можно построить рекурсивно из 4 копий P3 путем присвоения различных элементов из набора {1, 2, 3, 4} в качестве суффикса каждой копии.
Вершины	${\displaystyle n!}$
Края	${\displaystyle {\dfrac {1}{2}}~n!\left(n-1\right)}$
Обхват	6, если п > 2
Хроматическое число	смотрите в статье
Хроматический индекс	п − 1
Род	смотрите в статье
Характеристики	Обычный Гамильтониан Кэли Вершинно-транзитивный Максимально связанный Сверхсвязанный Гиперподключен
Обозначение	пп
Таблица графиков и параметров

в математический поле теория графов, то блинный график п_п или же п-блинный график - граф, вершинами которого являются перестановки п символы от 1 до п и его ребра задаются между перестановками транзитивными перестановками префиксов.

Сортировка блинов это разговорный термин для математической задачи сортировки неупорядоченной стопки блины в порядке размера, когда шпатель можно вставить в любую точку стопки и перевернуть все блины над ней. А блинчик номер - минимальное количество переворотов, необходимое для заданного количества блинов. Получение блинного числа равносильно задаче получения диаметр блинного графа.^[1]

Блинный график размерности п, п_п, это регулярный граф с ${\displaystyle n!}$ вершины. Его степень п - 1, следовательно, согласно лемма о рукопожатии, она имеет ${\displaystyle {\dfrac {1}{2}}~n!\left(n-1\right)}$ края. п_п можно построить рекурсивно из n копий п_п−1, назначив другой элемент из набора {1, 2,…, п} в качестве суффикса к каждой копии.

Полученные результаты

п_п (п ≥ 4) является сверхсвязанный и гипер-связанный.^[2]

Их обхват является^[3]

${\displaystyle g(P_{n})=6,{\text{ if }}n>2.}$

Γ (п_п) род из п_п является:^[4]

${\displaystyle n!\left({\frac {n-4}{6}}\right)+1\leq \gamma (P_{n})\leq n!\left({\frac {n-3}{4}}\right)-{\frac {n}{2}}+1.}$

Хроматические свойства

Есть некоторые известные раскраска графика свойства блинных графов.

А п_п (п ≥ 3) блинный граф имеет общее хроматическое число ${\displaystyle \chi _{t}(P_{n})=n}$, хроматический индекс ${\displaystyle \chi _{e}(P_{n})=n-1}$.^[5]

Существуют эффективные алгоритмы правильной (n − 1) -раскраски и полной п-раскрашивание блинных графиков.^[5]

Для ${\displaystyle \chi (P_{n})}$ для хроматического числа известны следующие пределы:

Если ${\displaystyle 4\leq n\leq 8}$, тогда

${\displaystyle \chi (P_{n})\leq {\begin{cases}n-k,&{\text{if }}n\equiv k{\pmod {4}},k=1,3;\\n-2,&{\text{if }}n\equiv k{\pmod {4}},k=0,2;\end{cases}}}$

если ${\displaystyle 9\leq n\leq 16}$, тогда

${\displaystyle \chi (P_{n})\leq {\begin{cases}n-(k+2),&{\text{if }}n\equiv k{\pmod {4}},k=1,3;\\n-4,&{\text{if }}n\equiv k{\pmod {4}},k=0,2;\end{cases}}}$

если ${\displaystyle n\geq 17}$, тогда

${\displaystyle \chi (P_{n})\leq {\begin{cases}n-(k+4),&{\text{if }}n\equiv k{\pmod {4}},k=1,2,3;\\n-8,&{\text{if }}n\equiv k{\pmod {4}},k=0.\end{cases}}}$

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

Конкретные или вероятные значения хроматического числа

${\displaystyle n}$	3	4	5	6	7	8	9	10	11	12	13	14	15	16
${\displaystyle \chi (P_{n})}$	2	3	3	4	4	4?	4?	4?	4?	4?	4?	4?	4?	4?

Перечисление цикла

В п_п (п ≥ 3) блинный граф всегда есть хотя бы один цикл длины ℓ, когда ${\displaystyle 6\leq \ell \leq n!}$ (но нет циклов длины 3, 4 или 5).^[6] Отсюда следует, что граф Гамильтониан и любые две вершины можно соединить гамильтоновым путем.

О 6-циклах п_п (п ≥ 4) блинный граф: каждая вершина принадлежит ровно одному 6-циклу. График содержит ${\displaystyle {\frac {n!}{6}}}$ независимые (вершинно-непересекающиеся) 6-циклы.^[7]

О 7-циклах п_п (п ≥ 4) блинный граф: каждая вершина принадлежит ${\displaystyle 7\cdot (n-3)}$ 7-циклов. График содержит ${\displaystyle n!\cdot (n-3)}$ разные 7-циклы.^[8]

О 8-циклах п_п (п ≥ 4) блинный граф: граф содержит ${\displaystyle {\frac {n!(n^{3}+12n^{2}-103n+176)}{16}}}$ разные 8-циклы; максимальный набор независимых 8-циклов содержит ${\displaystyle {\frac {n!}{8}}}$ из тех.^[7]

Диаметр

Задача сортировки блинов (получение номера блинов) и получение диаметра графа блинов эквивалентны. Одна из основных трудностей в решении этой проблемы - сложный цикл структура блинного графа.

Блинные числа
(последовательность A058986 в OEIS )

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
${\displaystyle P_{n}}$	0	1	3	4	5	7	8	9	10	11	13	14	15	16	17	18	19

Число блинов, которое представляет собой минимальное количество переворачиваний, необходимое для сортировки любой стопки п было показано, что блины лежат между 15/14п и 18/11п (приблизительно 1,07п и 1,64п,), но точное значение остается открытой проблемой.^[9]

В 1979 г. Билл Гейтс и Христос Пападимитриу^[10] дал верхнюю границу 5/3п. Спустя тридцать лет это было улучшено, чтобы 18/11п командой исследователей из Техасский университет в Далласе под руководством профессора-основателя Хэл Садборо^[11] (Chitturi et al., 2009 г.^[12]).

В 2011 году Лоран Бюльто, Гийом Фертин и Ирена Русу^[13] доказал, что задача нахождения кратчайшей последовательности переворотов для заданной стопки блинов является NP-сложной, тем самым ответив на вопрос, который оставался открытым более трех десятилетий.

Сгоревший блин граф

В варианте, называемом проблема подгоревшего блина, дно каждого блина в стопке подгорело, и сортировка должна завершаться подгоревшей стороной каждого блина вниз. Это знаковая перестановка, а если блин я "сгоревшей стороной вверх" отрицательный элемент я ставится на место я в перестановке. В сгоревший блин граф является графическим представлением этой проблемы.

А ${\displaystyle P'_{n}}$ граф сгоревший блин обычный, его порядок ${\displaystyle 2^{n}\cdot n!}$, его степень ${\displaystyle n}$.

Для своего варианта Дэвид С. Коэн (Дэвид X. Коэн ) и Мануэль Блюм в 1995 году доказал, что ${\displaystyle 3n/2\leq P'_{n}\leq 2n-2}$ (когда верхний предел истинен, только если ${\displaystyle n>9}$).^[14]

Цифры подгоревшие блины
(последовательность A078941 в OEIS )

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12
${\displaystyle P'_{n}}$	1	4	6	8	10	12	14	15	17	18	19	21

Обхват графа сгоревшего блина составляет:^[3]

${\displaystyle g(P_{n})=8{\text{, if }}n>2.}$

Другие классы блинных графов

Как в исходной задаче сортировки блинов, так и в задаче сгоревших блинов, изменение префикса была операцией, соединяющей две перестановки. Если мы разрешаем развороты без префиксов (как если бы мы переворачивали двумя шпателями вместо одного), то можно определить четыре класса графов-блинов. Каждый граф-блинчик встраивается во все графы-блины более высокого порядка того же семейства.^[3]

Классы блинных графиков

Имя	Обозначение	Объяснение	Заказ	Степень	Обхват (если n> 2)
беззнаковый график обращения префикса	${\displaystyle UP_{n}}$	Оригинальная задача сортировки блинов	${\displaystyle n!}$	${\displaystyle n-1}$	${\displaystyle 6}$
беззнаковый график разворота	${\displaystyle UR_{n}}$	Исходная задача с двумя шпателями	${\displaystyle n!}$	${\displaystyle {n \choose 2}}$	${\displaystyle 4}$
подписанный график обращения префикса	${\displaystyle SP_{n}}$	Проблема подгоревшего блина	${\displaystyle 2^{n}\cdot n!}$	${\displaystyle n}$	${\displaystyle 8}$
подписанный график разворота	${\displaystyle SR_{n}}$	Проблема подгоревшего блина двумя лопатками	${\displaystyle 2^{n}\cdot n!}$	${\displaystyle {n+1 \choose 2}}$	${\displaystyle 4}$

Приложения

Поскольку графы-блины обладают множеством интересных свойств, таких как симметричные и рекурсивные структуры (они Графики Кэли, таким образом вершинно-транзитивный ), сублогарифмической степени и диаметра и относительно редкий (по сравнению, например, с гиперкубы ) им уделяется большое внимание как модели сетей межсетевого взаимодействия для параллельных компьютеров.^{[4][15][16][17]} Когда мы рассматриваем блинные графы как модель взаимосвязанных сетей, диаметр графа является мерой, которая представляет задержку связи.^[18][19]

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

Рекомендации

1. Асаи, Сёго; Куноике, Юсуке; Синано, Юдзи; Канеко, Кейчи (01.09.2006). Вычисление диаметра 17-блинного графа с использованием кластера ПК. Euro-Par 2006 Параллельная обработка: 12-я Международная конференция Euro-Par. Конспект лекций по информатике. 4128. С. 1114–1124. Дои:10.1007/11823285_117. ISBN  978-3-540-37783-2.
2. Дэн, Юнь-Пин; Сяо-Донг, Чжан (31 марта 2012 г.). "Группы автоморфизмов графов-блинов". Письма об обработке информации. 112 (7): 264–266. arXiv:1201.0452. Дои:10.1016 / j.ipl.2011.12.010.
3. Компо, Филипп Э.К. (06.09.2011). «Обхват блинных графиков». Дискретная прикладная математика. 159 (15): 1641–1645. Дои:10.1016 / j.dam.2011.06.013.
4. Нгуен, Куан; Беттайеб, Саид (5 ноября 2009 г.). «О роде блинной сети» (PDF). Международный арабский журнал информационных технологий. 8 (3): 289–292.
5. Константинова, Елена (01.08.2017). «Хроматические свойства блинных графиков». Обсуждения Математическая теория графов. 37 (3): 777–787. Дои:10.7151 / dmgt.1978.
6. Шеу, Джих-Цзянь; Тан, Джимми Дж. М. (2006). «Встраивание цикла в сети межсетевых соединений» (PDF). 23-й семинар по комбинаторной математике и теории вычислений.
7. Константинова, Е.В .; Медведев, А. (2013-04-26). «Маленькие циклы в блинном графике» (PDF). Ars Mathematica Contemporanea. 7: 237–246. Дои:10.26493 / 1855-3974.214.0e8. Архивировано из оригинал (PDF) на 2017-12-15. Получено 2017-08-04.
8. Константинова, Е.В .; Медведев, А. (01.04.2010). «Циклы длины семь на блинном графике». Дискретн. Анальный. Исслед. Опер. 17 (5): 46–55. Дои:10.1016 / j.tcs.2008.04.045.
9. Фертин, Г., Лабарр, А., Русу, И., Танье, Э., Виалетт, С. (2009). Комбинаторика перестроек генома. MIT Press. ISBN  9780262062824.
10. Гейтс, В.; Пападимитриу, К. (1979). «Границы для сортировки по обращению префикса» (PDF). Дискретная математика. 27: 47–57. Дои:10.1016 / 0012-365X (79) 90068-2. Архивировано из оригинал (PDF) на 2007-06-10. Получено 2017-08-04.
11. «Команда побеждает молодого Билла Гейтса улучшенным ответом на так называемую задачу« Блин »по математике». Техасский университет в Центре новостей Далласа. 17 сентября 2008 г. Архивировано с оригинал 5 апреля 2012 г.. Получено 10 ноября, 2008. Команда студентов Университета Калифорнии в Далласе, изучающих информатику, и их научный руководитель усовершенствовали давнее решение математической головоломки, известной как проблема блинов. Предыдущее лучшее решение, просуществовавшее почти 30 лет, было разработано Биллом Гейтсом и одним из его преподавателей в Гарварде Христосом Пападимитриу за несколько лет до основания Microsoft.
12. Chitturi, B .; Fahle, W .; Meng, Z .; Morales, L .; Shields, C.O .; Sudborough, I.H .; Войт, В. (31 августа 2009 г.). «Верхняя граница (18/11) n для сортировки по перестановкам префиксов». Теоретическая информатика. Графики, игры и вычисления: Посвящается профессору Буркхарду Моньену по случаю его 65-летия. 410 (36): 3372–3390. Дои:10.1016 / j.tcs.2008.04.045.
13. Бюльто, Лоран; Фертин, Гийом; Русу, Ирена (2015). "Блин листать сложно". Журнал компьютерных и системных наук. 81 (8): 1556–1574. arXiv:1111.0434. Дои:10.1016 / j.jcss.2015.02.003.
14. Дэвид С. Коэн, Мануэль Блюм: О проблеме сортировки подгоревших блинов. В: Дискретная прикладная математика. 61, № 2, 1995, С. 105–120. DOI: 10.1016 / 0166-218X (94) 00009-3.
15. Akl, S.G .; Qiu, K .; Стойменович, И. (1993). «Фундаментальные алгоритмы для сетей межсоединений типа« звезда »и« блины »с приложениями к вычислительной геометрии». Сети. 23 (4): 215–225. CiteSeerX  10.1.1.363.4949. Дои:10.1002 / нетто.3230230403.
16. Bass, D.W .; Садборо, И. (Март 2003 г.). «Блин проблемы с ограниченным обращением префиксов и некоторыми соответствующими сетями Кэли». Журнал параллельных и распределенных вычислений. 63 (3): 327–336. CiteSeerX  10.1.1.27.7009. Дои:10.1016 / S0743-7315 (03) 00033-9.
17. Berthomé, P .; Ferreira, A .; Переннес, С. (декабрь 1996 г.). «Оптимальное распространение информации в звездных и блинных сетях». Транзакции IEEE в параллельных и распределенных системах. 7 (12): 1292–1300. CiteSeerX  10.1.1.44.6681. Дои:10.1109/71.553290.
18. Кумар, В., Грама, А., Гупта, А., Карипис, Г .: Введение в параллельные вычисления: разработка и анализ алгоритмов. Бенджамин / Каммингс (1994)
19. Куинн, М.Дж .: Параллельные вычисления: теория и практика, второе издание. МакгроуХилл (1994)