Acabo de leer en la Wikipedia alemana que un gráfico infinito es un gráfico con un número infinito de nodos o un número infinito de bordes. Solo conozco aplicaciones y algoritmos para gráficos finitos. ¿Para qué sirven los gráficos infinitos? ¿Cuáles son las aplicaciones de esos? No puedo...
Sea un gráfico simple en n vértices ( n > 3 ) sin vértices de grado n - 1 . Suponga que para cualquiera de los dos vértices de G , hay un vértice único adyacente a ambos. Es un ejercicio de A Course in Combinatorics , van Lint y Wilson, para demostrar que dicho gráfico es...
A continuación, MSO denota la lógica monádica de segundo orden de los gráficos con cuantificaciones de conjuntos de vértices y conjuntos de bordes. Sea una familia cerrada menor de gráficos. Se deduce de Robertson y de Seymour gráfico teoría menor que F se caracteriza por una lista finita H 1 , H...
Supongamos que tenemos un gráfico ponderado no dirigido (con pesos no negativos). Supongamos que todos los caminos más cortos en son únicos. Supongamos que tenemos estos \ binom {n} {2} caminos (secuencias de bordes no ponderados), pero no conocemos G en sí. ¿Podemos producir cualquier G que...
Se le da un gráfico con vértices. Puede ser bipartito si quieres. Hay conjuntos de aristas (digamos disjunto). Estoy interesado en el problema de encontrar un subconjunto , lo más pequeño posible (o incluso más pequeño), de modo que el gráfico inducido tenga al menos un borde de cada clase , para...
Feedback Vertex Set es NP-complete para gráficos generales. Se sabe que es NP-completo para gráficos limitados de grado 8 debido a una reducción de la cubierta del vértice. El artículo de Wikipedia dice que es polisoluble para gráficos limitados de grado 3 y NP-completo para gráficos limitados de...
Estoy buscando formas de mantener un árbol de expansión de un gráfico relativamente equilibrado, a medida que agrego nuevos nodos / bordes al gráfico. Tengo un gráfico no dirigido que comienza como un solo nodo, la "raíz". En cada paso, agrego al gráfico un nuevo nodo y un borde que lo conecta al...
Estoy interesado en modelos de gráficos aleatorios que son similares a los gráficos de redes informáticas reales. No estoy seguro de si el modelo común bien estudiado ( vértices, cada borde posible se selecciona con probabilidad ) es bueno para estudiar redes informáticas reales (¿verdad?).G ( n ,...
Sea un gráfico no ponderado no dirigido con vértices aristas. ¿Es posible preprocesar y producir una estructura de datos de tamaño para que pueda responder consultas de la forma "distancia entren m G m ⋅ p o l y l o g ( n ) u vGGGnnnmmmGGGm⋅polylog(n)m⋅polylog(n)m \cdot \mathrm{polylog}(n)uuu y "...
Supongamos que t(G)t(G)t(G) denota el número de árboles de expansión en un gráfico con vértices. Hay un algoritmo que calcula en operaciones aritméticas . Este algoritmo es para calcular , donde Q es el laplaciano de G y J es la matriz que consiste únicamente en 1 's. Para obtener más información...
¿Hay un ejemplo de una clase de gráficos para los cuales el problema de coloración de vértices está en P pero el conjunto independiente si el problema es NP
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
Estoy interesado en el siguiente problema: Dada una matriz , ¿hay un gráfico no dirigido en n vértices cuya matriz de adyacencia al cuadrado es esa matriz?n×nn×nn\times nnnn ¿Se conoce la complejidad computacional de este problema? Observaciones: Por supuesto, esto también puede expresarse como...
Muchos problemas de gráficos duros se pueden resolver en tiempo polinómico en gráficos de ancho de árbol acotado . De hecho, los libros de texto suelen utilizar, por ejemplo, un conjunto independiente como ejemplo, que es un problema local . Aproximadamente, un problema local es un problema cuya...
¿Alguien sabe acerca de un resultado de completitud NP para el problema DOMINATORIO SET en gráficos, restringido a la clase de gráficos bipartitos planos de grado máximo 3? Sé que es NP completo para la clase de gráficos planos de grado máximo 3 (ver el libro de Garey y Johnson), así como para...
¿Qué se sabe sobre la complejidad exacta del problema de supercuerdas más corto? ¿Se puede resolver más rápido que O∗(2n)O∗(2n)O^*(2^n) ? ¿Existen algoritmos conocidos que resuelvan la supercadena más corta sin reducir a TSP? UPD: suprime los factores polinomiales.O∗(⋅)O∗(⋅)O^*(\cdot) El...
¿Hay una secuencia de gráficos no dirigidos , donde cada C n tiene exactamente n vértices y el problema{Cn}n∈N{Cn}n∈N\{C_n\}_{n\in \mathbb N}CnCnC_nnnn Dado y un gráfico G , ¿es C n un subgrafo inducido de G ?nnnGGGCnCnC_nGGG se sabe que está en la clase ? (Por ejemplo, cuando C n = K n , este...
¿Cómo puedo determinar la cantidad de rutas simples únicas dentro de un gráfico no dirigido? Ya sea para una determinada longitud o para un rango de longitudes aceptables. Recuerde que una ruta simple es una ruta sin ciclos, así que estoy hablando de contar el número de rutas sin...
¿Se conoce la siguiente clase de gráfico en la literatura? La clase de gráficos está parametrizada por los enteros positivos y y contiene cada gráfico modo que para cada vértice , el subgrafo de inducido en todos los vértices a distancia como máximo de en tiene un ancho de árbol como máximo...
Mientras buscaba en el Sistema de información sobre clases de gráficos y sus inclusiones , encontré varias clases de gráficos para las cuales el problema del Ciclo Hamiltoniano es NP completo, mientras que la complejidad de los problemas del Camino Hamiltoniano NO se conoce. Algunas de esas clases...