Блинный график

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

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

Сортировка блинов — это разговорный термин, обозначающий математическую задачу сортировки неупорядоченной стопки блинов по размеру, когда лопатку можно вставить в любую точку стопки и использовать для переворачивания всех блинов над ней. Число блинов — это минимальное количество бросков, необходимое для заданного количества блинов. Получение блинного числа эквивалентно задаче получения диаметра блинного графа.

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

Результаты

P _n ( n ≥ 4) сверхсвязен и гиперсвязен .

Их обхват составляет

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

γ( группы _Pn Pn) Род ограничен снизу _: и сверху следующим образом

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

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

Существуют некоторые известные свойства раскраски блинных графов.

≥ имеет ₃ ) Блинный граф P n ( n полное хроматическое число $\chi _{t}(P_{n})=n$, хроматический индекс $\chi _{e}(P_{n})=n-1$.

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

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

Если $4\leq n\leq 8$, затем

$\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}}$

если $9\leq n\leq 16$, затем

$\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}}$

если $n\geq 17$, затем

$\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}}$

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

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

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

Перечисление циклов

В блинном графе P _n ( n ≥ 3) всегда существует хотя бы один цикл длины ℓ , когда $6\leq \ell \leq n!$ (но циклов длины 3, 4 или 5 нет). Это означает, что граф гамильтонов и любые две вершины можно соединить гамильтоновым путем.

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

О 7-циклах блинного графа P _n ( n ≥ 4): каждая вершина принадлежит $7\cdot (n-3)$ 7-циклов. Граф содержит $n!\cdot (n-3)$ разные 7-циклы.

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

Диаметр

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

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

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

число блинов, которое представляет собой минимальное количество переворотов, необходимое для сортировки любой стопки из n блинов, находится между Было показано, что ⁠ 15/14 ​ ​ ⁠ н и ⁠ 18/11 n ) , ⁠ n приблизительно 1,07 ( и 1,64 n но точное значение остаётся открытой проблемой.

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

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

График подгоревших блинов

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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