Buen árbol de expansión

Condiciones de un buen árbol de expansión

En el campo matemático de la teoría de grafos , un buen árbol de expansión ^[1] de un grafo planar incrustado es un árbol de expansión con raíz cuyos bordes que no son árboles satisfacen las siguientes condiciones. ${\displaystyle T}$ ${\displaystyle G}$ ${\displaystyle G}$

• no hay ningún borde que no sea un árbol donde y se encuentren en un camino desde la raíz hasta una hoja, ${\displaystyle (u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle T}$
• Las aristas incidentes a un vértice se pueden dividir por tres conjuntos y , donde, ${\displaystyle v}$ ${\displaystyle X_{v},Y_{v}}$ ${\displaystyle Z_{v}}$
  • ${\displaystyle X_{v}}$Es un conjunto de bordes no arbóreos, terminan en zona roja
  • ${\displaystyle Y_{v}}$es un conjunto de bordes de árboles, son hijos de ${\displaystyle v}$
  • ${\displaystyle Z_{v}}$Es un conjunto de bordes no arbóreos, terminan en zona verde

Definición formal

Fuente: ^{[1] [2]}

Una ilustración para y conjuntos de bordes. ${\displaystyle X_{v},Y_{v}}$ ${\displaystyle Z_{v}}$

Sea un grafo plano. Sea un árbol de expansión con raíz de . Sea la ruta en desde la raíz hasta un vértice . La ruta divide a los hijos de , , excepto , en dos grupos; el grupo izquierdo y el grupo derecho . Un hijo de está en el grupo y se denota por si la arista aparece antes de la arista en el orden en el sentido de las agujas del reloj de las aristas incidentes a cuando el ordenamiento se inicia desde la arista . De manera similar, un hijo de está en el grupo y se denota por si la arista aparece después de la arista en el orden en el sentido de las agujas del reloj de las aristas incidentes a cuando el ordenamiento se inicia desde la arista . El árbol se llama un buen árbol de expansión ^[1] de si cada vértice de satisface las siguientes dos condiciones con respecto a . ${\displaystyle G_{\phi }}$ ${\displaystyle T}$ ${\displaystyle G_{\phi }}$ ${\displaystyle P(r,v)=(r=u_{1}),u_{2},\ldots ,(v=u_{k})}$ ${\displaystyle T}$ ${\displaystyle r}$ ${\displaystyle v\neq r}$ ${\displaystyle P(r,v)}$ ${\displaystyle u_{i}}$ ${\displaystyle (1\leq i<k)}$ ${\displaystyle u_{i+1}}$ ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle u_{i}}$ ${\displaystyle L}$ ${\displaystyle u_{i}^{L}}$ ${\displaystyle (u_{i},x)}$ ${\displaystyle (u_{i},u_{i+1})}$ ${\displaystyle u_{i}}$ ${\displaystyle (u_{i},u_{i+1})}$ ${\displaystyle x}$ ${\displaystyle u_{i}}$ ${\displaystyle R}$ ${\displaystyle u_{i}^{R}}$ ${\displaystyle (u_{i},x)}$ ${\displaystyle (u_{i},u_{i+1})}$ ${\displaystyle u_{i}}$ ${\displaystyle (u_{i},u_{i+1})}$ ${\displaystyle T}$ ${\displaystyle G_{\phi }}$ ${\displaystyle v}$ ${\displaystyle (v\neq r)}$ ${\displaystyle G_{\phi }}$ ${\displaystyle P(r,v)}$

• [Cond1] no tiene un borde que no sea de árbol , ; y ${\displaystyle G_{\phi }}$ ${\displaystyle (v,u_{i})}$ ${\displaystyle i<k}$
• [Cond2] los bordes incidentes al vértice excluido se pueden dividir en tres conjuntos disjuntos (posiblemente vacíos) y satisfacer las siguientes condiciones (a)-(c) ${\displaystyle G_{\phi }}$ ${\displaystyle v}$ ${\displaystyle (u_{k-1},v)}$ ${\displaystyle X_{v},Y_{v}}$ ${\displaystyle Z_{v}}$
  • (a) Cada uno de y es un conjunto de aristas consecutivas que no son de árbol y es un conjunto de aristas consecutivas de árbol. ${\displaystyle X_{v}}$ ${\displaystyle Z_{v}}$ ${\displaystyle Y_{v}}$
  • (b) Los bordes del conjunto , y aparecen en el sentido de las agujas del reloj en este orden desde el borde . ${\displaystyle X_{v}}$ ${\displaystyle Y_{v}}$ ${\displaystyle Z_{v}}$ ${\displaystyle (u_{k-1},v)}$
  • (c) Para cada arista , está contenido en , , y para cada arista , está contenido en , . ${\displaystyle (v,v')\in X_{v}}$ ${\displaystyle v'}$ ${\displaystyle T_{u_{i}^{L}}}$ ${\displaystyle i<k}$ ${\displaystyle (v,v')\in Z_{v}}$ ${\displaystyle v'}$ ${\displaystyle T_{u_{i}^{R}}}$ ${\displaystyle i<k}$

    

    Un gráfico plano (arriba), un buen árbol de expansión de (abajo) los bordes sólidos son parte de un buen árbol de expansión y los bordes punteados son bordes que no son del árbol con respecto a . ${\displaystyle G_{\phi }}$ ${\displaystyle T}$ ${\displaystyle G_{\phi }}$ ${\displaystyle G_{\phi }}$ ${\displaystyle T}$

Aplicaciones

En el dibujo monótono de gráficos, ^[2] en la representación de gráficos con 2-visibilidad. ^[1]

Cómo encontrar un buen árbol de expansión

Todo grafo planar tiene una incrustación tal que contiene un buen árbol de expansión. Un buen árbol de expansión y una incrustación adecuada se pueden encontrar en tiempo lineal. ^[1] No todas las incrustaciones de contienen un buen árbol de expansión. ${\displaystyle G}$ ${\displaystyle G_{\phi }}$ ${\displaystyle G_{\phi }}$ ${\displaystyle G}$ ${\displaystyle G}$

Véase también

• Árbol de expansión
• Realizador de Schnyder

Referencias

1. Hossain, Md. Iqbal; Rahman, Md. Saidur (23 de noviembre de 2015). "Buenos árboles de expansión en el dibujo de grafos". Ciencias de la Computación Teórica . 607 : 149–165. doi : 10.1016/j.tcs.2015.09.004 .
2. Hossain, Md Iqbal; Rahman, Md Saidur (28 de junio de 2014). "Dibujos de cuadrícula monótona de gráficos planares". Frontiers in Algorithmics . Apuntes de clase en informática. Vol. 8497. Springer, Cham. págs. 105–116. arXiv : 1310.6084 . doi :10.1007/978-3-319-08016-1_10. ISBN 978-3-319-08015-4.S2CID10852618  .​