Gráfica mediana

En teoría de grafos, un grafo mediano es un grafo no dirigido en el que tres vértices cualesquiera a , b y c tienen una única mediana  , el vértice m ( a , b , c ), que pertenece a los caminos más cortos entre cada par de vértices a , b y c .

El concepto de gráficas medianas ha sido estudiado durante mucho tiempo, por ejemplo por Birkhoff y Kiss ( Birkhoff, Kiss 1947 ) o (más explícitamente) por Avann ( Avann 1961 ), pero el primer artículo llamado "Gráficas medianas" apareció en 1971 ( Nebesk'y 1971 ). Como escriben Chang Graham y Saks, "los gráficos medianos surgen naturalmente en el estudio de conjuntos ordenados y redes distributivas discretas y tienen una vasta literatura". [1] En filogenética , el gráfico de Buneman que representa todos los árboles evolutivos de máxima verosimilitud es el gráfico mediano. [2] Los gráficos medianos también aparecen en la teoría de la elección social  : si un conjunto de posibilidades tiene la estructura de un gráfico mediano, se puede determinar sin ambigüedades la preferencia de la mayoría entre ellos. [3]

Se puede encontrar una descripción general de los gráficos medianos en Klavžar, Mulder, 1999 , Bandelt, Chepoi, 2008 y Knuth, 2008 .

Ejemplos

Cualquier árbol es un gráfico mediano. [4] En un árbol, la unión de los tres caminos más cortos entre pares de tres vértices a , b y c es un camino en sí mismo o un subárbol formado por tres caminos desde el mismo vértice central de grado tres. Si la unión de tres caminos es en sí misma un camino, la mediana m ( a , b , c ) es igual a uno de los vértices a , b o c , según qué vértice se encuentre entre otros dos del camino. Si el árbol formado por la unión de caminos no es un camino, la mediana será el nodo central del subárbol.

Los retículos son otro ejemplo de gráficos medianos . En un gráfico de celosía, las coordenadas de la mediana m ( a , b , c ) se pueden encontrar como la mediana de las coordenadas de los vértices a , b y c . Por el contrario, resulta que es posible disponer los vértices en una red de enteros de tal manera que las medianas se puedan calcular como las medianas de las coordenadas. [5]

Los gráficos de marco [6] , gráficos planos en los que todas las caras interiores son cuadriláteros y todos los vértices interiores tienen cuatro o más aristas incidentes, son otra subclase de gráficos medianos. [7] Polyomino  es un caso especial de gráficos de cuadros y, por lo tanto, también forma un gráfico mediano.

El grafo simplex κ( G ) de un grafo no dirigido arbitrario G tiene un vértice para cada camarilla (subgrafo completo) de G , y dos vértices están conectados por una arista si las camarillas correspondientes difieren solo en un vértice. La mediana de las tres camarillas dadas se puede formar usando la regla de la mayoría , que le permite determinar qué vértices de camarilla incluir. Un grafo simplex es un grafo mediano en el que esta regla determina la mediana de cada triple de vértices.

Ningún ciclo de longitud distinta de cuatro puede ser un gráfico mediano, ya que cualquier ciclo tiene tres vértices a , b y c , que están conectados por tres caminos más cortos que no tienen intersecciones.

Definiciones equivalentes

En un gráfico arbitrario, para dos vértices a y b cualesquiera, el número mínimo de aristas entre ellos se denomina distancia , que se denota como d ( x , y ). El intervalo de vértices que se encuentran en el camino más corto entre a y b se define como

yo ( un , segundo ) = { v | re ( un , segundo ) = re ( un , v ) + re ( v , b ) } .

El gráfico mediano se define como un gráfico, para tres vértices cualesquiera a , b y c de los cuales estos intervalos se intersecan en un punto:

Para todo a , b y c | yo ( un , segundo ) ∩ yo ( un , c ) ∩ yo ( segundo , c ) | = 1.

De manera similar, para cualesquiera tres vértices a , b y c , uno puede encontrar un vértice m ( a , b , c ) tal que las distancias no ponderadas en el gráfico satisfagan las igualdades

y m ( a , b , c ) es el único vértice para el que esto es cierto.

También se pueden definir gráficos de mediana como soluciones a problemas de 2 satisfacibilidad, como reducción de hipercubo, como gráficos de álgebras de mediana finita, como gráficos de Buneman de sistemas de partición de Halley y como gráficos de windex 2. Consulte las secciones a continuación.

Redes distribuidas y álgebras medianas

En la teoría de la red , la gráfica de una red finita tiene un vértice para cada elemento de la red y una arista para cada par de elementos de la relación de cobertura la red. Los retículos generalmente se representan visualmente como diagramas de Hasse , que son dibujos de gráficos de retículos. Estos gráficos, especialmente para redes distributivas , resultan estar estrechamente relacionados con los gráficos de mediana.

En el retículo distributivo de Birkhoff , la operación ternaria autodual de la mediana [8]

metro ( un , segundo , do ) = ( un ∧ segundo ) ∨ ( un ∧ do ) ∨ ( segundo ∧ do ) = ( un ∨ segundo ) ∧ ( un ∨ do ) ∧ ( segundo ∨ do ),

satisface algunos axiomas clave que son característicos de las medianas ordinarias de números en el intervalo de 0 a 1 y álgebras medianas :

La ley distributiva puede ser reemplazada por una asociativa: [9]

La operación mediana también se puede utilizar para definir el concepto de intervalos para celosías distribuidas:

yo ( un , segundo ) = { X | m(a, x, b) = x } = { x | un ∧ segundo ≤ X ≤ un ∨ segundo } . [diez]

La gráfica de un retículo distributivo finito tiene una arista entre los vértices a y b cuando I ( a , b ) = { a , b }. Para dos vértices a y b cualesquiera de este gráfico, el intervalo I ( a , b ) definido en términos de la teoría de celosía consta de los vértices del camino más corto de a a b , y esto coincide con los intervalos de la teoría de gráficos definidos anteriormente. Para cualesquiera tres elementos de red a , b y c , m ( a , b , c ) es la única intersección de los tres intervalos I ( a , b ), I ( a , c ) e I ( b , c ). [11] Por lo tanto, el gráfico de una red distribuida finita arbitraria es un gráfico mediano. Por el contrario, si el gráfico de la mediana G contiene dos vértices 0 y 1 tales que cualquier otro vértice se encuentra en el camino más corto entre estos dos (equivalentemente, m (0, a , 1) = a para todo a ), entonces podemos definir un distribuido un retículo en el que a ∧ b = m ( a ,0, b ) ya ∨ b = m ( a , 1, b ), y G será la gráfica de este retículo. [12]

Duffus y Rival ( Duffus, Rival 1983 ) describen que los gráficos de celosía distributiva preservan el diámetro de reducción de los hipercubos. En general, cualquier gráfico mediano genera una operación ternaria m que satisface las leyes de idempotencia, conmutatividad y distributividad, pero, posiblemente, sin un solo elemento de la red distribuida. Cualquier operación ternaria en un conjunto finito que satisfaga estas tres propiedades (pero no necesariamente tiene los elementos 0 y 1) genera un gráfico de mediana. [13]

Conjuntos convexos y familias Halley

En un gráfico mediano, se dice que un conjunto de vértices S es convexo si, para dos vértices cualesquiera a y b que pertenecen a S , todo el intervalo I ( a , b ) es un subconjunto de S. De manera equivalente, de acuerdo con las dos definiciones de intervalos anteriores, S es convexo si contiene cualquier camino más corto entre dos vértices, o si contiene la mediana de tres puntos cualesquiera, dos de los cuales se encuentran en S . Tenga en cuenta que la intersección de cualquier par de conjuntos convexos es en sí misma convexa. [catorce]

Los conjuntos convexos en un gráfico mediano tienen la propiedad Halley : si F es una familia arbitraria de conjuntos convexos que se intersecan por pares, entonces todos los conjuntos F tienen un punto común. [15] Entonces, dejemos que F tenga solo tres conjuntos convexos S , T y U . Sean a  las intersecciones de un par S y T , b  las intersecciones de un par T y U , y c  las intersecciones de un par S y U. Entonces cualquier camino más corto de a a b debe estar dentro de T debido a la convexidad y, de la misma manera, cualquier camino más corto entre dos pares cualesquiera de vértices debe estar dentro de otros dos conjuntos, pero m ( a , b , c ) pertenece a los caminos entre los tres pares de vértices, de modo que se encuentra dentro de los tres conjuntos. Si F contiene más de tres conjuntos convexos, el resultado se obtiene por inducción sobre el número de conjuntos: uno puede reemplazar cualquier par de conjuntos en F con su intersección, lo que deja los conjuntos resultantes que se intersecan por pares.

Los conjuntos _

W uv = { w | re ( w , tu ) < re ( w , v )},

que se definen para cada borde del gráfico uv . En términos simples, W uv consta de vértices que están más cerca de u que de v , o, de manera equivalente, vértices w para los cuales el camino más corto de v a w pasa por u . Para mostrar que W uv es convexo, suponga que w 1 w 2 … w k  es un camino más corto arbitrario que comienza y termina dentro de W uv . Entonces w 2 también debe estar dentro de W uv , de lo contrario dos puntos m 1 = m ( u , w 1 , w k ) y m 2 = m ( m 1 , w 2 … w k ) serán dos medianas diferentes u , w 1 , y w k , lo que contradice la definición de un gráfico de mediana, en el que la mediana es única por definición. Por lo tanto, cada vértice en el camino más corto entre dos vértices W uv también se encuentra en W uv , por lo que W uv contiene todos los caminos más cortos entre vértices, que es una de las definiciones de convexidad.

La propiedad de Halley para conjuntos W uv juega un papel clave en la descripción de gráficos de mediana como un problema de 2 satisfacibilidad.

2-satisfacibilidad

Los gráficos de mediana están estrechamente relacionados con los conjuntos de soluciones de problemas de 2 satisfacibilidad , que se pueden usar para describir estos gráficos y que se pueden usar para mostrar la conexión con el mapeo de hipercubo que conserva la adyacencia. [dieciséis]

Una instancia de 2-satisfacibilidad consiste en un conjunto de variables booleanas y una colección de afirmaciones , restricciones en algunos pares de variables para evitar algunas combinaciones de valores. Por lo general, estos problemas se expresan en forma normal conjuntiva , en la que cada enunciado se expresa mediante una disyunción y el conjunto completo de restricciones se expresa mediante una conjunción de enunciados, por ejemplo,

La solución a tal instancia es asignar valores verdaderos a las para satisfacer todas las aseveraciones, o, de manera equivalente, que las aserciones de forma normal conjuntiva produzcan valores verdaderos al sustituir los valores. La familia de todas las soluciones tiene la estructura natural de un álgebra mediana, donde la mediana de tres soluciones se forma eligiendo el valor mayoritario de los tres valores. Es fácil verificar directamente que esta mediana no puede violar las afirmaciones. Por lo tanto, estas soluciones forman un gráfico mediano, en el que los vecinos de cada solución se forman negando un conjunto de variables, para las cuales todos los valores dentro de los conjuntos son iguales o no iguales.

Por el contrario, cualquier gráfico de mediana G puede representarse como un conjunto de soluciones a una instancia del problema de 2 satisfacibilidad. Para encontrar tal representación, creamos una instancia de un problema de 2 satisfacibilidad en el que cada variable describe la dirección de uno de los bordes del gráfico (asignar una dirección a un borde da como resultado gráficos dirigidos ) y cada restricción incluye dos arcos dirigidos solo si existe un vértice v para el cual ambos arcos se encuentran en el camino más corto desde otros vértices a v . Cada vértice v del gráfico G corresponde a una solución a una instancia del problema de 2 satisfacibilidad en el que todos los arcos están dirigidos a v . Cada instancia de solución debe obtenerse de algún vértice v de esta manera, donde v  es la intersección común de conjuntos W uw para arcos dirigidos de w a u . Esta intersección común existe debido a la propiedad de Halley de los conjuntos W uw . Así, las soluciones de una instancia de este problema de 2-satisfacibilidad corresponden uno a uno a los vértices del grafo G.

Reducción de hipercubo

La reducción de un grafo G  es un mapeo de un grafo G en uno de sus subgrafos conservando la adyacencia. [17] Más precisamente, es un homomorfismo φ de G a sí mismo, en el que φ( v ) = v para todo vértice v en el subgrafo φ(G). La imagen de la reducción se llama la reducción del gráfico G . Las reducciones son ejemplos de mapeos cortos : la distancia entre φ( v ) y φ( w ) para cualquier v y w es como máximo la distancia entre v y w , y estas distancias son iguales si ambos vértices v y w pertenecen a φ( G ). Así, la rucción debe ser un subgrafo isométrico del gráfico G : las distancias en la reducción son iguales a las distancias correspondientes en G .

Si G es un gráfico mediano, y a , b y c  son tres vértices arbitrarios de la reducción φ( G ), entonces el vértice φ( m ( a , b , c )) debe ser la mediana de a , b y c , y por lo tanto debe ser igual a m ( a , b , c ). Por lo tanto, φ( G ) contiene las medianas de todas las ternas de vértices y debe ser un gráfico de medianas. En otras palabras, la familia de gráficas medianas se cierra bajo la operación de reducción. [Dieciocho]

Un gráfico de hipercubo en el que los vértices corresponden a todos los vectores de k bits posibles y en el que dos vértices están conectados si los vectores correspondientes difieren en un solo bit es un caso especial de un gráfico de red de k dimensiones y, por lo tanto, un gráfico de mediana. La mediana de tres vectores de bits a , b y c se puede calcular tomando el valor mayoritario de los bits a , b y c . Dado que los gráficos medianos están cerrados bajo la operación de reducción e incluyen hipercubos, cualquier reducción de hipercubo es un gráfico mediano.

Por el contrario, cualquier gráfico de mediana debe ser una reducción de hipercubo. [19] Esto se puede ver en la conexión anterior entre los gráficos de la mediana y el problema de 2-satisfacibilidad. Sea G la solución a una instancia del problema de dos satisfacibilidades. Sin pérdida de generalidad, este ejemplo se puede formular de manera que dos variables no sean siempre iguales o no iguales en todas las soluciones. Entonces el espacio de todas las asignaciones de valores a las variables forman un hipercubo. Para cualquier enunciado formado por la disyunción de dos variables o sus negaciones, en una instancia del problema de 2 satisfacibilidad, se puede formar una reducción de hipercubo en la que la asignación de variables que viola este enunciado se asigna a la asignación de variables en las que ambos Las variables satisfacen la declaración, pero no cambian otras variables. La composición de las reducciones así construida para cada enunciado da una reducción del hipercubo al espacio de solución de la instancia del problema, y ​​por lo tanto da una representación del grafo G como una reducción del hipercubo. En particular, los gráficos de mediana son isométricos a subgráficos de hipercubo y, por lo tanto, son un cubo parcial . Sin embargo, no todos los cubos parciales son gráficos medianos. Por ejemplo, un ciclo con seis vértices es un cubo parcial, pero no un gráfico de mediana.

Imrich y Klavžar ( Imrich, Klavžar 1998 ) escriben que se puede construir una incrustación isométrica de un gráfico mediano en un hipercubo en un tiempo O ( m log n ), donde n y m  son el número de vértices y bordes del gráfico. [veinte]

Gráficos sin triángulos y algoritmos de reconocimiento

Los problemas de verificar si un gráfico es una mediana y si un gráfico contiene triángulos están bien estudiados y, como señalan Imrich, Klavžar y Mulder (1999 ), son computacionalmente equivalentes en algún sentido. [21] Por lo tanto, el tiempo más conocido para verificar si una gráfica tiene triángulos, que es O( m 1.41 ), [22] puede usarse como una estimación del tiempo para verificar si una gráfica es mediana, y cualquier progreso en el El problema de reconocer gráficas medianas conducirá al progreso en algoritmos para determinar triángulos en gráficas.

Para probar la equivalencia en una dirección, supongamos que nos dan un gráfico G y queremos verificar si contiene triángulos. Vamos a crear otro grafo H a partir de G , teniendo como vértices un conjunto de cero, uno o dos vértices adyacentes del grafo G . Dos de estos conjuntos son adyacentes en H si difieren en un solo vértice. Como una descripción alternativa , H se puede formar dividiendo cada borde de G en dos y agregando un nuevo vértice conectado a todos los vértices del gráfico original G. Este gráfico H es un cubo parcial por construcción, pero será mediana solo cuando G no contenga triángulos: si a , b y c forman un triángulo en G , entonces { a , b }, { a , c } y { b , c } no tienen medianas en H , ya que tal mediana tendría que corresponder al conjunto { a , b , c }, pero los conjuntos de tres o más vértices de G no forman vértices en H . Por lo tanto, G no contiene triángulos si y solo si H es un gráfico mediano. En el caso de que G no contenga triángulos, H es su grafo símplex . Un algoritmo para verificar efectivamente si H es un gráfico mediano, mediante esta construcción, se puede usar para verificar la ausencia de triángulos en un gráfico G. Tal transformación preserva la complejidad computacional del problema, ya que el tamaño de H es proporcional al tamaño de G.

La reducción en la otra dirección, desde buscar triángulos hasta verificar si un gráfico es mediano, es más compleja y depende del algoritmo de reconocimiento de gráfico mediano descrito ( Hagauer, Imrich, Klavžar 1999 ) que prueba algunas condiciones necesarias para un gráfico mediano en forma casi lineal. tiempo. El nuevo paso clave utiliza la búsqueda primero en amplitud para descomponer el gráfico en niveles según su distancia desde una raíz elegida arbitrariamente, formando así un gráfico en el que dos vértices son adyacentes si tienen un vecino común en el nivel anterior, y la búsqueda de triángulos ocurre en estos gráficos. La mediana de cualquier triángulo debe ser un vecino común de los tres vértices del triángulo. Si tal vecino no existe, el gráfico no es una mediana. Si se encuentran todos los triángulos y todos tienen medianas, y el algoritmo anterior determina que la gráfica cumple el resto de condiciones para gráficas de medianas, entonces debe ser mediana. Tenga en cuenta que este algoritmo requiere no solo verificar la ausencia de triángulos, sino también enumerar los triángulos en el gráfico de nivel. En un gráfico arbitrario, la enumeración de triángulos a veces requiere un tiempo Ω( m 3/2 ), ya que algunos gráficos tienen tantos triángulos. Sin embargo, Hagauer (Hagauer et al.) demostró que el número de triángulos que aparecen en los gráficos de nivel es casi lineal, lo que permitió a Alon (Alon et al.) utilizar la técnica de la multiplicación rápida de matrices para encontrar triángulos.

Árboles de evolución, gráficos de Buneman y sistemas de partición Halley

La filogenética  es la derivación de árboles filogenéticos a partir de las características observadas de una especie . Dichos árboles deben tener vistas en diferentes vértices y pueden contener vértices ocultos adicionales , pero los vértices ocultos deben tener tres o más aristas incidentes y deben estar etiquetados con características. Las características son binarias si tienen solo dos valores posibles, y un conjunto de especies y sus características muestra una historia evolutiva perfecta si hay un árbol evolutivo en el que los vértices (especies y vértices ocultos) etiquetados con cualquier característica particular forman una contigua subárbol. Si no es posible un árbol con un historial de desarrollo perfecto, a menudo es deseable encontrar el árbol de máxima verosimilitud , o de manera equivalente, minimizar el número de casos en los que los puntos finales de los bordes del árbol tienen características diferentes al sumar todos los bordes. y sobre todas las características.

Buneman ( 1971 ) describió un método para derivar árboles de evolución perfectos para características binarias, si existen. Su método se generaliza de forma natural para construir un gráfico mediano de cualquier conjunto de especies y características binarias, y este gráfico se llama red mediana o gráfico de Buneman [23] y es una red filogenética . Cualquier árbol evolutivo de máxima verosimilitud se puede incrustar en un gráfico de Buneman, en el sentido de que los bordes del árbol siguen caminos en el gráfico y el número de cambios de valor de caracterización en un borde del árbol es igual al número de caminos correspondientes. El gráfico de Buneman es un árbol si y solo si existe un historial de desarrollo perfecto. Esto ocurre cuando no hay dos características incompatibles para las cuales se observan las cuatro combinaciones de valores.

Para generar un gráfico de Buneman para un conjunto de especies y características, primero nos deshacemos de las características redundantes que no se pueden distinguir de otras características y de las características redundantes que siempre coinciden con otras características. Luego formamos un vértice oculto para cualquier combinación de valores característicos, de modo que dos valores cualesquiera existan en formas conocidas. En el ejemplo que se muestra, hay ratones pequeños de cola marrón, ratones pequeños de cola plateada, ratones pequeños de cola marrón, ratones grandes de cola marrón y ratones grandes de cola plateada. El método del gráfico de Buneman creará un vértice oculto correspondiente a una especie desconocida de ratones pequeños de cola plateada, ya que cualquier combinación de emparejamiento (pequeño y plateado, pequeño y con cola y plateado y con cola) aparece en algunas otras especies. Sin embargo, el método no asume la existencia de grandes anuros marrones, ya que no hay especies de grandes y, al mismo tiempo, anuros. Después de definir los vértices ocultos, formamos bordes entre cada par de vistas o vértices ocultos que difieren en una característica.

De manera equivalente, se puede describir un conjunto de características binarias como un sistema de particiones , familias de conjuntos con la propiedad de que el complemento de cualquier conjunto en la familia pertenece a la familia. Este sistema de partición representa un conjunto para cada valor de característica, que consta de las especies que tienen ese valor. Si se incluyen vértices ocultos, el sistema de partición resultante tiene la propiedad Halley  : las intersecciones por parejas de subfamilias no están vacías. En cierto sentido, los gráficos medianos se pueden considerar como derivados de los sistemas de mosaico Halley: los pares ( W uv , W vu ) definidos para cada borde uv del gráfico mediano forman un sistema de mosaico Halley, de modo que si la construcción del gráfico Buneman se aplica a este sistema, los vértices ocultos no son necesarios y el resultado será el gráfico original. [24]

Bandelt , Forster, Sykes, Richards, 1995 y Bandelt, Macaulay, Richards, 2000 describen una técnica para simplificar el cálculo manual de los gráficos de Buneman y muestran el uso de esta construcción para representar visualmente las relaciones genéticas de las personas.

Propiedades adicionales

Notas

  1. ↑ 1 2 3 Chung, Graham, Saks, 1987 .
  2. ↑ Buneman, 1971 , Vestido, Hendy, Huber, Moulton, 1997 , Vestido, Huber, Moulton, 1997 .
  3. ↑ Bandelt, Barthélémy, 1984 , Day, McMorris, 2003 .
  4. ↑ Imrich, Klavžar, 2000 , Declaración 1.26, página 24.
  5. ↑ Esto se deriva inmediatamente de la propiedad de reducción del hipercubo de los gráficos medianos, como se describe a continuación.
  6. ↑ AV Karzanov. Extensiones de métricas finitas y el problema de colocación de equipos // Actas de la ISA RAS. - 2007. - T. 29 . - S. 225-244 .
  7. ↑ Soltan, Zambitskii, Prisˇacaru, 1973 , Chepoi, Dragan, Vaxès, 2002 , Chepoi, Fanciullini, Vaxès, 2004 .
  8. ↑ Birkhoff, Kiss, 1947 atribuyen la definición de esta operación al artículo de G. Birkhoff. Teoría de la red. - Sociedad Matemática Americana, 1940. - Pág. 74 . .
  9. ↑ Knuth, 2008 , págs. 65 y ejercicios 75, 76 en las páginas 89-90. Knuth argumenta que no existe una prueba simple de que la asociatividad implique distributividad.
  10. ↑ La equivalencia de las dos expresiones en esta igualdad, una en términos de la operación de la mediana y la otra en términos de las operaciones de red y desigualdad, es el Teorema 1 en Birkhoff y Kiss ( Birkhoff, Kiss 1947 ).
  11. ↑ Birkhoff, Kiss, 1947 , Teorema 2.
  12. ↑ Birkhoff, Kiss, 1947 , página 751.
  13. ↑ Avanna, 1961 .
  14. ↑ Knuth, 2008 llama a este conjunto ideal , pero un conjunto convexo en un gráfico de celosía distribuida no es lo mismo que un ideal de celosía .
  15. ↑ Imrich, Klavžar, 2000 , Teorema 2.40, página 77.
  16. ↑ Bandelt, Chepoi, 2008 , declaración 2.5, p.8; Chung, Graham, Saks, 1989 ; Feder, 1995 ; Knuth, 2008 , Teorema S, página 72.
  17. ↑ Infierno, 1976 .
  18. ↑ Imrich, Klavžar, 2000 , declaración 1.33, página 27.
  19. ↑ Bandelt, 1984 ; Imrich, Klavžar, 2000 , Teorema 2.39, p.76; Knuth, 2008 , página 74.
  20. ↑ Una técnica que culmina en el Lema 7.10 en la página 218 del artículo es usar el algoritmo de Chiba y Nishizeki ( Chiba, Nishizeki 1985 ) para obtener una lista de todos los ciclos de longitud 4 en un gráfico G , y que crea un gráfico que tiene aristas como vértices el grafo G y como aristas sus lados opuestos de un ciclo de 4 aristas. Los componentes conectados de estos gráficos se utilizan para formar las coordenadas del hipercubo. Un algoritmo equivalente es el de Knuth ( Knuth 2008 ), Algorithm H, p.69.
  21. ↑ Para conocer el algoritmo de reconocimiento de gráficos medianos, consulte Jha, Slutzki, 1992 , Imrich, Klavžar, 1998 y Hagauer, Imrich, Klavžar, 1999 . Para el algoritmo de reconocimiento de gráficos sin triángulos, consulte Itai, Rodeh, 1978 , Chiba, Nishizeki, 1985 y Alon, Yuster, Zwick, 1995 .
  22. ↑ Alon, Yuster, Zwick, 1995 . El algoritmo se basa en la multiplicación rápida de matrices . Aquí m  es el número de aristas en el gráfico, y una "O" grande oculta un factor constante grande. El mejor algoritmo práctico de reconocimiento de triángulos requiere un tiempo O( m 3/2 ). Para el reconocimiento de gráficos medianos, la restricción de tiempo se puede expresar en términos de m o n (el número de vértices), como m = O ( n log n ).
  23. ↑ Mulder, Schrijver, 1979 describió una versión de este método para sistemas de características que no requieren vértices ocultos, mientras que Barthélémy, 1989 proporcionó la versión completa. Los recuentos de Buneman se nombran en Dress, Hendy, Huber, Moulton, 1997 y Dress, Huber, Moulton, 1997 .
  24. ↑ Mulder, Schrijver, 1979 .
  25. ↑ Škrekovski, 2001 .
  26. ↑ Mulder, 1980 .

Notas

Enlaces