En el caso de los gráficos sin etiquetar, el problema del isomorfismo del gráfico puede abordarse mediante una serie de algoritmos que funcionan muy bien en la práctica. Es decir, aunque el peor tiempo de ejecución es exponencial, generalmente se tiene un tiempo de ejecución polinómico. Esperaba...
Estaba aprendiendo sobre la primera búsqueda de amplitud y se me ocurrió una pregunta de por qué BFS se llama así. En el libro Introducción a los algoritmos de CLRS , leí la siguiente razón para esto: La búsqueda de amplitud primero se llama así porque expande la frontera entre vértices...
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...
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...
Estoy interesado en las propiedades de una clase de gráficos bipartitos donde todos los nodos en X son 3-regulares, todos los nodos en Y son 2-regulares, y | X | = | 2 Y / 3 | . Primero, ¿es esta una clase de gráficos bien conocida? En segundo lugar,G ( X∪ Y, E)G(X∪Y,E)G(X \cup Y, E)XXXYYYEl | XEl...
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...
Tengo una tarea para la cual me he estado golpeando la cabeza durante algún tiempo, y agradecería cualquier pista. Se trata de elegir un problema conocido, cuya integridad NP está probada, y construir una reducción de ese problema al siguiente problema que llamaré DGD (diagnóstico de gráfico...
Aquí está el problema: Hay un gráfico conectado con nodos que representan a varias personas. Cada nodo / persona tiene una opinión sobre un tema, por ejemplo, trump vs clinton, libros de papel vs kindle, etc. El objetivo es hacer que cada nodo en un gráfico comparta la misma opinión,...
Una relación de equivalencia en un conjunto de vértices finitos puede representarse mediante un gráfico no dirigido que es una unión disjunta de camarillas. El conjunto de vértices representa los elementos y un borde representa que dos elementos son equivalentes. Si tengo un gráfico y gráficos G 1...
Estoy trabajando en un editor de diagramas. Los diagramas muestran formas 2D ( nodos ) conectadas con conectores ( bordes ). Me gustaría agregar una operación que, dada una selección de nodos, los "desenrede" : los reposiciona para reducir el número de bordes cruzados, si es posible (y está bien...
Supongamos que le doy un gráfico no dirigido con bordes ponderados y le digo que cada nodo corresponde a un punto en el espacio 3d. Siempre que haya un borde entre dos nodos, el peso del borde es la distancia entre los puntos. Su objetivo es reconstruir las posiciones relativas de los puntos,...
Pebbling es un juego de solitario jugado en un gráfico no dirigido , donde cada vértice tiene cero o más guijarros. Un solo movimiento consiste en eliminar dos piedras de un vértice y agregar una piedra a un vecino arbitrario de . (Obviamente, el vértice v debe tener al menos dos guijarros antes...
Formulación Alternativa Se me ocurrió una formulación alternativa para el siguiente problema. La formulación alternativa es en realidad un caso especial del problema a continuación y utiliza gráficos bipartitos para describir el problema. Sin embargo, creo que la formulación alternativa sigue...
Un gráfico es cordal si no tiene ciclos inducidos de longitud o más. Un árbol clique de es un árbol en el que los vértices del árbol son la máxima camarillas de . Un borde en corresponde a un separador mínimo. El número de árboles de camarilla distintos puede ser exponencial en el número de...
Dado un gráfico acíclico dirigido , un vértice es una fuente si su grado es cero, lo que significa que solo tiene arcos salientes.D = ( V, A )re=(V,UNA)D = (V,A)v ∈ Vv∈Vv \in V ¿Existe un algoritmo de tiempo lineal para encontrar una fuente en un gráfico acíclico dirigido dado? Pregunta de...
Actualmente estoy trabajando para comprender el uso del límite de Cheeger y la desigualdad de Cheeger, y su uso para la partición espectral, la conductancia, la expansión, etc., pero todavía me cuesta comenzar una intuición con respecto al segundo valor propio de la matriz de adyacencia. Por lo...
Mi problema es así: Tengo un diseño físico representado como un gráfico. Los nodos representan ganchos / conductos donde un cable puede anclarse y los bordes son la posible conexión entre 2 nodos desde donde puede ir el cable. Hay algunos nodos especiales, llamados divisores, desde donde un solo...
¿Existe alguna definición formal sobre la altura promedio de un árbol binario? Tengo una pregunta tutorial sobre cómo encontrar la altura promedio de un árbol binario usando los siguientes dos métodos: La solución natural podría ser tomar la longitud promedio de todos los caminos posibles desde...
Estoy buscando un algoritmo para convertir un dígrafo (gráfico dirigido) en un gráfico no dirigido de manera reversible, es decir, el dígrafo debe ser reconstruible si se nos da el gráfico no dirigido. Entiendo que esto vendrá a expensas del gráfico no dirigido que tiene más vértices, pero no me...
Tengo un problema que se puede reducir a un problema de asignación. (En una pregunta anterior descubrí cómo hacerlo). Lo que significa que tenemos un conjunto de agentes y un conjunto de tareas, así como una función de costo . Necesitamos encontrar una asignación para que el costo total sea...