Рассмотрим следующую проблему. Вход: неориентированный граф . Вывод: граф H, который является младшим из G с самой высокой граничной плотностью среди всех миноров G , то есть с самым высоким отношением | E ( H ) | / | V ( H ) | ,G=(V,E)G=(V,E)G=(V,E)HHHGGGGGG|E(H)|/|V(H)||E(H)|/|V(H)||E(H)|/|V(H)|...
Доказательство Омер Рейнгольда , что дает алгоритм USTCON (В U ndirected граф со специальными вершинами S и т , они Con подсоединены?) , Используя только logspace. Основная идея состоит в том, чтобы построить график расширителя из исходного графика, а затем выполнить обход в графике расширителя....
Я ищу реализацию алгоритма для вычисления ширины пути графа. Хорошо известно, что вычисление ширины пути эквивалентно вычислению числа поиска узла, числа разделения вершин или толщины интервала графа. Алгоритм не должен быть очень быстрым; Я хочу запустить его на графиках не более 20 вершин. Мне...
В главе 1 книги «Вероятностный метод» Алона и Спенсера упоминается следующая проблема: Учитывая граф , решите, является ли его граничная связность по крайней мере или нет.GGGn/2n/2n/2 Автор упоминает о существовании алгоритма от Matula и улучшает его до...
Меня интересует сложность задачи о доминирующем множестве (DSP) в некоторых конкретных классах графов, которые являются подклассами хордовых графов . Граф является неориентированным графом путей, если он является графом пересечения вершин семейства путей в некотором неориентированном дереве. Пусть...
Один из моих друзей спрашивает меня о следующей проблеме планирования на дереве. Я считаю, что это очень чисто и интересно. Есть ли какая-либо ссылка на это? Проблема: Существует дерево , каждое ребро имеет симметричную стоимость перемещения 1 . Для каждой вершины v i есть задача, которую...
Известно ли, что задача множества вершин обратной связи на неориентированных плоских графах ограниченной степени является трудной?Н
Для ориентированного циклического графа, где вес каждого ребра может быть отрицательным, концепция «кратчайшего пути» имеет смысл, только если нет отрицательных циклов, и в этом случае вы можете применить алгоритм Беллмана-Форда. Тем не менее, я заинтересован в поиске кратчайшего пути между двумя...
Мы дали направленный ациклический граф с номером , связанным с каждой вершиной ( г : V → N ), и целевым числом Т ∈ N .G=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N}T∈NT∈NT\in \mathbb{N} Проблема DAG подмножества суммы (может существовать под другим именем, ссылка будет большой) спрашивает , есть...
Treewidth и pathwidth являются популярными параметрами, измеряющими близость графа к дереву или пути, соответственно. В самом деле, кажется, что древовидная ширина настолько популярна, что во многих статьях, книгах и конспектах лекций, которые (даже очень осторожно) знакомят с алгоритмическими...
Разложение дерева сложно в худшем случае, но жадный метод кажется почти оптимальным в небольших реальных сетях. Известно ли что-нибудь о сложности разложения дерева «типичного» экземпляра некоторого класса графов? Есть ли пример семейства графов, где жадные методы разложения дерева плохо работают?...
Этот вопрос похож на NP-сложные задачи на деревьях : Существует большое количество NP-полных задач, которые можно отследить на рефератах . Есть ли какие-либо известные проблемы, которые остаются NP-полными, если они ограничены Cographs? Чтобы быть более точным, меня интересуют примеры, в которых...
Я ищу хороший справочник для кратчайших путей узкого места. В частности, учитывая вершины s и t в неориентированном графе с весом ребер, вы хотите кратчайший путь от s до t, где длина пути - это максимальное ребро на этом пути. Это можно решить за время O (n + m), найдя средний вес ребра и...
Пусть x1,…,xnx1,…,xnx_1, \ldots, x_n - точки на плоскости R2R2\mathbb{R}^2 . Рассмотрим полный граф с точками в виде вершин и весами ребер . Вы всегда можете найти вес, который составляет не менее \ 2 2 от общего веса? Если нет, то какая константа должна заменить \ frac 2 3 ?2∥xi−xj∥2‖xi−xj‖2\|x_i...
Свойство графа называется наследственным, если оно замкнуто относительно удаления вершин (т. Е. Все индуцированные подграфы наследуют это свойство). Свойство графа называется аддитивным, если оно замкнуто относительно взятия непересекающихся объединений. Нетрудно найти свойства, которые являются...
В моей работе возникает следующая проблема: Существует ли известный алгоритм, который аппроксимирует хроматическое число графа без независимого набора порядка 65? (Таким образом, альфа (G) <= 64 известна, а | V | / 64 - тривиальная нижняя, | V | тривиальная верхняя граница. Но существуют ли...
Для данного графа нам нужно найти мощность наибольшего множества вершин, чтобы каждая из них присутствовала в каждом максимально возможном сопоставлении.граммGG Есть ли решение помимо очевидного удаления каждой вершины и найти максимальное совпадение, чтобы увидеть, как оно...
Были предприняты некоторые попытки решить проблему изоморфизма графов с помощью квантового случайного блуждания жестких бозонов (симметричное, но без двойного заполнения). Симметричная степень матрицы смежности, которая казалась многообещающей, оказалась неполной для общих графов в этой статье...
В известном контрпримере для изоморфизма графа с помощью метода Вейсфейлера-Лемана (WL) в этой статье Кай, Фюрер и Иммерман построили следующий гаджет . Они строят граф определяемый какXk=(Vk,Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) Vk=Ak∪Bk∪Mk where Ak={ai∣1≤i≤k},Bk={bi∣1≤i≤k}, and Mk={mS∣S⊆{1,2,…,k}, |S| is...
Я ищу небольшой граф которого векторное хроматическое число меньше хроматического числа,