Для плоского вложения плоского графа на плоскость с прямыми ребрами определите вершину как острую вершину, если максимальный угол между двумя последовательными ребрами вокруг нее больше 180. Или, другими словами, если существует линия, проходящая через это вершина вложения так, что все ребра,...
Это дополнительный вопрос к этому вопросу о бесконечных графах. Ответы и комментарии к этому списку объектов и ситуаций, которые естественным образом моделируются бесконечными графами. Но есть также многочисленные теоремы о бесконечных графах (см. Главу 8 в книге Дистеля), из которых, например,...
Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...
Связанная проблема: Теорема Веблена утверждает, что «граф допускает разложение цикла тогда и только тогда, когда оно четное». Циклы являются ребрами непересекающимися, но не обязательно узлы непересекающимися. Другими словами, «множество ребер графа можно разбить на циклы тогда и только тогда,...
Планарные графы -бесплатно. Такие графики могут быть разложены на трехсвязные компоненты, которые, как известно, являются либо плоскими, либо компонентами K 5 .К3 , 3К3,3K_{3,3}К5К5K_5 Есть ли такая «хорошая» декомпозиция графов рода один? В своей основополагающей работе над минорами графов...
Около года назад мы с другом подумали, как реализовать алгоритм Крускала для плотных графов лучше, чем обычная граница (без учета предварительно отсортированных ребер). В частности, мы достигаем во всех случаях, аналогично Prim, когда реализованы с использованием матриц смежности.O ( м журналм...
1-тусклый алгоритм Вейсфейлер-Леман (WL) широко известен как каноническая маркировка или алгоритм , цвета уточнения. Это работает следующим образом: Начальная раскраска равномерна, C 0 ( v ) = 1 для всех вершин v ∈ V ( G ) ∪ V ( H ) .С0С0C_0С0( v ) = 1С0(v)знак равно1C_0(v) = 1v ∈ V( G ) ∪ V(...
Мы рассматриваем DAG (ориентированные ациклические графы) с одним исходным узлом sss и одним целевым узлом ttt ; допускаются параллельные ребра, соединяющие одну и ту же пару вершин. - разрез представляет собой набор ребер, удаление уничтожает все - пути по длиннее , чем ; более короткие - пути, а...
Я пересматриваю некоторую криптографическую модель. Чтобы показать его неадекватность, я разработал искусственный протокол, основанный на изоморфизме графа. Это «обычное дело» (еще спорный!) Предположить существование BPP алгоритмов способны генерировать «жесткие экземпляры проблемы Изоморфизма...
Я написал реализацию алгоритма Куна-Мункреса для задачи идеального соответствия двудольных с минимальным весом на основе лекционных заметок, которые я нашел здесь и там в Интернете. Это работает очень хорошо, даже на тысячах вершин. И я согласен, что теория, стоящая за этим, действительно...
Мы знаем, что алгоритм mincut Каргера может быть использован, чтобы доказать (неконструктивно), что максимальное число возможных срезов, которые может иметь граф, равно (n2)(n2)n \choose 2 . Мне было интересно, можем ли мы как-то доказать эту идентичность, дав биективное (довольно инъективное)...
Рассмотрим # P-полную задачу подсчета числа покрытий вершин данного графа .G=(V,E)G=(V,E)G = (V, E) Я хотел бы знать, есть ли какой-либо результат, показывающий, как сложность такой проблемы изменяется с некоторым параметром (например, d = | E |GGG).d=|E||V|d=|E||V|d = \frac{|E|}{|V|} У меня такое...
Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...
Самая длинная проблема на пути - NP-сложная. (Типичное?) Доказательство опирается на редукцию задачи о гамильтоновом пути (которая является NP-полной). Обратите внимание, что здесь путь считается простым (node-). То есть ни одна вершина не может встречаться более одного раза в пути. Очевидно, что...
Что-нибудь известно о следующей проблеме? Имеет ли это смысл вообще? Как это называется? Это тривиально эквивалентно какой-то другой проблеме? Что такое сложность времени? Для заданного неориентированного (общего / плоского / ограниченной степени / и т. Д.) Графа G = (V, E) найдите максимальное...
Учитывая неориентированный регулярный граф , какова связь между его диаметром - определенным как наибольшее расстояние между двумя узлами - и его проводимостью, определенной как где e (S, S ^ c) - количество ребер, пересекающих S и S ^ c...
Предположим, что мы соединяем точки используя набор неориентированных ребер E , так что либо связано с , либо связано с , независимо и равномерно случайным образом для всех .V=Z2V=Z2V = \mathbb{Z}^2EEE( i + 1 , j + 1 )(i,j)(i,j)(i, j)(i+1,j+1)(i+1,j+1)(i + 1, j + 1)( i , j + 1 ) i ,...
GI и проблема узлов являются проблемой определения структурной эквивалентности математических объектов. Есть ли какие-либо результаты установления связей между ними? Хорошие связи проблемы узлов со статистической физикой были изучены с помощью полиномов узлов , есть ли похожие результаты для ?G...
Меня интересуют графики по вершинам, которые можно получить с помощью следующего процесса.nnn Начнем с произвольного графа на вершинах. Пометьте все вершины в как неиспользуемые .GGGGk≤nk≤nk\le nGGG Производят новый граф , добавив новую вершину , который соединен с одним или более неиспользованных...
Этот вопрос связан с одним из моих предыдущих вопросов, NP-трудными задачами на деревьях . Я ищу проблемы, которые являются P-полными на деревьях.