De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

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

Gráficos orientados [ editar ]

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

Un torneo es una orientación de un gráfico completo . Un polytree 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 polytree con n vértices. [3]

El número de gráficos orientados no isomórficos 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 gráficos dirigidos completos (gráficos en los que hay un borde dirigido en una o ambas direcciones entre cada par de vértices distintos). Un gráfico dirigido completo se puede convertir en un gráfico orientado eliminando cada 2 ciclos y, a la inversa, un gráfico orientado se puede convertir en un gráfico dirigido completo agregando un 2 ciclos entre cada par de vértices que no son puntos finales de un borde; estas correspondencias son biyectivas . Por lo tanto, la misma secuencia de números también resuelve el problema de enumeración de gráficos para dígrafos completos. Existe una fórmula explícita pero complicada para los números en esta secuencia. [4]

Orientaciones restringidas [ editar ]

Una orientación fuerte es una orientación que da como resultado un gráfico fuertemente conectado . Las orientaciones totalmente cíclicas estrechamente relacionadas son orientaciones en las que cada borde pertenece al menos a un ciclo simple. Una orientación de un grafo no dirigido G es totalmente cíclico si y sólo si es una fuerte orientación de cada componente conectado 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 gráficos 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 gráfico acíclico dirigido . Cada gráfico tiene una orientación acíclica; todas las orientaciones acíclicas pueden obtenerse colocando los vértices en una secuencia y luego dirigiendo cada borde desde el punto final anterior de la secuencia al punto final posterior. El teorema de Gallai-Hasse-Roy-Vitaver establece que una gráfica 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 totalmente cíclicas están relacionadas entre sí por dualidad plana.. Una orientación acíclica con una sola fuente y un solo sumidero se denomina orientación bipolar . [7]

Una orientación transitiva es una orientación tal que el gráfico dirigido resultante es su propio cierre transitivo . Los gráficos con orientaciones transitivas se denominan gráficos 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 gráfico 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 gráficos de cuadrícula surgen en la mecánica estadística en la teoría de modelos de tipo hielo . [10]

Una orientación de Pfaffian tiene la propiedad de que ciertos ciclos pares en el gráfico tienen un número impar de aristas orientadas en cada una de las dos direcciones alrededor del ciclo. Siempre existen para gráficos planos , pero no para algunos otros gráficos. Se utilizan en el algoritmo FKT para contar coincidencias perfectas. [11]

Ver también [ editar ]

  • Relación de Connex

Referencias [ editar ]

  1. ^ Diestel, Reinhard (2005), "1.10 Otras nociones de gráficos", Graph Theory (PDF) (3rd ed.), Springer , ISBN 978-3-540-26182-7.
  2. ^ Rebane, George; Pearl, Judea (1987), "La recuperación de poliarboles causales a partir de datos estadísticos", Proc. Tercera Conferencia Anual sobre Incertidumbre en Inteligencia Artificial (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. 133, MR 0357214 .
  5. ^ Robbins, HE (1939), "Un teorema sobre gráficos, 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  CS1 maint: parámetro desalentado ( enlace ).
  6. ↑ Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), "Teorema 3.13", Esparcimiento: Gráficos, Estructuras y Algoritmos , Algoritmos y Combinatoria, 28 , Heidelberg: Springer, p. 42, doi : 10.1007 / 978-3-642-27875-4 , hdl : 10338.dmlcz / 143192 , ISBN 978-3-642-27874-7, MR  2920058.
  7. ↑ de Fraysseix, Hubert; Ossona de Méndez, Patrice ; Rosenstiehl, Pierre (1995), "Orientaciones bipolares revisitadas", Matemáticas aplicadas discretas , 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 relationship d'ordre", Les Comptes rendus de l'Académie des sciences , 254 : 1370 –1371, MR 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 gráfico", Algorithmica , 16 (4–5): 402–414, doi : 10.1007 / s004539900057 , MR 1407581 .
  11. ^ Thomas, Robin (2006), "Un estudio de las orientaciones de gráficos de Pfaffian" (PDF) , Congreso Internacional de Matemáticos. Vol. III , Eur. Matemáticas. Soc., Zúrich, págs. 963–984, doi : 10.4171 / 022-3 / 47 , ISBN  978-3-03719-022-7, MR  2275714 CS1 maint: parámetro desalentado ( enlace )

Enlaces externos [ editar ]

  • Weisstein, Eric W. , "Orientación de gráficos" , MathWorld
  • Weisstein, Eric W. , "Gráfico orientado" , MathWorld