Dado un DAG no ponderado (gráfico acíclico dirigido) y dos vértices s y t , ¿es posible encontrar el camino más corto y más largo de s a t en tiempo polinómico? Las longitudes de camino se miden por el número de aristas.D=(V,A)D=(V,A)D = (V,A)ssstttsssttt Estoy interesado en encontrar el rango de...
Si un gráfico está conectado y no tiene una ruta con una longitud mayor que , demuestre que cada dos rutas en de longitud tienen al menos un vértice en común. GGGkkkGGGkkk Creo que ese vértice común debería estar en el medio de ambos caminos. Porque si este no es el caso, entonces podemos tener...
Estoy buscando el algoritmo O (V + E) para encontrar la reducción transitiva dado un DAG. Es decir, elimine tantos bordes como sea posible para que si pudiera alcanzar v desde u, para v y u arbitrarios, aún pueda alcanzar después de eliminar los bordes. Si este es un problema estándar, indíqueme...
Creo que esto es cierto, pero tampoco he podido obtener una prueba formal. ¿Pero es cierto que cualquier árbol de expansión mínimo es accesible mediante la aplicación del algoritmo de Kruskal? Del mismo modo, ¿es esto cierto para el algoritmo de Prim? EDITAR: Para ser más precisos, quiero saber si...
He implementado una clasificación topológica basada en el artículo de Wikipedia que estoy usando para la resolución de dependencias, pero devuelve una lista lineal. ¿Qué tipo de algoritmo puedo usar para encontrar las rutas
Soy un novato (novato total en la teoría de la complejidad computacional) y tengo una pregunta. Digamos que tenemos 'Problema de vendedor ambulante', ¿lo resolverá la siguiente aplicación de los Algoritmos de Dijkstra? Desde un punto de inicio calculamos la distancia más corta entre dos puntos....
Se dice que una gráfica dirigida es antipática si para cualquiera de los dos vértices y v en la gráfica G = ( V , E ) , hay como máximo una ruta simple de u a v .tuuuvvvG = ( V, E)G=(V,E)G=(V,E)tuuuvvv Supongamos que se me da un gráfico antipatía tal que cada borde tiene un peso positivo o...
Tengo una pregunta muy genérica que hacer. Está relacionado con la investigación. Estoy interesado en la teoría de grafos. He hecho un curso al respecto. He hecho algunos temas relacionados con la teoría de grafos como un punto de vista para hacerlo como estudiante de matemáticas y también estudié...
Dada una distribución de grados, ¿qué tan rápido podemos construir un gráfico que siga la distribución de grados dada? Un enlace o un bosquejo de algoritmo sería bueno. El algoritmo debe informar un "no" en caso de que no se pueda construir un gráfico y cualquier ejemplo si se pueden construir...
Esto podría estar al borde de la ciencia cognitiva computacional, pero tengo curiosidad sobre cómo el proceso seguido por los algoritmos de búsqueda de caminos comunes (como A * ) se compara con el proceso que los humanos usan en diferentes situaciones de búsqueda de caminos (dada la misma...
Tengo un problema y supongo que es NP-hard, pero no puedo probarlo. Aquí hay un gráfico de capas, donde la capa 0 es la capa más alta y la capa L la más baja. hay un borde dirigido entre capas, donde un borde (A, B) indica que el nodo A puede [cubrir] el nodo B. Y cuando A puede cubrir B, cada...
Actualmente estoy leyendo la introducción a los algoritmos y encontré el algoritmo de Johnson que depende de asegurarse de que todas las rutas sean positivas. el algo depende de encontrar una nueva función de peso (w ') que sea positiva para todos los bordes y mantenga la corrección de las...
¿Hay alguna manera de calcular el tamaño de una coincidencia máxima en un gráfico bipartito no ponderado de manera más eficiente (por ejemplo, más rápido) que calcular una coincidencia máxima? Es una posibilidad remota, pero a menudo es un problema interesante para evitar cálculos desechables...
Dado el hecho de que enumeración de la ruta s - t es un problema # P-completo, ¿podría haber métodos eficientes que calculen (o al menos aproximen) la longitud promedio de la ruta s - t sin enumerarlos? ¿Qué pasa si se permite a los caminos volver a visitar los vértices?ssstttsssttt Los...
En un primer árbol de profundidad, los bordes definen el árbol (es decir, los bordes que se usaron en el recorrido). Hay algunos bordes sobrantes que conectan algunos de los otros nodos. ¿Cuál es la diferencia entre un borde cruzado y un borde delantero? De wikipedia: Según este árbol de...
Considere un gráfico dirigido en el que se pueden agregar bordes dinámicamente y hacer algunas consultas específicas.GGG Ejemplo: bosque disjunto Considere el siguiente conjunto de consultas: arrow(u, v) equiv(u, v) find(u) el primero agrega una flecha al gráfico, el segundo decide si , el...
En el problema de la estación de servicio , se nos dan ciudades y carreteras entre ellas. Cada camino tiene longitud y cada ciudad define el precio del combustible. Una unidad de carretera cuesta una unidad de combustible. Nuestro objetivo es ir de una fuente a un destino de la manera más barata...
Estoy tratando de reproducir las redes sintéticas (gráficos) descritas en algunos documentos. Se afirma que el modelo Barabasi-Albert se utilizó para crear "redes sin escala con distribuciones de grado de ley de potencia, ".PAGUNA( k ) ∝ k- λPA(k)∝k−λP_A(k) ∝ k^{-λ} es una distribución de...
Para algunos gráficos, los algoritmos de búsqueda DFS y BFS procesan los nodos en el mismo orden exacto, siempre que ambos comiencen en el mismo nodo. Dos ejemplos son gráficos que son caminos y gráficos con forma de estrella (árboles de profundidad con un número arbitrario de hijos). ¿Hay alguna...
En el trabajo, se me ha encomendado la tarea de inferir cierta información sobre un lenguaje dinámico. Reescribo secuencias de declaraciones en letexpresiones anidadas , así: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x...