stringtranslate.com

Orientación (teoría de grafos)

En teoría de grafos , una orientación de un grafo no dirigido es una asignación de una dirección a cada borde, convirtiendo el grafo inicial en un grafo dirigido .

Gráficos orientados

Un grafo dirigido se denomina grafo orientado si ninguno de sus pares de vértices está unido por dos aristas mutuamente simétricas. Entre los grafos dirigidos, los grafos orientados son aquellos que no tienen 2-ciclos (es decir, como máximo uno de ( x , y ) y ( y , x ) pueden ser flechas del grafo). [1]

Un torneo es una orientación de un grafo completo . Un poliárbol es una orientación de un árbol no dirigido . [2] La conjetura de Sumner establece que cada torneo con 2 n – 2 vértices contiene cada poliárbol con n vértices. [3]

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

1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, … (secuencia A001174 en la OEIS ).

Los torneos están en correspondencia uno a uno con los grafos dirigidos completos (grafos en los que hay una arista dirigida en una o ambas direcciones entre cada par de vértices distintos). Un grafo dirigido completo se puede convertir en un grafo orientado eliminando cada 2-ciclo, y a la inversa, un grafo orientado se puede convertir en un grafo dirigido completo agregando un 2-ciclo entre cada par de vértices que no sean puntos finales de una arista; estas correspondencias son biyectivas . Por lo tanto, la misma secuencia de números también resuelve el problema de enumeración de grafos para dígrafos completos. Hay una fórmula explícita pero complicada para los números en esta secuencia. [4]

Orientaciones restringidas

Una orientación fuerte es una orientación que da como resultado un grafo fuertemente conexo . Las orientaciones totalmente cíclicas estrechamente relacionadas son orientaciones en las que cada arista pertenece al menos a un ciclo simple. Una orientación de un grafo no dirigido G es totalmente cíclica si y solo si es una orientación fuerte de cada componente conexo de G. El teorema de Robbins establece que un grafo tiene una orientación fuerte si y solo si está conexo por 2 aristas ; los grafos desconectados pueden tener orientaciones totalmente cíclicas, pero solo si no tienen puentes . [5]

Una orientación acíclica es una orientación que da como resultado un grafo acíclico dirigido . Todo grafo tiene una orientación acíclica; todas las orientaciones acíclicas pueden obtenerse colocando los vértices en una secuencia y luego dirigiendo cada arista desde el punto final anterior en la secuencia hasta el punto final posterior. El teorema de Gallai-Hasse-Roy-Vitaver establece que un grafo 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. [6] Las orientaciones acíclicas y las orientaciones totalmente cíclicas están relacionadas entre sí por la dualidad planar . Una orientación acíclica con una única fuente y un único sumidero se denomina orientación bipolar . [7]

Una orientación transitiva es una orientación tal que el grafo dirigido resultante es su propio cierre transitivo . Los grafos con orientaciones transitivas se denominan grafos de comparabilidad ; pueden definirse a partir de un conjunto parcialmente ordenado haciendo que dos elementos sean adyacentes siempre que sean comparables en el orden parcial. [8] Una orientación transitiva, si existe, se puede encontrar en tiempo lineal. [9] Sin embargo, probar si la orientación resultante (o cualquier orientación dada) es realmente transitiva requiere más tiempo, ya que es equivalente en complejidad a la multiplicación de matrices .

Una orientación euleriana de un grafo no dirigido es una orientación en la que cada vértice tiene el mismo grado de entrada y de salida. Las orientaciones eulerianas de los grafos de cuadrícula surgen en la mecánica estadística en la teoría de los modelos de tipo hielo . [10]

Una orientación pfaffiana tiene la propiedad de que ciertos ciclos de longitud par en el grafo tienen un número impar de aristas orientadas en cada una de las dos direcciones alrededor del ciclo. Siempre existen para grafos planares , pero no para otros grafos determinados. Se utilizan en el algoritmo FKT para contar las coincidencias perfectas. [11]

Véase también

Referencias

  1. ^ Diestel, Reinhard (2005), "1.10 Otras nociones de grafos", Teoría de grafos (PDF) (3.ª ed.), Springer , ISBN 978-3-540-26182-7.
  2. ^ Rebane, George; Pearl, Judea (1987), "La recuperación de poliárboles causales a partir de datos estadísticos", Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, EE. UU., julio de 1987 , págs. 222–228, arXiv : 1304.2736.
  3. ^ Conjetura del torneo universal de Sumner, Douglas B. West, consultado el 2 de agosto de 2012.
  4. ^ Harary, Frank ; Palmer, Edgar M. (1973), "Fórmula 5.4.13", Enumeración gráfica , Nueva York: Academic Press, pág. 133, MR  0357214.
  5. ^ Robbins, HE (1939), "Un teorema sobre grafos, con una aplicación a un problema de control de tráfico", The American Mathematical Monthly , 46 (5): 281–283, doi :10.2307/2303897, hdl : 10338.dmlcz/101517 , JSTOR  2303897.
  6. ^ Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "Teorema 3.13", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Sr.  2920058.
  7. ^ de Fraysseix, Hubert; Ossona de Mendez, Patrice ; Rosenstiehl, Pierre (1995), "Orientaciones bipolares revisitadas", Discrete Applied Mathematics , 56 (2–3): 157–179, doi : 10.1016/0166-218X(94)00085-R , MR  1318743.
  8. ^ Ghouila-Houri, Alain (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une Relations d'ordre", Les Comptes rendus de l'Académie des sciences , 254 : 1370 –1371, SEÑOR  0172275.
  9. ^ McConnell, RM; Spinrad, J. (1997), "Orientación transitiva en tiempo lineal", 8º Simposio ACM-SIAM sobre algoritmos discretos , págs. 19-25.
  10. ^ Mihail, M.; Winkler, P. (1996), "Sobre el número de orientaciones eulerianas de un grafo", Algorithmica , 16 (4–5): 402–414, doi :10.1007/s004539900057, MR  1407581.
  11. ^ Thomas, Robin (2006), "Un estudio de las orientaciones pfaffianas de los grafos" (PDF) , Congreso Internacional de Matemáticos. Vol. III , Eur. Math. Soc., Zúrich, pp. 963–984, doi :10.4171/022-3/47, ISBN 978-3-03719-022-7, Sr.  2275714

Enlaces externos