Orientación (teoría de grafos)

La orientación de un gráfico no dirigido es la asignación de direcciones a cada borde, lo que convierte el gráfico original en un gráfico dirigido .

Grafos dirigidos

Un grafo dirigido se llama dirigido si ninguno de sus pares de vértices está conectado por dos aristas simétricas (multidireccionales). Entre los gráficos dirigidos, estos gráficos se distinguen por la ausencia de 2 ciclos (es decir, solo uno de los arcos ( x , y ) y ( y , x ) puede estar presente en el gráfico) [1] [2] .

El torneo es la orientación del gráfico completo . Polytree es la orientación de un árbol no dirigido [3] . La conjetura de Sumner establece que cualquier torneo de vértices contiene cualquier poliárbol con n vértices [4] .

El número de grafos dirigidos no isomorfos con n vértices (para n =1, 2, 3, …) es

una; 2; 7; 42; 582; 21.480; 2.142.288; 575.016.219; 415.939.243.032; … (secuencia A001174 en OEIS ).

Los gráficos dirigidos están en una correspondencia uno a uno con los gráficos dirigidos completos (gráficos que tienen un arco dirigido entre cualquier par de vértices distintos). Un grafo dirigido completo se puede convertir en un grafo dirigido eliminando todos los 2 ciclos, y viceversa, un grafo dirigido se puede convertir en un grafo dirigido completo agregando un 2 ciclo entre cada par de vértices que no son extremos de ningún arco. Estas correspondencias son biyectivas . Por lo tanto, la misma secuencia de números resuelve el problema de enumeración de grafos para dígrafos completos. Hay una fórmula explícita pero compleja para los números en esta secuencia [5] .

Orientaciones limitadas

Una orientación fuerte es una orientación que resulta en un dígrafo fuertemente conectado . Las orientaciones completamente cíclicas estrechamente relacionadas son orientaciones en las que cada arco pertenece al menos a un ciclo simple. Una orientación de un gráfico no dirigido G es completamente cíclica si y solo si es una orientación fuerte de cualquier componente conexa de G. El teorema de Robbins establece que un gráfico tiene una fuerte orientación si y solo si está conectado por 2 aristas . Los grafos desconectados pueden tener orientaciones completamente cíclicas, pero solo si no tienen puentes [6] .

Una orientación acíclica es una orientación que da como resultado un gráfico acíclico dirigido . Cualquier gráfico tiene una orientación acíclica. Todas las orientaciones acíclicas se pueden obtener colocando vértices en una fila y luego dirigiendo un arco desde un vértice anterior a uno posterior en esa fila. El teorema de Gallai-Hasse-Roy-Vitaver establece que un gráfico tiene una orientación acíclica en la que el camino más largo tiene como máximo k vértices si y solo si puede colorearse con como máximo k colores [7] . Las orientaciones acíclicas y las orientaciones completamente cíclicas están relacionadas entre sí por la dualidad plana . Una orientación acíclica con una sola fuente y un solo sumidero se denomina orientación bipolar [8] .

Una orientación transitiva es una orientación tal que el grafo dirigido resultante es su clausura transitiva . Los gráficos con orientaciones transitivas se denominan gráficos de comparabilidad . Se pueden determinar a partir de un conjunto parcialmente ordenado haciendo dos elementos adyacentes en todos los casos en que sean comparables en orden parcial [9] . Una orientación transitiva, si existe, se puede encontrar en el tiempo lineal [10] . Sin embargo, comprobar si la orientación resultante (o cualquier orientación dada) es realmente transitiva lleva más tiempo, ya que es equivalente en complejidad a la multiplicación de matrices .

La orientación de Euler de un gráfico no dirigido es una orientación en la que cada vértice tiene el mismo grado de entrada y salida . La orientación de Euler de las redes aparece en mecánica estadística en la teoría de modelos de tipo hielo [11] .

La orientación de Pfaffian tiene la propiedad de que ciertos ciclos de longitud par en un gráfico tienen un número impar de arcos en dos direcciones diferentes. Tales orientaciones siempre existen para gráficos planos , pero no siempre para otros tipos de gráficos. Esta orientación se utiliza en el algoritmo FKT para contar coincidencias perfectas [12] .


Notas

  1. ↑ Diéstel, 2005 .
  2. ↑ Cabe señalar que en la traducción del libro de Distel, orientado se traduce como dirigido, y dirigido se traduce como orientado, es decir, se reordenan los conceptos. Esto puede generar confusión. En este artículo, como en otros artículos de Wikipedia, las definiciones se toman de la traducción al ruso.
  3. ↑ Rebane, Perla, 1987 , pág. 222–228.
  4. ↑ Conjetura del Torneo Universal de Sumner Archivado el 27 de febrero de 2014 en Wayback Machine , Douglas B. West, consultado el 2 de agosto de 2012.
  5. ↑ Harary, Palmer, 1973 , pág. 133.
  6. ↑ Robbins, 1939 , pág. 281–283.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , p. 42.
  8. ↑ de Fraysseix, Ossona de Méndez, Rosentiehl, 1995 , p. 157–179.
  9. ↑ Ghouila-Houri, 1962 , pág. 1370–1371.
  10. ↑ McConnell, Spinrad, 1997 , pág. 19–25.
  11. ↑ Michael y Winkler 1992 , pág. 138–145.
  12. ↑ Tomás, 2006 , pág. 963–984.

Literatura

Enlaces