Вопросы с тегом «graph-theory»

11
Сложность уникального st-Connectivity

Я хотел бы знать, может ли быть решена следующая проблема в (недетерминированное пространство журнала):NLNL\mathsf{NL} Для ориентированного графа с двумя выделенными вершинами s и t существует ли единственный путь из s в t в G ?s tGGGssstttт гssstttGGG Я чувствую, что он, вероятно, находится в...

11
Оптимальная предварительная обработка для определенных типов запросов

Предположим, у нас есть полугруппа с элементами . Наша цель - вычислить произведения .S = { s 1 , s 2 , … , s n } s i ∘ s i + 1 ∘ ⋯ ∘ s j( S, ∘ )(S,∘)(S,\circ)S= { с1, с2, ... , SN}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesя∘ ся + 1∘ ⋯ ∘ sJsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ \cdots\circ s_j В...

11
Обобщение теоремы Дилворта для помеченных DAG

Антицепь в DAG представляет собой подмножество ⊆ V вершин, попарно недостижим, а именно, нет v ≠ v ' ∈ таким образом, что v достижима из V ' в Е . Из теоремы Дилворта в теории частичного порядка известно, что если DAG не имеет антицепи размера k ∈ N , то она может быть разложена в объединение не...

11
3-Clique Partition для графиков фиксированного диаметра

Проблема разбиения с 3-мя кликами - это проблема определения , можно ли разбить вершины графа, скажем, , на 3 клики. Эта проблема является NP-трудной из-за простого сокращения проблемы 3-окрашиваемости. Нетрудно видеть, что ответ на эту проблему прост, когда diam ( G ) = 1 или diam ( G ) > 5 ....

11
Нахождение двойственного графа

Согласно книге «Топологическая теория графов» Гросса и Такера, учитывая клеточное вложение графа на поверхность (под «поверхностью» я подразумеваю здесь сферу с некоторыми ручками , а ниже S n относится к сфере с ровно n ручками), можно определить двойной мультиграф, рассматривая грани исходного...

11
Как генерировать графы с известным оптимальным покрытием вершин

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

11
Свойства MSO, планарные и неосновные графы

Теорема Курселя гласит, что любое свойство графа, определяемое в монадической логике второго порядка, может быть определено за линейное время на графах ограниченной длины дерева . Это одна из самых известных алгоритмических мета-теорем. Основываясь на теореме Курселя, я высказал следующую гипотезу:...

11
Путаница в том, что сокращение числа вершин охватывает количество циклов

Это смущает меня. Один простой случай подсчета - это когда проблема решения находится в а решений нет.PPP Лекция показывает, что проблема подсчета числа совершенных совпадений в двудольном графе (эквивалентно подсчету числа циклов в ориентированном графе) является -полной.#P#P\#P Они дают...

11
Приближаемость проблемы рода

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

11
Неправильная плоская окраска с размером монохроматического компонента

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

11
Сложность вычисления среднего расстояния графа

Пусть - среднее расстояние связного графаG .ad(G)ad(G)\rm{ad}(G)G.G.G. Одним из способов вычисления является суммирование элементов матрицы расстояний и соответствующее масштабирование суммы.D ( G ) , Gad(G)ad(G)\rm{ad}(G)D(G),D(G),D(G),GGG Если выходной граф представляет собой дерево, то известно,...

11
История и состояние проблемы сопоставления графиков

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

11
Для каких семейств графов это обобщенная география в ?

Как упомянул @Marzio, следующая игра называется Generalized Geography . Для графа и начальной вершины игра определяется следующим образом:G = ( V, E)гзнак равно(В,Е)G=(V,E)v ∈ Vv∈Вv \in V На каждом ходу (чередуются два игрока), игрок выбирает , и тогда происходит следующее:u ∈ N( v )U∈N(v)u\in N(v)...

11
Графовые классы, для которых диаметр может быть вычислен за линейное время

Напомним, диаметр графа является длина самой длинной кратчайшему пути в . Для данного графа очевидный алгоритм вычисления решает проблему кратчайшего пути всех пар (APSP) и возвращает длину самого длинного найденного пути.G диам ( G )GGGGGGdiam(G)diam(G)\text{diam}(G) Известно, что задача APSP...

11
Социальные сети, как правило, хорошие экспандеры?

Меня интересуют комбинаторные свойства социальных сетей в виде графиков. Люди смотрели на такие вещи, как распределение степеней, коэффициент кластеризации и сжимаемость этих графиков. Один основной вопрос: действительно ли эти графики являются хорошими графами расширителей? Кто-нибудь проверял,...

10
ПСУ с неограниченной дробной шириной гипердерева

На SODA 2006 работа Мартина Грохе и D sharp Нила Маркса «Решение ограничений с помощью дробных краевых покрытий» ( цитирование ACM ) показала, что для класса гиперграфов H с ограниченной дробной шириной гипердерева CSP ( H ) \ in ПТИМ .a´a´\acute{\rm a}HHHHHH∈PTIME∈PTIME\in PTIME Определения и т....

10
Интересные функции на графиках, которые можно эффективно максимизировать.

Скажем, у меня есть взвешенный граф такой, что является весовой функцией - обратите внимание, что допустимы отрицательные веса.w : E → [ - 1 , 1 ]G = ( V, E, ш )гзнак равно(В,Е,вес)G = (V,E,w)W : E→ [ - 1 , 1 ]вес:Е→[-1,1]w:E\rightarrow [-1,1] Скажем , что определяет свойство любого подмножества...

10
Может ли такая матрица существовать?

Во время моей работы я столкнулся со следующей проблемой: Я пытаюсь найти -матрицу , для любого , со следующими свойствами:n×nn×nn \times n (0,1)(0,1)(0,1)MMMn>3n>3n > 3 Определитель четен.MMM Для любых непустых подмножеств с, Подматрица имеет нечетный детерминанту тогда и только тогда ,...

10
Регулярный граф с высоким обхватом с «локально однородным» общим порядком на узлах

Определения Пусть ϵ>0ϵ>0\epsilon > 0 и пусть ddd , rrr и ggg - натуральные числа (при g>2r+1g>2r+1g > 2r+1 ). Пусть G=(V,E)G=(V,E)G = (V,E) простой регулярный неориентированный конечный граф с обхватом не менее .гdddggg Пусть быть общий порядок на .V≤≤\leVVV Для каждого пусть состоит из...