Пусть - корневое двоичное дерево. Каждый путь от корня до листа имеет длину . Каждый узел всегда имеет левый и правый дочерние узлы, но возможно, что они одинаковы (поэтому всегда возможно путей). Размер ограничен . Узел с разными дочерними узлами называется ветвящимся узлом...
Есть много примеров в комбинаторике и информатике, где мы можем проанализировать теоретико-графическую проблему, но для ее гиперграфа у нас отсутствуют инструменты. Как вы думаете, почему проблемы с 3-равномерными гиперграфами часто становятся намного сложнее, чем с 2-равномерными графами? Каковы...
Сообщение связано с: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles Насколько далеко Lovasz связан с пропускной способностью регулярных графов с нулевой ошибкой? Есть ли примеры, когда известно, что оценка Ловаша не равна емкости регулярного графа с...
Для смешанного графа с ребрами E и дугами A найдите совпадение в E, которое минимизирует количество дуг в G / M , где G / M получается из G путем сжатия совпадающих вершин и удаления параллельные дуги.G=(V,E,A)G=(V,E,A)G=(V,E,A)EEEAAAEEEG/MG/MG/MG/MG/MG/MGGG Является ли (вариант решения) этой...
Я ищу полный текст результата клики Луны и Мозера 1965 г. О кликах в графах (существуют графы с числом максимальных клик, экспоненциальным по ). Платежная система моего университета не имеет доступа к конкретному журналу. (На самом деле, предварительный просмотр предоставляет первые несколько...
Контекст: мы рассматриваем только орграфы. Пусть CYCLE будет языком графов с циклом; это NL-полная проблема. Пусть HASEDGE будет языком графов с хотя бы одним ребром. Тогда не тривиально, CYCLE∪HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup \text{HASEDGE} больше не NL-трудно, в то время как...
Существует ли алгоритм полиномиального времени, чтобы найти - если он существует - остовный паук данного графа ? Паук - это дерево с не более чем одним узлом со степенью больше 2: я знаю, что различные условия степеней на (по существу, достаточно большие степени узлов) гарантируют существование...
Сложно ли приблизить приблизительное дробное хроматическое число на графах с ограниченными
Во время моей работы я столкнулся со следующей проблемой: Я пытаюсь найти -матрицу , для любого , со следующими свойствами:n×nn×nn \times n (0,1)(0,1)(0,1)MMMn>3n>3n > 3 Определитель четен.MMM Для любых непустых подмножеств с, Подматрица имеет нечетный детерминанту тогда и только тогда ,...
Определения Пусть ϵ>0ϵ>0\epsilon > 0 и пусть ddd , rrr и ggg - натуральные числа (при g>2r+1g>2r+1g > 2r+1 ). Пусть G=(V,E)G=(V,E)G = (V,E) простой регулярный неориентированный конечный граф с обхватом не менее .гdddggg Пусть быть общий порядок на .V≤≤\leVVV Для каждого пусть состоит из...
Я хотел бы знать, изучалась ли ранее простая проблема и известно ли какое-либо решение. Пусть G - конечная (MxN) сетка, S - подмножество клеток G («крошки»). Говорят, что две крошки (локально) связаны, если их координаты отличаются не более чем на один (т. Е. Если они нарисованы в виде квадратов,...
Пусть граф с (положительно) взвешенными ребрами. Я хочу определить диаграмму Вороного для набора узлов / сайтов S , чтобы связать с узлом v ∈ S подграф R ( v ) группы G, индуцированный всеми узлами строго ближе к v, чем к любому другому узлу в S , измеряя длина пути по сумме весов на дугах. R ( v )...
Доказательство сложности является основной областью теории вычислительной сложности. Конечная цель этой области состоит в том, чтобы доказать , то есть любой доказатель не может дать доказательство неудовлетворенности данной входной формулой. Nп≠ c o NпNп≠соNпNP\neq coNP Граф - это одна из...
Пусть . Мне нужно сгенерировать простые графы G обхвата g , чтобы множество всех g- циклов образовывало двойное ребро, покрывающее G (то есть каждое ребро делится ровно двумя g- циклами), и такое, чтобы пересечение любых двух g- циклы - это либо вершина, ребро, либо пустое. Сгенерированные графы...
Пусть наследственный класс графов. (Наследственный = замкнуто относительно взятия индуцированных подграфов.) Пусть обозначит множество -vertex графов в . Допустим, что содержит почти все графы, если доля всех вершинных графов, попадающих в приближается к 1 при...
Следующий вопрос связан с оптимальностью алгоритма динамического программирования Беллмана-Форда - кратчайшего пути (см. Этот пост для связи). Кроме того, положительный ответ будет означать, что минимальный размер монотонной недетерминированной программы ветвления для задачи STCONN равен . t Θ ( n...
Этот блог рассказывает о создании "извилистых маленьких лабиринтов" с помощью компьютера, перечисляя их. Перечисление может быть выполнено с использованием алгоритма Уилсона для получения UST , но я не помню формулы для того, сколько их там....
Покрывающее дерево графа называется деревом полноты, если множество его листьев индуцирует полный подграф в графе хоста. Учитывая граф и целое число , какова сложность определения, содержит ли дерево полноты с максимум листами?ггGККkггGККk Причина для того, чтобы задать этот вопрос, состоит в том,...
Учитывая направленный граф, мы хотим решить, содержит ли он направленный цикл четной длины. В этой статье 1997 года, написанной YUSTER и ZWICK, утверждается, что проблема не в том, что она находится в а также в том, что она не является N P -полной.ппPNпNпNP Есть ли какой-либо недавний результат,...
Существуют ли классы графов, для которых ширина дерева ограничена сверху функцией числа клика , т.е. ?tw(G)tw(G)tw(G)ω(G)ω(G)\omega(G)tw(G)≤f(ω(G))tw(G)≤f(ω(G))tw(G)\leq f(\omega(G)) Например, это классический факт, что для любого хордального графа мы имеем . Таким образом, классы, связанные с...