Considere el siguiente problema. Dado: Un gráfico completo con pesos reales no negativos en los bordes. Tarea: Encuentre un subgrafo plano de peso máximo. ("Máximo" entre todos los subgrafos planos posibles.) Nota: El subgrafo de peso máximo será una triangulación; Si el gráfico completo está...
¿Existe una caracterización de gráficos cuyo conjunto de bordes se descomponga en una unión disjunta de combinaciones perfectas? Una clase trivial de tales gráficos son los gráficos -regulares ( n , n ) -bipartitos. Su conjunto de bordes se descompondrá en d combinaciones perfectas disjuntas....
Supongamos que tengo un gráfico disperso finito no dirigido y necesito poder ejecutar las siguientes consultas de manera eficiente: T N 1 N 2 FIsConnected(N1,N2)IsConnected(N1,N2)IsConnected(N_1, N_2) - retornos si existe un camino entre y , de lo
Estoy implementando el algoritmo de cancelación de ciclo para encontrar una solución óptima para el problema de flujo de costo mínimo. Al encontrar y eliminar los ciclos de costos negativos en la red residual, el costo total se reduce en cada ronda. Para encontrar un ciclo negativo, estoy usando el...
Estoy escribiendo un programa, resolviendo el problema del cartero chino (también conocido como problema de inspección de ruta) en un diagrama no dirigido y actualmente enfrento el problema para encontrar los mejores bordes adicionales para conectar los nodos con un grado impar, para poder calcular...
Queremos resolver un problema de flujo de costo mínimo con un algoritmo genérico de cancelación de ciclo negativo. Es decir, comenzamos con un flujo válido al azar, y luego no elegimos ningún ciclo negativo "bueno", como los ciclos de costo promedio mínimo, sino que utilizamos Bellman-Ford para...
Un gráfico bipartito es plano si no tiene o menores. K 5K3,3K3,3K_{3, 3}K5K5K_5 Estoy buscando las condiciones necesarias y / o suficientes para permitir dibujos planos sin bordes que "rodeen" conjuntos de vértices. Estos son dibujos satisfactorios: Todos los vértices de una parte se dibujan en...
MMMG(U,V,E)G(U,V,E)G(U, V, E)min(|U|,|V|)min(|U|,|V|)\min(|U|,
Si una gráfica tiene un ciclo de Euler, ¿los componentes biconéctados también tienen ciclos de
Estoy diseñando un algoritmo para una clase que determinará si un gráfico dirigido es único con respecto a un vértice tal manera que para cualquier haya como máximo una ruta de a . Comencé usando BFS (búsqueda de amplitud) para encontrar la ruta más corta de v a otro vértice u, y luego ejecuté BFS...
Puedes modificar cualquier gráfico GGG para que Dijkstra encuentre la solución con el mínimo número de aristas así: Multiplique cada peso de borde con un número , luego agregue al peso para penalizar cada borde adicional en la solución, es
Me encontré con el siguiente problema: Dado un gráfico acíclico dirigido con pesos de arista con valores reales y dos vértices syt, calcule el corte st mínimo. Para gráficos generales, esto es NP-hard, ya que uno puede reducir trivialmente el corte máximo simplemente invirtiendo los pesos de los...
Estoy buscando un documento fácil e introductorio sobre la prueba del Teorema de Courcelle . También estoy interesado en su conexión con la complejidad parametrizada con respecto al ancho del árbol . Solo soy un principiante en este campo. ¿Alguna
Estoy trabajando en un problema relacionado con los cuadrados latinos, y quiero un método para lo que esencialmente se reduce al problema de decisión: Entrada : Un gráfico simple finito G. Salida : YESsi G tiene un automorfismo no trivial, de lo NOcontrario. Por lo tanto... Pregunta : ¿Existe...
Considere un gráfico no dirigido con una fuente y un vértice de sumidero. Nos gustaría eliminar el número mínimo de vértices en ese gráfico para desconectar cualquier ruta entre la fuente y el sumidero. ¿Podemos hacer esto usando un algoritmo de corte máximo y corte
El problema de 3 colores puede probarse NP-Complete haciendo uso de la reducción de 3SAT Graph Coloring (de 3SAT) . Como consecuencia, el problema de 4 colores es NP-Completo usando la reducción de 3 colores: Reducción de la instancia de 3 colores: agregando un vértice adicional al gráfico del...
Considera este problema: Dado un gráfico no dirigido , encuentre tal que:G=(V,E)G=(V,E)G = (V, E)G′=(V′,E′)G′=(V′,E′)G' = (V', E') G′G′G' es un subgrafo inducido deGGG G′G′G' no tiene 3 camarillas |V′||V′||V'|es máximo Por lo tanto, se debe eliminar el menor número de vértices de...
Dado un gráfico , encuentre vértices , cuya eliminación daría como resultado un gráfico con el componente más grande más pequeño. G = ( V, E)sol=(V,mi)G = (V, E)kkk{v∗1,…,v∗k}{v1∗,...,vk∗}\{v^*_1,\dots,v^*_k\} Supongo que para grandesy grande el problema es difícil (NP-hard), pero estoy interesado...
Actualmente estoy trabajando en mi tesis de maestría, y se trata de la agrupación en gráficos. Estoy trabajando con una idea usando hormigas para resolver el problema. Actualmente estoy trabajando en la implementación y me pregunto exactamente qué tan bien representar los bordes del gráfico. Cada...
Estoy buscando un algoritmo que proporcione una cadena canónica para un gráfico de color dado. Es decir. un algoritmo que devuelve una cadena para un gráfico, de modo que dos gráficos obtienen la misma cadena si y solo si son isomórficos. En particular, estoy buscando un algoritmo simple que sea...