Рассуждая немного об этом вопросе , я попытался определить все различные причины, по которым граф может не быть k раскрашиваемым. Это единственные две причины, которые я смог определить до сих пор:G=(VG,EG)G=(VG,EG)G = (V_G,E_G)kkk содержит клику размером k + 1 . Это очевидная причина.GGGk+1k+1k+1...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Пусть 0≤p≤10≤p≤10\le p\le 1 и рассмотрим решение задачи CLIQUE Ввод: целое числоpp_p sss , граф GGG с ttt вершинами и края Вопрос: действительно содержит клику по крайней мере вершинами?⌈p(t2)⌉⌈p(t2)⌉\lceil p\binom{t}{2} \rceil GGGsss Экземпляр CLIQUE содержит пропорцию от всех возможных ребер....
Проблема цикла заключается в следующем:Кkk Экземпляр: неориентированный граф с n вершинами и до ( nграммGGNnn края.( н2)(n2)n \choose 2 Вопрос: существует ли (правильный) цикл в G ?КkkграммGG Предыстория: для любого фиксированного мы можем решить цикл за времени.2 k O ( n 2 )Кkk2 к2k2kO (...
В простой форме: Может ли двусторонний конечный автомат распознавать вершинные графы, содержащие треугольник с состояниями?vvvo(v3)o(v3)o(v^3) Детали Здесь представляют интерес графы с вершинами, закодированные с использованием последовательности ребер, причем каждое ребро представляет собой пару...
Этот вопрос мотивирован вопросом MathOverflow Пэна Чжана . Валиант показал, что подсчет максимальных клик в общем графе является # P-полным, но что если мы ограничимся графами несопоставимости (т. Е. Мы хотим подсчитать максимальные антицепи в конечном множестве)? Этот вопрос кажется достаточно...
Проблема разбиения с 3-мя кликами - это проблема определения , можно ли разбить вершины графа, скажем, , на 3 клики. Эта проблема является NP-трудной из-за простого сокращения проблемы 3-окрашиваемости. Нетрудно видеть, что ответ на эту проблему прост, когда diam ( G ) = 1 или diam ( G ) > 5 ....
Я ищу полный текст результата клики Луны и Мозера 1965 г. О кликах в графах (существуют графы с числом максимальных клик, экспоненциальным по ). Платежная система моего университета не имеет доступа к конкретному журналу. (На самом деле, предварительный просмотр предоставляет первые несколько...
Для данного семейства не более подмножеств . Замыкание объединения другого набор семейство , содержащий каждый набор , который можно построить, взяв объединение 1 или более множеств в . Byмы обозначим число множеств в . n { 1 , 2 , … , n } F C F | C | СFF\mathcal FNNn{ 1 , 2 , … , n }{1,2,...,N}\{...
Я заинтересован в уменьшении клика до SAT, не делая экземпляр намного больше.kkk Клика находится в NP, поэтому ее можно уменьшить до SAT, используя логарифмическое пространство. Простое сокращение учебника Garey / Johnson увеличивает размер экземпляра до кубического размера. Тем не менее, Клик...
Я читаю старую статью MC Golumbic о графиках EPT (пересечение ребер в дереве). В статье показано, что число максимальных кликов экземпляра графа EPT является полиномиальным. Он приходит к выводу, что если оракул сообщает, что графггG является графиком EPT, то можно найти максимальную клику с...