En el estudio de los grafos planares , los árboles de flores son árboles con medias aristas dirigidas adicionales. Cada árbol de flores está asociado con una incrustación de un grafo planar. Los árboles de flores se pueden utilizar para muestrear grafos planares aleatorios. [1]
Un árbol de flores se construye a partir de un árbol con raíces incrustado en el plano añadiendo tallos que se abren y se cierran a los vértices. El número de tallos que se abren y se cierran debe coincidir. [2] Algunos autores exigen que los árboles de flores tengan raíces y establecen condiciones sobre qué tipo de tallos pueden llevar. [3] Los términos hojas y flores también se utilizan a veces para los tallos que se abren y se cierran. [3] [4]
Se puede construir un grafo plano incrustado a partir de un árbol de flores conectando cada tallo de apertura con un tallo de cierre. Se visitan los medios bordes recorriendo el grafo en el sentido de las agujas del reloj comenzando en un tallo de apertura. Si el árbol tiene raíces, generalmente se comienza en la raíz. El algoritmo es análogo al emparejamiento de paréntesis y utiliza una pila . En cada etapa, si el tipo del medio borde actual es el mismo que el medio borde en la parte superior de la pila, se empuja hacia la pila. Si los colores difieren, se saca la pila y se conectan los dos medios bordes. [4] Si orientamos los bordes agregados desde el tallo de apertura hasta el tallo de cierre, no tenemos bordes en sentido contrario a las agujas del reloj. Este proceso lleva tiempo lineal. [1]
De manera similar, una incrustación de un grafo plano con raíz puede codificarse como un árbol de flores. Si la raíz está en la esquina, esto puede hacerse en tiempo lineal. Los bordes de un grafo plano con raíz pueden orientarse de modo que haya un camino desde la raíz hasta cualquier vértice, pero no hay ciclos en sentido antihorario. En este caso, se puede usar un algoritmo de profundidad para convertirlo en un árbol de flores. Comenzando con el vértice raíz, observe cada borde incidente a él. Si apunta en dirección opuesta a nuestro vértice actual, córtelo, etiquetando la mitad del borde exterior como un tallo de cierre y la mitad del borde interior como un tallo de apertura. Si apunta hacia nuestro vértice actual, márquelo como para conservarlo y establezca su otro punto final como nuestro vértice actual. Continúe hasta que se hayan considerado todos los bordes. Si el mapa no tiene raíz en una esquina, construir el árbol de flores toma tiempo cuadrático. [1]
Los árboles de flores también se utilizan para generar aleatoriamente diagramas de nudos grandes . Los nudos se pueden representar mediante grafos planares de 4-regulares donde cada nodo está marcado como un cruce superior o inferior. Los árboles de flores se pueden utilizar para generar grafos planares de 4-regulares aleatorios. Sin embargo, estos no siempre dan diagramas de nudos ya que puede haber más de un componente. Esto se puede comprobar en tiempo cúbico . [5]
