Вопросы с тегом «co.combinatorics»

15
Поддержание порядка в списке в за раз

Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...

15
Разбиение графа на узло-непересекающиеся циклы

Связанная проблема: Теорема Веблена утверждает, что «граф допускает разложение цикла тогда и только тогда, когда оно четное». Циклы являются ребрами непересекающимися, но не обязательно узлы непересекающимися. Другими словами, «множество ребер графа можно разбить на циклы тогда и только тогда,...

15
Что мы можем доказать бесконечными графами, что мы не можем доказать без них?

Это дополнительный вопрос к этому вопросу о бесконечных графах. Ответы и комментарии к этому списку объектов и ситуаций, которые естественным образом моделируются бесконечными графами. Но есть также многочисленные теоремы о бесконечных графах (см. Главу 8 в книге Дистеля), из которых, например,...

15
Разложение графов рода один

Планарные графы -бесплатно. Такие графики могут быть разложены на трехсвязные компоненты, которые, как известно, являются либо плоскими, либо компонентами K 5 .К3 , 3К3,3K_{3,3}К5К5K_5 Есть ли такая «хорошая» декомпозиция графов рода один? В своей основополагающей работе над минорами графов...

15
Разложение k-связных графов на (k + 1) -связные компоненты

Связный граф можно разложить на его двусвязные компоненты. Это дерево сечений блоков является уникальным. Аналогично, двусвязные графы можно разложить на трехсвязные компоненты. Соответствующее дерево SPQR описывает все 2-вершинные срезы графа и однозначно определяется из его графа. Этот процесс не...

14
Количество срезов графа без использования алгоритма Каргера

Мы знаем, что алгоритм mincut Каргера может быть использован, чтобы доказать (неконструктивно), что максимальное число возможных срезов, которые может иметь граф, равно (n2)(n2)n \choose 2 . Мне было интересно, можем ли мы как-то доказать эту идентичность, дав биективное (довольно инъективное)...

14
0-1 Линейное программирование: вычисление оптимальной формулировки

Рассмотрим мерное пространство , и пусть - линейное ограничение вида , где , и k \ in \ mathbb {R} .nnn{0,1}n{0,1}n\{0,1\}^nccca1Икс1+ а2Икс2+ а3Икс3+ . , , + а  n - 1Иксn - 1+ аNИксN≥ ka1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq kaя∈ Rai∈Ra_i...

14
Преобразование Байгеля-Таруи из ACC

Я читаю приложение о АССЕ нижних границах для NEXP в Arora и Барак вычислительной сложности книги. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Одна из ключевых лемм - это преобразование из цепей в полилинейные полиномы над целыми числами с полилогарифмической степенью и...

14
Проводимость и диаметр в регулярных графиках

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

14
Количество триангуляций множества

Этим летом я услышал, как Эмо Велцл говорит на эту тему. Я знаю, что число триангуляций набора из точек на плоскости находится где-то между Ω ( 8,48 n ) и O ( 30 n ) . Извиняюсь, если я устарел; Обновления приветствуются.nnnΩ(8.48n)Ω(8.48n)\Omega(8.48^n)O(30n)O(30n)O(30^n) Я упомянул об этом в...

14
Идеальные совпадения на шахматной доске?

Рассмотрим проблему определения максимального количества рыцарей, которых можно разместить на шахматной доске, чтобы двое из них не атаковали друг друга. Ответ 32: найти идеальное соответствие не так уж и сложно (график, индуцированный ходами коня, является двудольным, и есть идеальное соответствие...

14
Точный алгоритм для задачи маркировки ребер в DAG

Я внедряю некоторую системную часть, которая требует некоторой помощи. Поэтому я формулирую это как проблему графа, чтобы сделать его независимым от домена. Задача: Нам дан ориентированный ациклический граф . Без ограничения общности предположим, что G имеет ровно одну исходную вершину s и ровно...

14
VC размерность полиномов над тропическими полукольцами?

Как и в этом вопросе, я заинтересован в BPPBPP\mathbf{BPP} по сравнению с PP\mathbf{P} / polypoly\mathrm{poly} задачи для тропических (max,+)(max,+)(\max,+) и (min,+)(min,+)(\min,+) цепей. Этот вопрос сводится к показу верхних оценок размерности многочленов VC над тропическими полукольцами (см....

13
H-свободный раздел

Это вопрос, навеянный проблемой H-свободного разреза . Для данного графа разбиение его множества вершин на частей является -свободным, если не индуцирует копию для всех , .VVVrrrV1,V2,…,VrV1,V2,…,VrV_1, V_2, \ldots, V_rHHHG[Vi]G[Vi]G[V_i]HHHiii1≤i≤r1≤i≤r1 \leq i \leq r Я хочу рассмотреть следующий...

13
Сохраняется ли ширина клики при сжатии краев?

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

13
О методах Пфаффа в подсчете и комбинаторике

Недавно я изучал введение в голографические алгоритмы. Я столкнулся с некоторыми комбинаторными объектами, которые называются пфаффианцами. Я не очень много знаю о них на данный момент и натолкнулся на некоторые неожиданные способы их использования. Например, я узнал, что их можно использовать для...

13
Емкость Уникально Решаемой Головоломки (USP)

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

13
LP релаксация независимого множества

Я пробовал следующее расслабление LP максимального независимого набора max∑iximax∑ixi\max \sum_i x_i s.t. xi+xj≤1 ∀(i,j)∈Es.t. xi+xj≤1 ∀(i,j)∈E\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E xi≥0xi≥0x_i\ge 0 Я получаю 1/21/21/2 для каждой переменной для каждого кубического недвудольного графа Я...

13
Игра Дракула

История вопроса Этот вопрос мотивирован настольной игрой под названием «Дракула». В этой игре есть один вампир и четыре охотника, цель охотников - поймать вампира. Действие игры происходит в Европе. Игра выглядит следующим образом: 1. Игрок-охотник сажает всех охотников в города. В одном городе...

13
Применение номеров Рамси

Определение чисел Рамси следующее: Пусть положительное число такого , что каждый граф порядка по крайней мере содержит либо клику на вершину или множество стабильного на вершинах.R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)aaabbb Я работаю над некоторым расширением номеров Рамси. Хотя исследование...