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...
Muy similar a mi pregunta publicada anteriormente . Esta vez, sin embargo, el gráfico no está dirigido. Dado Un gráfico G no dirigido sin múltiples bordes o bucles,GGG Un vértice fuente sss , Un vértice objetivo ttt , Longitud máxima del camino lll , Busco - A subgrafo de G que contiene...
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...
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,
Estoy buscando un pequeño gráfico GGG cuyo número cromático vectorial es menor que el número cromático,
Dado un DAG (gráfico acíclico dirigido) , con fuentes de S y se hunde T . Encuentre un DAG D ′ , con fuentes S y sumideros T , con un número mínimo de aristas tales que:DDDSSSTTTD′D′D'SSSTTT Para todos los pares hay una ruta de u a v en D si y solo si hay una ruta de u a v en D ′ .u∈S,v∈Tu∈S,v∈Tu...
Considere una gráfica con vértices ym aristas. Los vértices están etiquetados con variables reales x i , donde x 1 = 0 es fijo. Cada borde representa una "medida": para el borde ( u , v ) , obtengo una medida z ≈ x u - x v . Más precisamente, z es una cantidad verdaderamente aleatoria en ( x u - x...
Cruzado desde MO . Sea una clase gráfica definida por un número finito de subgrafías inducidas prohibidas, todas las cuales son cíclicas (contienen al menos un ciclo).CCC ¿Hay problemas de gráficos NP-hard que se puedan resolver en tiempo polinómico para no sean Clique y Clique cover?CCC Si...
Sea un gráfico dirigido acíclico, de modo que el grado de salida de cualquier vértice sea O ( log | V | ) . Para cada vértice de G podemos contar el número de vértices alcanzables, simplemente ejecutando dfs desde cada vértice y esto llevará tiempo O ( | V | | E | ) . ¿Hay una mejor manera de...
¿Se ha estudiado este problema antes? Dado un gráfico métrico no dirigido G (las longitudes de los bordes satisfacen la desigualdad del triángulo), encuentre un conjunto S de vértices tal que MST (G [S]) se maximice, donde MST (G [S]) es el árbol de expansión mínimo del subgráfico inducido por S....
Me gustaría preguntar si hay un resultado ya publicado sobre eso: Tomamos todos los caminos diferentes posibles entre cada par de nodos de dos gráficos regulares conectados (con el grado , digamos, y el número de nodos n ) y escribimos sus longitudes. Por supuesto, este número de caminos distintos...
Como mencionó @Marzio, el siguiente juego se conoce como Geografía Generalizada . Dado un gráfico y un vértice inicial , el juego se define de la siguiente manera:v ∈ VG = ( V, E)sol=(V,mi)G=(V,E)v ∈ Vv∈Vv \in V En cada turno (dos jugadores alternando), un jugador elige u ∈ N( v )tu∈norte(v)u\in...
En este momento hay montañas de resultados en separadores en gráficos, desde separador plano, separador de árbol, gráficos de ancho de árbol acotado, gráficos de género acotados, etc., etc. ¿Hay alguna encuesta actualizada sobre esto y sus
Dado un gráfico ponderado no dirigido con m=o(n2)m=o(n2)m = o(n^2) aristas, me gustaría calcular distancias de aproximación menores que 2 entre cualquier par de vértices dado. Por supuesto, me gustaría utilizar el espacio subcuadrático y el tiempo de consulta sublineal. Soy consciente del...
Este reciente artículo de FOCS2013, Strong Backdoors to Bounded Treewidth SAT de Gaspers y Szeider habla sobre el vínculo entre el ancho del árbol del gráfico de la cláusula SAT y la dureza de la instancia. Para instancias 3-SAT aleatorias, es decir, instancias 3-SAT elegidas al azar, ¿cuál es...
Recordemos el diámetro de un gráfico es la longitud de un camino más largo más corto de G . Dado un gráfico, un algoritmo obvio para calcular diam ( G ) resuelve el problema de la ruta más corta de todos los pares (APSP) y devuelve la longitud de la ruta más larga
Estoy buscando una forma de generar gráficos para que se conozca la cobertura óptima del vértice. No hay restricciones en el número de nodos o bordes, solo que el gráfico está completamente conectado. la idea es generar un gráfico que no sea fácil de encontrar la cubierta óptima del vértice, para...
GGGMGMGM_GGGGMG[i,j]MG[i,j]M_G[i, j]iiijjjGGG+++maxmax\max Digo que una subgrafía de (con el mismo conjunto de vértices) es sp-equivalente a si . En otras palabras, quitar bordes para ir de a no cambia la longitud de los caminos más cortos; los bordes eliminados no son necesarios para ninguna ruta...
Estoy buscando una estructura de datos y un algoritmo para calcular la cantidad mínima de cambios necesarios para transformar una palabra en otra, dadas las dos palabras como entradas, donde los únicos cambios permitidos son agregue una letra en una de las extremidades (por ejemplo, AB ->...
Deja ad(G)ad(G)\rm{ad}(G) sea la distancia media de un gráfico conectado G.G.G. Una forma de calcular ad(G)ad(G)\rm{ad}(G) es sumar los elementos de D(G),D(G),D(G), la matriz de distancia de GGG y escalar la suma adecuadamente. Si el gráfico de salida es un árbol, entonces se sabe que la...