El teorema de Fáry dice que se puede dibujar un gráfico plano simple sin cruces para que cada borde sea un segmento de línea recta. Mi pregunta es si existe un teorema análogo para las gráficas del número de cruce acotado . Específicamente, ¿podemos decir que se puede dibujar un gráfico simple con...
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...
Tengo un gráfico que consiste solo en gráficos de estrellas. Un gráfico de estrella consiste en un nodo central que tiene bordes para cada otro nodo en él. Deje ser diferentes gráficos radiales de diferentes tamaños que están presentes en . Llamamos al conjunto de todos los nodos que son centros en...
Me pregunto si el siguiente problema tiene un nombre o algún resultado relacionado con él. Sea un gráfico ponderado donde denota el peso del borde entre y , y para todos , . El problema es encontrar un subconjunto de vértices que maximice la suma de los pesos de los bordes adyacentes a ellos:...
Uno de los principales problemas en la enumeración de gráficos es determinar la 'forma' de un gráfico, por ejemplo, la clase de isomorfismo de cualquier gráfico particular. Soy plenamente consciente de que cada gráfico se puede representar como una matriz simétrica. Sin embargo, para obtener su...
Defina una malla en 3D como una colección conectada de tetraedros con interiores disjuntos (para que los tetraedros solo compartan caras , k ≤ 2 ). Dado un gráfico arbitrario, ¿existe un procedimiento eficiente para probar si se puede incrustar como una malla?k ≤ 2k≤2k \le 2 Aquí, una incrustación...
Me gustaría tener un límite en la cardinalidad del conjunto de gráficos de unidades de disco con vértices. Se sabe que verificar si un gráfico es miembro de este conjunto es NP-hard. ¿Esto conduce a un límite inferior en la cardinalidad, suponiendo P ≠ NP?NNN≠≠\neq Por ejemplo, suponga que hay un...
Estoy trabajando en algoritmos de aproximación para un problema de conjunto dominante mínimo. En particular, estoy interesado en las clases de gráficos restringidas por subgrafos inducidos prohibidos. Dado que el problema de la dominación y sus variantes se han estudiado ampliamente, supongo que...
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...
Tengo un conjunto finito , una función , y una orden total en . Quiero encontrar el número de ciclos distintos en .f : S → S < S SSSSf:S→Sf:S→Sf:S\to
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...
Al presentar la descomposición modular del gráfico , la mayoría de los autores utilizan el gráfico de 11 vértices, que copio de wikipedia. La pregunta es quién es (son) el diseñador original de la misma. (No estoy preguntando quién dibujó este gráfico para Wikipedia, sino la fuente original del...
Supongamos que tenemos un gráfico en nodos. Nos gustaría asignar a cada nodo un o un . Llame a esto una configuración . El número de s que tenemos que asignar es exactamente (por lo tanto, el número de s es ). Dada una configuración , observamos cada nodo y sumamos los valores asignados a sus...
Deje ser un gráfico. Dejeser un número entero Sea el número de inducidas por aristas de tienen vértices y un número impar de aristas. Sea el número de inducidas por aristas de tienen vértices y un número par de aristas. Deje . El problema ODD EVEN DELTA consiste en calcular , dados y .G = ( V,...
puntos distintos se seleccionan aleatoriamente de unacuadrícula p × q . (Obviamente, k ≤ p × q y es un número constante dado.) Se construye un gráfico ponderado completo a partir de estos k puntos de modo que el peso del borde entre el vértice i y el vértice j sea igual a la distancia de Manhattan...
Me encontré con este problema de coincidencia para el que no puedo escribir un algoritmo de tiempo polinómico. Supongamos que sean gráficos ponderados completos con conjuntos de vértices P V y Q V , respectivamente, donde | P V | = | Q V | = n . Además, dejar que w P y w Q ser las funciones de...
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...
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 )...