¿Para qué gráficos no dirigidos son todos los árboles de búsqueda de profundidad primero (para todos los vértices iniciales posibles y para todas las opciones de qué vecinos buscar primero) rutas dirigidas? Es decir, cada árbol DFS debe tener solo una hoja, y todos los demás vértices deben tener...
Considere el siguiente problema. Entrada: Un gráfico no dirigido . Salida: Un gráfico H que es un menor de con la densidad de borde más alta entre todos los menores de , es decir, con la relación más alta.G=(V,E)G=(V,E)G=(V,E)HHHGGGGGG|E(H)|/|V(H)||E(H)|/|V(H)||E(H)|/|V(H)| ¿Se ha estudiado este...
Estoy interesado en comprender la estructura de la clase de gráficos modo que no exista un subgrafo inducido por vértices en cuatro vértices que coincida perfectamente. Dicho de manera diferente para cualquier cuatro vértices a , b , c , d en G si a b y c d son bordes, entonces el gráfico debe...
Una propiedad de gráfico se denomina hereditaria si se cierra con respecto a la eliminación de vértices (es decir, todas las subgrafías inducidas heredan la propiedad). Una propiedad gráfica se llama aditiva si se cierra con respecto a tomar uniones disjuntas. No es difícil encontrar propiedades...
Problema Tengo un gráfico no dirigido (con múltiples bordes), que cambiará con el tiempo, los nodos y los bordes se pueden insertar y eliminar. En cada modificación del gráfico, tengo que actualizar los componentes conectados de este gráfico. Propiedades Las propiedades adicionales son que no se...
De nuevo, un problema de partición de bordes cuya complejidad me causa curiosidad, motivado por una pregunta anterior mía . Entrada: un gráfico cúbico G=(V,E)G=(V,E)G=(V,E) Pregunta: ¿hay una partición de en E 1 , E 2 , ... , E s , de modo que el subgrafo inducido por cada E i sea una garra...
Deje que G sea un gráfico conectado. ¿Cuál es la complejidad de contar todos los subgrafos conectados si G es de los siguientes tipos? G es general. G es plano. G es bipartito. No me importan las estructuras o ... ¡solo necesito contar todas las subgrafías conectadas! También estoy...
La descomposición de los árboles es difícil en el peor de los casos, pero el método codicioso parece ser casi óptimo en pequeñas redes de la vida real. ¿Se sabe algo sobre la dureza de la descomposición del árbol de una instancia "típica" de alguna clase de gráficos? ¿Hay algún ejemplo de una...
Deje y denote por G k el conjunto de todos los gráficos que se pueden incrustar en una superficie del género k de modo que todos los vértices estén situados en la cara externa . Por ejemplo, G 0 es el conjunto de gráficos de plano exterior. ¿Puede el ancho de árbol de los gráficos en G k estar...
Hay varias nociones en competencia de un "gráfico disperso". Por ejemplo, un gráfico empotrable en la superficie podría considerarse escaso. O un gráfico con densidad de borde acotada. O un gráfico con gran circunferencia. Un gráfico con gran expansión. Un gráfico con ancho de árbol acotado....
Dado un gráfico , necesitamos encontrar la cardinalidad del conjunto más grande de vértices para que cada uno de ellos esté presente en cada coincidencia máxima posible.GGG ¿Hay una solución al lado de lo obvio para eliminar cada vértice y encontrar la coincidencia máxima para ver que se...
En el famoso contraejemplo para el isomorfismo gráfico mediante el método Weisfeiler-Lehman (WL) , Cai, Furer e Immerman construyeron el siguiente dispositivo en este documento . Construyen un gráfico dado porXk=(Vk,Ek)Xk=(Vk,Ek)X_k = (V_k,
Está formulado extendiendo los gráficos de umbral . Dado un gráfico de umbral , donde C es la camarilla y I es el conjunto independiente, mi extensión es como sigue: Cada vértice v ∈ I puede ser reemplazado por un nuevo clique K v tal que los vértices de K v tienen el mismos vecinos de v...
Se han realizado algunos esfuerzos para atacar el problema del isomorfismo gráfico utilizando la caminata aleatoria cuántica de bosones de núcleo duro (simétrica pero sin ocupación doble). Amir Rahnamai Barghi e Ilya Ponomarenko demostraron que el poder simétrico de la matriz de adyacencia, que...
Si es un gráfico con el máximo grado 3 y es un menor de H , entonces es un menor topológica de .solGGHHHHsolGGHHH Wikipedia cita este resultado de la "teoría de grafos" de Diestel. Está listado como la Proposición 1.7.4 en la última versión del libro. El libro carece de prueba o cita. ¿Se conoce...
Instancia: Un gráfico no dirigido con dos vértices distinguidos s ≠ t , y un entero k ≥ 2 .solGGs ≠ ts≠ts\neq tk ≥ 2k≥2k\geq 2 Pregunta: ¿Existe una ruta en G , de modo que la ruta toque a lo sumo k vértices? (La ruta toca un vértice si el vértice está en la ruta o tiene un vecino en la ruta).s -...
Aquí: http://www.planarity.org/Klein_elementary_graph_theory.pdf (en incrustaciones de capítulos) se le da la definición de incrustación combinatoria de un gráfico plano. (con definición de caras, etc.) Aunque podría usarse fácilmente para cualquier gráfico, definen el gráfico plano como el...
Dejemos que kkk sea fijo, y que GGG sea un gráfico (conectado). Si no me equivoco, se deduce del trabajo de Bodlaender [1, Teorema 3.11] que si el ancho de árbol de GGG es aproximadamente de al menos 2k32k32k^3 , entonces GGG contiene una estrella K1,kK1,kK_{1,k} como menor. ¿Podemos hacer que...
Dado un gráfico dirigido con n nodos de modo que cada vértice tenga exactamente dos bordes salientes, y un número natural N codificado en binario, dos vértices syt, Quiero contar el número de rutas (no necesariamente simples) de sa t en N pasos. ¿Es este un problema difícil de # P? O, en...
Sabemos, por ejemplo, por Koutis-Miller-Peng (basado en el trabajo de Spielman y Teng), que podemos resolver muy rápidamente los sistemas lineales Ax=bAx=bA x = b para las matrices AAA que son la matriz de Laplacia de gráficos para algunos gráficos dispersos con pesos de borde no negativos . Ahora...