Considere una gráfica con todas las aristas con capacidad unitaria. Uno puede encontrar el corte mínimo en tiempo polinómico. Supongamos que se me permite aumentar la capacidad de cualquier bordes hasta el infinito (equivalente a fusionar los nodos a cada lado del borde). ¿Cuál es la forma óptima...
El teorema de Robertson-Seymour dice que cualquier familia GG\mathcal G de gráficas menores cerradas puede caracterizarse por un número finito de menores prohibidos. ¿Existe algún algoritmo que para una entrada GG\mathcal G dé salida a los menores prohibidos o es indecidible? Obviamente, la...
Estoy tratando de encontrar un gráfico con esas propiedades para mis estudios, pero desafortunadamente no puedo encontrar ese gráfico. ¿Alguien sabe si existe ese gráfico, o por qué es imposible
Estoy resolviendo un problema de "mezclar" conjuntos de imágenes superpuestas. Estos conjuntos se pueden representar mediante un gráfico ponderado no dirigido como este: Cada nodo representa una imagen. Las imágenes superpuestas están conectadas por un borde. El peso del borde representa el...
¿Cuántos ciclos hay en un gráfico de vértices de modo que el gráfico no tenga ningún ciclo ? ( k ≥ 3 ) n C m ( m > k )CkCkC_k (k≥3)(k≥3)(k \geq 3)nnn CmCmC_m (m>k)(m>k)(m>k) Por ejemplo, , , entonces el gráfico tendrá como máximo dos para que no tenga ningúnk = 3 C 3 G C k ( k > 3 )...
Tenemos un algoritmo de tiempo para determinar si un gráfico G tiene un ciclo de longitud exactamente k . ¿Cómo podemos encontrar cuántos k- ciclos están presentes en G usando el mismo algoritmo o cualquier otro?f(k)n3f(k)n3f(k)
Suponga que tengo conjuntos de con elementos tomados de r posibles. Cada conjunto es de tamaño n ( n < r ), donde los conjuntos pueden superponerse. Quiero determinar si los siguientes dos problemas son NP completos o
Dado un lenguaje regular en el alfabeto A , su autómata determinista mínimo puede verse como un multigrafo conectado directo con un grado de salida constante | A | y un estado inicial marcado (olvidando etiquetas de transiciones, estados finales). Mantenemos el estado inicial porque cada vértice...
¿Comprobar la transitividad de un dígrafo no es más fácil que (en términos de complejidad asintótica) tomar el cierre transitivo del dígrafo? ¿Conocemos algún límite inferior mejor que para determinar si un dígrafo es transitivo o
Ha habido algunas preguntas ( 1 , 2 , 3 ) sobre la terminación transitiva aquí que me hicieron pensar si algo como esto es posible: Supongamos que obtenemos un gráfico solGG entrada dirigido y nos gustaría responder consultas del tipo " ?", Es decir, preguntar si existe un borde entre dos...
Problema clásico: Deje que se dé un número . El problema -clique es el siguiente.kkkkkkk Dado un gráfico , ¿existe un subconjunto de vértices para que dos vértices de sean adyacentes?S k SGGGSSSkkkSSS Problema de hipergrafía: Deje que se den los números y . El problema -hiperclique es el...
Estoy buscando referencias para el siguiente problema: dados los enteros y , enumere todos los gráficos planos no isomórficos en vértices y ancho de árbol \ leq k . Me interesan los resultados teóricos y prácticos, pero en su mayoría algoritmos prácticos que son posibles de codificar y ejecutar...
Esta pregunta es doble y está principalmente orientada a referencias: ¿Hay algún lugar donde se den las intuiciones principales para probar el teorema menor del gráfico, sin entrar demasiado en los detalles? Sé que la prueba es larga y difícil, pero seguramente debe haber ideas clave que puedan...
Supongamos que y H son dos gráficos r- conectados regulares de tamaño n . Deje A el conjunto de permutaciones P tal que P G P - 1 = H . Si G = H entonces A es el conjunto de automorfismos de G .solGGHHHrrrnortennUNAAAPAGSPPPAGSG P- 1= HPGP−1=HPGP^{-1}=HG = HG=HG=HAAAGGG ¿Cuál es el límite...
Dado un gráfico y un δ > 0, uno quiere calcular h ( G , δ ) = m i n | S | ≤ δ | V | ϕ ( S ) . ( ϕ ( S ) = E ( S , ˉ S )G = ( V, E)G=(V,E)G=(V,E)δ> 0δ>0\delta > 0h ( G , δ) = m i nEl | SEl | ≤ δEl | VEl |ϕ ( S)h(G,δ)=min|S|≤δ|V|ϕ(S)h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert }...
Deje ser un gráfico. Un conjunto de vértices se llama crítico si y no vértice en es adyacente a exactamente un vértice en . El problema es encontrar un conjunto de vértices de tamaño mínimo tal que para cada conjunto crítico .X ⊆ V X ≠ ∅ V ∖ X X S ⊆ V S ∩ X ≠ ∅ XG = ( V, E)G=(V,E)G=(V,E)X⊆...
Dejar solsolG ser un gráfico que es la unión disjunta de una camarilla y un conjunto independiente, es decir G =Knorte1+Knorte2¯¯¯¯¯¯¯¯=Knorte1+yonorte2.sol=Knorte1+Knorte2¯=Knorte1+yonorte2.G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} . La clase de gráfico de todos estos gráficos se...
Considere el siguiente problema: Entrada: un gráfico simple (no dirigido) .G = ( V, E)sol=(V,mi)G=(V,E) Pregunta: ¿Existe una orientación de satisfaga la propiedad de que para cada s , t ∈ V hay a lo sumo una s - t walk (dirigida) ?solsolGs , t ∈ Vs,t∈Vs,t \in Vsssttt Esto puede expresarse...
Me pregunto si el siguiente problema es NP-hard. Entrada: G = ( V, E)G=(V,E)G = (V,E) un gráfico simple y una coloración de los bordes ( no verifica ninguna propiedad específica).fF: E→ { 1 , 2 , 3 }f:E→{1,2,3}f : E \to \{1,2,3\}Fff Pregunta: ¿ es posible dividir en triángulos | E | / 3 , de...
Ahora es una observación bien conocida que muchas estructuras gráficas que surgen en entornos naturales tienden a obedecer propiedades libres de escala, como la ley de poder de la distribución de grados. ¿Hay algún buen ejemplo de gráficos naturales que sean bastante aleatorios y que no obedezcan...