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

17
Свойства случайно ориентированных графов с фиксированной степенью выхода

Меня интересуют свойства случайных ориентированных графов с фиксированной степенью ddd . Я представляю модель случайного графа, где каждая вершина выбирает d соседей (скажем, с заменой) uar Вопрос : Известно ли что-нибудь о стационарном времени распределения и перемешивания случайных блужданий на...

17
Связность графов удалением ребер и вершин

Будем говорить , что граф является ( , б ) связным , если удаление любых через вершины и любые б ребер из G листьев всегда связного графа. Например, k- связный граф, согласно стандартному определению, ( k - 1 , 0 ) -связный, согласно новому определению. Существует ли алгоритм полиномиальное время ,...

17
Классы графов, в которых задачи о гамильтоновом цикле и гамильтоновом пути имеют разную сложность

При поиске Информационной системы о классах графов и их включениях я обнаружил несколько классов графов, для которых задача о гамильтоновом цикле NP-полна, а сложность задач о гамильтоновом пути НЕ известна. Некоторые из этих классов представляют собой двудольные графы максимальной степени 3,...

17
Геометрическая картина за квантовыми экспандерами

(также спрашивается здесь , без ответов) -квантовый расширитель является распределение над унитарной группой со свойством , что: а) , b) , где \ mu_H - мера Хаара. Если вместо распределений по унитарным мы рассмотрим распределения по матрицам перестановок, нетрудно увидеть, что мы восстанавливаем...

17
Наборы степеней для линейных графиков расширения

Линейное расширение из ч.у.м. является линейным порядком на элементах , такие , что в влечет в для всех .P P x ≤ y P x ≤ y L x , y ∈ PLLLPP\mathcal{P}PP\mathcal{P}x≤yx≤yx \leq yPP\mathcal{P}x≤yx≤yx \leq yLLLx,y∈Px,y∈Px,y\in\mathcal{P} Линейное расширение граф представляет собой график , на...

17
Время покрытия ориентированных графов

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

17
Нежное введение в изоморфизм графов для ограниченных валансных графов

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

17
Трудные задачи для графов высшего рода

Планарные графы имеют род ноль. Графы, встраиваемые в тор, имеют род не более 1. Мой вопрос прост: Есть ли какие-нибудь проблемы, которые полиномиально разрешимы на плоских графах, но NP-трудны на графах рода один? В более общем смысле, существуют ли проблемы, которые полиномиально разрешимы на...

17
Запрещенные миноры для графов ограниченной ширины

Этот вопрос похож на один из моих предыдущих вопросов. Известно, что является запрещенным минором для графов с шириной не более t .Kt+2Kt+2K_{t+2}ttt Существует ли красиво построенное, параметризованное, бесконечное семейство графов (кроме полных графов и сеточных графов), которые являются...

17
Обобщение локально ограниченных графов ширины

Известен ли следующий класс графов в литературе? Класс графов параметризуется натуральными числами и и содержит каждый граф такой, что для каждой вершины подграф индуцируется на всех вершинах на расстоянии не более от в имеет длину не более .dddTTtG = ( V, E)граммзнак равно(В,Е)G=(V,E)v ∈ Vv∈Вv\in...

16
Сложность распознавания вершинно-транзитивных графов

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

16
NP-сложность проблемы разбиения графа?

Меня интересует эта проблема: учитывая неориентированный граф , существует ли разбиение G на графы G 1 ( E 1 , V 1 ) и G 2 ( E 2 , V 2 ), такие что G 1 а G 2 изоморфны?G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Здесь разбивается на два...

16
Чувствительность свойств графика

В [1] Turan показывает, что чувствительность (называемая в статье «критической сложностью») свойства графа строго больше, чем гдеm- количество вершин в графе. Он продолжает предполагать, что любое нетривиальное свойство графа имеет чувствительность≥m-1. Он упоминает, что это было проверено дляm≤5....

16
Прибавление разложения дерева минимальной ширины за полиномиальное время

Как известно, древовидная декомпозиция графа состоит из дерева со связанным мешком для каждой вершины , которое удовлетворяет следующим условиям:T T v ⊆ V ( G ) v ∈ V ( T )GGGTTTTv⊆V(G)Tv⊆V(G)T_v \subseteq V(G)v∈V(T)v∈V(T)v \in V(T) Каждая вершина происходит в некотором мешке T .GGGTTT Для каждого...

16
Почему идеальные графики называются идеальными?

Извините, если это наивный вопрос, но я не смог найти оправдания ни в одном из основных учебников, таких как Бонди-Мёрти, Дистел или Уэст. У совершенных графиков есть много прекрасных свойств, но какова единственная причина, по которой их называют идеальными? Или это просто эстетическое...

16
Какой самый быстрый детерминистический алгоритм для достижения динамического орграфа без удаления ребер?

Каков наилучший детерминированный результат для поддержания динамического транзитивного замыкания в ориентированном графе только с вставкой ребер? Я читал некоторые статьи по проблеме динамического транзитивного замыкания с вставкой и удалением ребер. Однако, есть ли лучшие алгоритмы для этого...

16
Сильно регулярный граф и GI-полнота

Не известно , если изоморфизм графов (GI) для сильно регулярных графов (SRGS) в P . Есть ли намеки на то, что это может или не может быть GI- Complete? Есть ли сильные последствия в таких случаях? (Аналогично убеждению, что GI не может быть...

16
Представление неплоских графов с перекрывающимися кругами

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

16
Нахождение k кратчайших путей с помощью алгоритма Эппштейна

Я пытаюсь выяснить, как граф путей соответствии с алгоритмом Эппштейна в этой статье работает, и как я могу восстановить k кратчайших путей от s до t с соответствующей конструкцией кучи H ( G ) .P(G)P(G)P(G)kkkssstttH(G)H(G)H(G) Слишком далеко: содержит все ребраоставляя вершину V в графе G ,...