У меня есть граф который состоит только из звездных графов. Звездный граф состоит из одного центрального узла, имеющего ребра для каждого другого узла в нем. Пусть быть разные звезды графики различных размеров , которые присутствуют в . Мы называем множество всех узлов , которые являются центрами в...
При введении модульной декомпозиции графа большинство авторов используют граф из 11 вершин, который я копирую из википедии. Вопрос в том, кто является (являются) его первоначальным разработчиком. (Я не спрашиваю, кто нарисовал этот график для Википедии, но его первоначальный источник.) Страница...
Одной из основных проблем при перечислении графов является определение «формы» графа, например, класса изоморфизма любого конкретного графа. Я полностью осознаю, что каждый граф может быть представлен в виде симметричной матрицы. Однако, чтобы получить его форму, вам понадобится набор перестановок...
Определите сетку в 3D как связанную совокупность тетраэдров с непересекающимися внутренностями (поэтому тетраэдры имеют только k-грани, k ≤ 2К≤2k \le 2). Учитывая произвольный граф, есть ли эффективная процедура для проверки, если он может быть встроен в виде сетки? Здесь вложение - это отображение...
Я хотел бы ограничить мощность множества графов единичных дисков с NNNВершины. Известно, что проверка того, является ли граф членом этого набора, является NP-сложной задачей. Приводит ли это к какой-либо нижней границе мощности, предполагая, что P≠≠\neq NP? Например, предположим, что есть порядок...
Я хотел выяснить, каковы некоторые применения SGT в области теории информации и кодирования и, возможно, коммуникаций. Самое связанное, что приходит на ум, это работа над кодами расширителей. Майкл Сипсер и Даниэль Спилман, «Коды расширителей», IEEE Transactions по теории информации, том 42, № 6,...
Мой вопрос немного расплывчатый. Мне было интересно, если (и как), мы можем применить понятие ширины дерева для задач упаковки в графах. Я был бы счастлив с любым пониманием или ссылками прошлой исследовательской работы на этом (предполагая, что они - некоторая связь)....
Есть ли какие-либо известные результаты о сложности поиска разделителя (любого размера), удовлетворяющего заданному свойству? Я знаю, что разделитель кликов легко найти (за полиномиальное время), а также знаю, что во многих работах рассматривается проблема поиска небольших разделителей или...
В предыдущем вопросе « Параметризованный алгоритм поиска бикликов» я поинтересовался, существуют ли быстрые параметризованные алгоритмы для нахождения -биклика в графе вершин, и узнал, что он открыт, если он равен FPT относительно . То же самое верно и для подсчета в -bicliques, или известно , что...
Предположим, у нас есть график nnnузлы. Мы хотели бы назначить каждому узлу либо+1+1+1 или −1−1−1, Назовите это конфигурациейσ∈{+1,−1}nσ∈{+1,−1}n\sigma \in \{+1,−1\}^n, Номер+1+1+1с, что мы должны назначить точно sss (отсюда количество −1−1−1с это n−sn−sn−s.) Учитывая конфигурацию σσ\sigmaСмотрим...
kkk различных точек выбираются случайным образом из сетки . (Очевидно, что и является заданным постоянным числом.) Из этих точек строится полный взвешенный граф таким образом, чтобы вес ребра между вершиной и вершиной равнялся манхэттенскому расстоянию двух вершин в исходной сетке. ,p×qp×qp\times...
Я столкнулся с этой проблемой соответствия, для которой я не могу записать алгоритм полиномиального времени. Пусть - полные взвешенные графы с множествами вершин и соответственно, где . Кроме того, пусть и - весовые функции на ребрах и соответственно.P,QP,QP,...
Рассмотрим граф со всеми ребрами, имеющими единичную емкость. Можно найти минимальное сокращение за полиномиальное время. Предположим, мне разрешено увеличивать емкость любых ребер до бесконечности (эквивалентно объединению узлов по обе стороны ребра). Каков оптимальный способ выбора оптимального...
Я пытаюсь найти график с этими свойствами для моих исследований, но, к сожалению, я не могу найти такой график. Кто-нибудь знает, существует ли этот граф, или почему невозможно...
Я решаю проблему «смешивания» наборов перекрывающихся изображений. Эти наборы могут быть представлены неориентированным взвешенным графом, таким как этот: Каждый узел представляет изображение. Перекрывающиеся изображения связаны ребром. Вес края представляет размер области перекрытия ( смешивание...
Сколько циклов СКСКC_k ( k ≥ 3 )(К≥3)(k \geq 3) есть в NNn граф вершин такой, что у графа нет цикла СмСмC_m ( м > к )(м>К)(m>k), Например N = 5Nзнак равно5n=5, к =3Кзнак равно3k=3тогда граф будет иметь не более двух С3С3C_3так что ггG не будет иметь СК( к > 3 ) .СК(К>3),C_k (k > 3). Я...
Предположим, что у меня есть пPP наборы с элементами, взятыми из рrrвозможные. Каждый набор имеет размерNnn (n <
Не проще ли проверить транзитивность орграфа, чем (с точки зрения асимптотической сложности) взять транзитивное замыкание орграфа? Знаем ли мы какую-либо нижнюю границу лучше, чемΩ(n2)Ω(n2)\Omega(n^2) определить, является ли орграф транзитивным или...
Здесь было несколько вопросов ( 1 , 2 , 3 ) о транзитивном завершении, которые заставили меня задуматься, возможно ли что-то подобное: Предположим, мы получили входной ориентированный граф GGG и хотел бы ответить на запросы типа "(u,v)∈G+(u,v)∈G+(u,v)\in G^+? ", т.е. спрашивает, существует ли ребро...
Я ищу ссылки на следующую задачу: с учетом целых чисел и перечислить все неизоморфные плоские графы по вершинам и ширине дерева . Меня интересуют как теоретические, так и практические результаты, но в основном практические алгоритмы, которые можно кодировать и запускать для максимально больших...