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

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

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

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
Запрещенные миноры для графов с ограниченным родом

Хорошо известно, что K5K5K_5 и K3,3K3,3K_{3,3} являются запрещенными минорами для плоских графов. Существуют сотни запрещенных миноров для графов, встраиваемых в тор. Количество запрещенных миноров для графов, встраиваемых на поверхность рода g, является экспоненциальной функцией от g . Мой вопрос...

16
Ссылка на алгоритм тестирования ацикличности смешанного графа?

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

15
Подграф изоморфизма с деревом

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

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

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

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

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

15
Графовые разложения для объединения «локальных» функций маркировки вершин

ΣИксΠi j ∈ Eе( хя, хJ)∑x∏ij∈Ef(xi,xj)\sum_x \prod_{ij \in E} f(x_i,x_j)МаксимумИксΠi j ∈ Eе( хя, хJ)maxx∏ij∈Ef(xi,xj)\max_x \prod_{ij \in E} f(x_i,x_j) Где max или сумма берется по всем меткам VVV , произведение берется по всем ребрам ЕEE для графа G = { V, E}G={V,E}G=\{V,E\} а еff - произвольная...

15
Несовершенный изоморфизм подграфа

Рассмотрим следующую проблему: учитывая граф запросов G=(V,E)G=(V,E)G = (V, E) и опорный граф , мы хотим найти инъективное отображение которое минимизирует количество ребра такие, что . Это обобщение проблемы изоморфизма подграфа, где мы позволяем подграфам быть изоморфными вплоть до нескольких...

15
Рекомендации по модульной декомпозиции

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

15
Модульная декомпозиция и клик-ширина

Я пытаюсь понять некоторые понятия о модульной декомпозиции и графах ширины клика . В этой статье («О P4-аккуратных графах») есть доказательство того, как решать задачи оптимизации, такие как число кликов или хроматическое число, с использованием модульной декомпозиции. Решение этих проблем путем...

15
Известна ли эта плотная версия алгоритма Крускала?

Около года назад мы с другом подумали, как реализовать алгоритм Крускала для плотных графов лучше, чем обычная граница (без учета предварительно отсортированных ребер). В частности, мы достигаем во всех случаях, аналогично Prim, когда реализованы с использованием матриц смежности.O ( м журналм...

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

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

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

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

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

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

15
Рисование графиков с несколькими «острыми» вершинами?

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