Дано это даг. Вы хотите пометить каждый узел тем, сколько узлов доступно из него. - тривиальная верхняя граница; является нижней границей (я думаю). Есть ли лучший алгоритм? Есть ли основания полагать, что нижняя граница может быть улучшена (связана: что именно известно о нижних границах для...
Рассмотрим электрическую сеть, смоделированную как планарный граф G, где каждое ребро представляет собой резистор 1 Ом. Как быстро мы можем вычислить точное эффективное сопротивление между двумя вершинами в G? Эквивалентно, как быстро мы можем вычислить точный ток, протекающий вдоль каждого края,...
Время коммутирования в связанном графе определяется как ожидаемое количество шагов в случайном блуждании, начиная с , до посещения узла и затем достижения узла снова. В основном это сумма двух времен удара и .G = ( V, E)гзнак равно(В,Е)G=(V,E)яяiJJjяяiЧАС( я , j )ЧАС(я,J)H(i,j)ЧАС( J , I...
Кубические графы - это графы, в которых каждая вершина имеет степень 3. Они были тщательно изучены, и я знаю, что некоторые NP-сложные задачи остаются NP-трудными, даже если они ограничены подклассами кубических графов, но некоторые другие становятся проще. Суперкласс кубических графов - это класс...
все знают, что существует много проблем с решениями, которые являются NP-сложными на общих графах, но меня интересуют проблемы, которые даже NP-сложны, когда лежащий в основе граф является путем. Итак, вы можете помочь мне собрать такие проблемы? Я уже нашел связанный вопрос о NP-трудных проблемах...
Я ищу неориентированные, невзвешенные связные графы , в которых для каждой пары существует уникальный путь который реализует расстояние ,G=(V,E)G=(V,E)G=(V,E)u,v∈Vu,v∈Vu,v \in Vu→vu→vu \rightarrow vd(u,v)d(u,v)d(u,v) Этот класс графиков хорошо известен? Какие еще свойства у него есть? Например,...
Каковы основные ссылки? Существуют ли какие-либо хорошие высокоуровневые обзоры SGT и его приложений для CS в целом и машинного обучения более
Кто-нибудь знает о программе с открытым исходным кодом для вычисления дерева разложения графов для фиксированной "k" (ширина)? Я знаю, что проблема поиска Tree-Decomposition является NP-Hard для переменной «k», но мои входные экземпляры будут очень маленькими (~ 10 узлов), и «k»...
В игре Tower Defense у вас есть сетка NxM с началом, финишем и несколькими стенами. Враги выбирают кратчайший путь от начала до конца, не проходя сквозь стены (обычно они не привязаны к сетке, но для простоты, скажем, так. В любом случае они не могут перемещаться через диагональные «дыры») Задача...
Какие приложения есть в Vertex Cover Problem в реальном мире? В каких отраслевых или исследовательских проектах используется фактически внедренное программное обеспечение, основанное на теоретических результатах для задачи Vertex Cover? В частности, реализованы ли какие-либо из следующих...
Я рассматриваю графовые классы, которые можно охарактеризовать запрещенными подграфами. Если у класса графов есть конечный набор запрещенных подграфов, то существует тривиальный алгоритм распознавания полиномиального времени (можно просто использовать грубую силу). Но бесконечное семейство...
1- Существуют ли какие-либо конкретные свойства для матрицы смежности, когда граф плоский? 2. Есть ли что-то особенное для вычисления матрицы перманента смежности, когда граф...
(вставлено из MathOverflow) Здравствуй, Я читал эту тему: /mathpro/16393/finding-a-cycle-of-fixed-length Я хочу найти 5-цикл в графике. На самом деле, то, что я действительно хочу, это кратчайший нечетный цикл длиной не менее 5, но, возможно, это немного не относится к делу. В моих целях я...
Фон: Пусть две вершины неориентированного графа . Множество вершин является -сепаратором, если и принадлежат различным связным компонентам . Если собственное подмножество -сепаратора является -сепаратором, то является минимальным -сепаратором. Множество вершин является (минимальным) разделителем,...
Рассуждая немного об этом вопросе , я попытался определить все различные причины, по которым граф может не быть k раскрашиваемым. Это единственные две причины, которые я смог определить до сих пор:G=(VG,EG)G=(VG,EG)G = (V_G,E_G)kkk содержит клику размером k + 1 . Это очевидная причина.GGGk+1k+1k+1...
Рассмотрим множество плоских графов, где все внутренние грани являются треугольниками. Если есть внутренняя точка нечетной степени, график не может быть трехцветным. Если каждая внутренняя точка имеет четную степень, она всегда может быть трехцветной? В идеале я хотел бы небольшой...
Следующая интересная проблема возникла в моем исследовании недавно: МИГ: График .G ( V, E)G(V,E)G(V, E) РЕШЕНИЕ: завершение неординарного нечетного цикла, определяемое как надмножество множества ребер, так что завершенный граф обладает свойством того, что каждое ребро в содержится в нечетком...
Коготь - это . Тривиальный алгоритм обнаружит коготь за времени. Это можно сделать в , где - показатель быстрого умножения матриц следующим образом: возьмите подграф, индуцированный для каждой вершины , и найдите треугольник в его...
Я только что прочитал в немецкой Википедии, что бесконечный граф - это граф с бесконечным числом узлов или бесконечным числом ребер. Я знаю только приложения и алгоритмы для конечных графов. Для чего нужны бесконечные графики? Каковы приложения тех? Я не могу представить алгоритмы, которые будут...
Класс сложности PPAD (например, вычисление различных равновесий по Нэшу) может быть определен как совокупность полных задач поиска, многократно сводимых к END OF LINE : КОНЕЦ ЛИНИИ : Для заданных схем S и P с n входными битами и n выходными битами, такими что P (0 n ) = 0 n ! = S (0 n ) , найти...