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

10
Нахождение коротких и толстых путей

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

10
Обрезка сильно связанного орграфа

Учитывая сильно связанный орграф G со взвешенными ребрами, я хотел бы идентифицировать ребра, которые доказуемо не являются частью какого-либо минимального сильно связного подграфа (MSCS) группы G. Одним из способов нахождения таких ребер является модифицированный алгоритм Флойда-Варшалла....

10
Существует ли алгоритм полиномиального времени для решения изоморфизма графов для графов Делоне (конечных) гексагональных тесселяций?

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

10
Решетки проблемы

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

10
Перечисление всех пар непересекающихся путей

Учитывая , ориентированный граф , и две вершины . Пара простых путей от до является ребром, если они не разделяют ребро.G = ( V, E)гзнак равно(В,Е)G = (V,E)s , t ∈ Vs,T∈Вs,t \in Vп1, р2п1,п2p_1,p_2sssTTt Используя максимальный поток, легко определить, существует ли пара непересекающихся ребер от до...

10
Задача наименьшего расстояния с длиной как функции времени

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

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

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

10
В поисках пауков

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

10
Сортировка точек таким образом, чтобы минимальное евклидово расстояние между последовательными точками было бы максимальным

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

10
Соединение ячеек перестановками строк и столбцов в конечной сетке

Я хотел бы знать, изучалась ли ранее простая проблема и известно ли какое-либо решение. Пусть G - конечная (MxN) сетка, S - подмножество клеток G («крошки»). Говорят, что две крошки (локально) связаны, если их координаты отличаются не более чем на один (т. Е. Если они нарисованы в виде квадратов,...

10
Нахождение мин-макс вершинно-непересекающихся путей с общим источником на плоских графах

Для заданного невзвешенного плоского графа и набора пар вершин ( - константа) найдите непересекающихся вершин (кроме исходных) путей от до таких что длина самого длинного пути сведена к минимуму.( с , т1) , ... , ( s , тК)(s,T1),...,(s,TК)(s,t_1),\dots,(s,t_k)k ≥ 2К≥2k\ge2ККksssTяTяt_i Вопрос: есть...

10
Эффективный изоморфизм графов для аналогичных графовых запросов

Учитывая граф G1, G2 и G3, мы хотим выполнить тест F изоморфизма между G1 и G2, а также G1 и G3. Если G2 и G3 очень похожи, так что G3 формируется путем удаления одного узла и вставки одного узла из G2, и у нас есть результат F (G1, G2), можем ли мы вычислить F (G1, G3), не вычисляя его с нуля...

10
Простой путь на даге с задними краями

Какова сложность следующей задачи ( P? NP-hard?):∈∈\in Входные данные: направленный ациклический граф , множество обратных ребер и два отдельных узла и .E ′ ⊂ V × V s tD=(V,E)D=(V,E)D=(V,E)E′⊂V×VE′⊂V×VE'\subset V\times Vsssttt Вопрос: Пусть обозначает граф, образованный добавлением к ребер из ....

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

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

10
Нумерация подмножеств

Исправить . Для любого достаточно большого мы хотели бы пометить все подмножества размера точно натуральными числами из . Нам бы хотелось, чтобы эта маркировка удовлетворяла следующему свойству: есть множество целых чисел, stk≥5k≥5k\ge5nnn{1..n}{1..n}\{1..n\}n/kn/kn/k{1...T}{1...T}\{1...T\}SSS Если...

10
«Родственники» проблемы кратчайшего пути

Рассмотрим связный неориентированный граф с неотрицательными весами ребер и двумя выделенными вершинами s,ts,ts,t . Ниже приведены некоторые задачи на пути, которые имеют следующую форму: найдите путь s−ts−ts-t , чтобы некоторая функция весов ребер на пути была минимальной. В этом смысле все они...

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

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

10
Полнота охватывающих деревьев

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

10
Какие графовые проблемы являются

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

9
Проблема резервного копирования NP-завершена?

Является ли следующее решение задачи NP-завершенным: Пусть неориентированный граф и двумя целыми числами. Можно ли выбрать для каждой вершины ровно разных соседей, чтобы ни один узел не был выбран больше, чем раз.GGGb≤cb≤cb \le cGGGbbbccc Случай может быть решен для любого за полиномиальное время с...