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

10
Решение графа гомоморфизма

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

10
Логический код, исправляющий ошибки над

Существует ли известная конструкция линейного кода с исправлением ошибок (с приемлемыми параметрами), такая, что при задании булева вектора v ∈ { 0 , 1 } n он также возвращает булев вектор WHP? (хотя это более F q )E C C : FNQ→ FмQECC:Fqn→Fqm\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^mv ∈ { 0 , 1...

10
Генерация графиков обхвата

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

10
Вычисление закрытия профсоюза

Для данного семейства не более подмножеств . Замыкание объединения другого набор семейство , содержащий каждый набор , который можно построить, взяв объединение 1 или более множеств в . Byмы обозначим число множеств в . n { 1 , 2 , … , n } F C F | C | СFF\mathcal FNNn{ 1 , 2 , … , n }{1,2,...,N}\{...

10
Случайное блуждание и среднее время попадания в простой неориентированный граф

Пусть простой неориентированный граф на n вершинах и m ребрах.G = ( V, E)гзнак равно(В,Е)G=(V,E)NNnммm Я пытаюсь определить ожидаемую продолжительность работы алгоритма Вильсона для генерации случайного остовного дерева . Там показано, что O ( τ ) , где τ - среднее время удара : τ = ∑ v ∈ V π ( v )...

9
Расширения теоремы Рамсея: одноцветные, но разнообразные

В качестве продолжения моего предыдущего вопроса , который был разрешен Сянь-Чжи Чангом, приведу еще одну попытку найти соответствующее обобщение теоремы Рамсея. (Вам не нужно читать предыдущий вопрос; этот пост является самостоятельным.) Параметры: целые числа 1≪d≪k≪n1≪d≪k≪n1 \ll d \ll k \ll n...

9
Построение графиков ограниченного пересечения числа

Теорема Фари говорит, что простой планарный граф можно нарисовать без пересечений, так что каждое ребро является отрезком прямой. Мой вопрос заключается в том, существует ли аналогичная теорема для графов ограниченного числа пересечений . В частности, можем ли мы сказать, что простой график с...

9
Ограничение числа ребер между звездными графами так, чтобы граф был плоским

У меня есть граф который состоит только из звездных графов. Звездный граф состоит из одного центрального узла, имеющего ребра для каждого другого узла в нем. Пусть быть разные звезды графики различных размеров , которые присутствуют в . Мы называем множество всех узлов , которые являются центрами в...

9
Существуют ли «графические» алгебры, которые могут описать «форму» графов?

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

9
Сколько слов длины

ИЗМЕНЕНО ДЛЯ ДОБАВЛЕНИЯ : На этот вопрос теперь по существу дан ответ; пожалуйста, смотрите эту запись в блоге для более подробной информации. Спасибо всем, кто разместил комментарии и ответы здесь. ОРИГИНАЛЬНЫЙ ВОПРОС Это, надеюсь, более умная и информированная версия вопроса, который я задал на...

9
Разделяет ли пара непересекающихся гомотопических циклов в дуале граф?

Позволять гGG быть графом, вложенным в ориентируемую компактную поверхность рода гggтак что вложение является клеточным. Рассмотрим двойственный графикг*G∗G^*, ПозволятьС1C1C_1 а также С2C2C_2 быть непересекающимися циклами в г*G∗G^* гомотопны друг другу и позволяют Е1E1E_1 а также Е2E2E_2 быть их...

9
Вариация расхождения с участием случайных графов

Предположим, у нас есть график nnnузлы. Мы хотели бы назначить каждому узлу либо+1+1+1 или −1−1−1, Назовите это конфигурациейσ∈{+1,−1}nσ∈{+1,−1}n\sigma \in \{+1,−1\}^n, Номер+1+1+1с, что мы должны назначить точно sss (отсюда количество −1−1−1с это n−sn−sn−s.) Учитывая конфигурацию σσ\sigmaСмотрим...

9
Существование «раскрасочных матриц»

Изменить: теперь есть дополнительный вопрос, связанный с этим сообщением. Определения Позволять ccc а также kkkбыть целыми числами. Мы используем обозначения[i]={1,2,...,i}[i]={1,2,...,i}[i] = \{1,2,...,i\}, c×cc×cc \times c матрица M=(mi,j)M=(mi,j)M = (m_{i,j}) Говорят, что ccc-До-kkkраскраска,...

9
Какова ожидаемая длина кратчайшего гамильтонова пути в случайно выбранных точках плоской сетки?

kkk различных точек выбираются случайным образом из сетки . (Очевидно, что и является заданным постоянным числом.) Из этих точек строится полный взвешенный граф таким образом, чтобы вес ребра между вершиной и вершиной равнялся манхэттенскому расстоянию двух вершин в исходной сетке. ,p×qp×qp\times...

9
Генерация интересных комбинаторных задач оптимизации

Я преподаю курс метаэвристики, и мне нужно создать интересные примеры классических комбинаторных задач для термина «проект». Давайте сосредоточимся на TSP. Мы занимаемся графиками размерности200200200и больше. Я попытался, конечно, сгенерировать график с матрицей затрат со значениями, взятыми из...

9
Понимание переговоров на конференциях и семинарах

Я аспирант из Индии. Мне очень интересно посещать семинары, конференции и приглашенных лекторов от известных профессоров. В конце беседы, как обычно, некоторые люди задают вопросы, а докладчик отвечает на них. Но моя проблема в том, что я не понимаю большинство вопросов и ответов. Даже если я задам...

9
Увеличение способности максимизировать минимальное сокращение

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

9
Случайные ограничения и связь с полным влиянием булевых функций

Скажем, у нас есть булева функция f:{−1,1}n→{−1,1}f:{−1,1}n→{−1,1}f:\{-1,1\}^n\rightarrow \{-1,1\} и мы применяем δδ\deltaслучайное ограничение на fff, Кроме того, скажем, что дерево решенийTTT это вычисляет fff сжимается до размера O(1)O(1)O(1)в результате случайного ограничения. Означает ли это,...

9
Известна ли сложность этой проблемы покрытия?

Позволять G = ( V, E)гзнак равно(В,Е)G=(V,E)быть графом Набор вершинИкс⊆ VИкс⊆ВX\subseteq Vназывается критическим, еслиИкс≠ ∅Икс≠∅X\neq\emptyset и нет вершины в В∖ XВ∖ИксV\setminus X смежна ровно с одной вершиной в ИксИксX, Проблема состоит в том, чтобы найти множество вершинS⊆ VS⊆ВS\subseteq V...

9
Число автоморфизмов графа для графа изоморфизма

Позволять GGG а также HHH быть двумя rrrрегулярные связные графы размера nnn, ПозволятьAAA быть набором перестановок PPP такой, что PGP−1=HPGP−1=HPGP^{-1}=H, ЕслиG=HG=HG=H тогда AAA это множество автоморфизмов GGG, Каков самый известный верхний предел размера AAA? Есть ли какие-либо результаты для...