Algoritmo gamma

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 19 de enero de 2020; las comprobaciones requieren 2 ediciones .

El algoritmo gamma  es un algoritmo para aplanar un gráfico y verificar su planaridad a lo largo del camino .

Definiciones

Algoritmo

Coloque sobre el plano cualquier ciclo H del grafo G sin repeticiones de vértices.

  1. Construya todos los segmentos S 1 ,..,S k del gráfico G a partir de H .
  2. Si hay un segmento S i con una cara admisible  , selecciónelo.
  3. Si todos los segmentos tienen varias caras adicionales, seleccione cualquiera.
  4. Seleccione una cadena gamma arbitraria del segmento y ajústela en una cara admisible.
  5. Vaya al paso (2) agregando una cadena gamma al gráfico H.

Propiedades de las gráficas para el correcto funcionamiento del algoritmo

  1. El gráfico debe estar conectado .
  2. El gráfico debe tener al menos un ciclo .
  3. El gráfico no debe tener puentes , es decir, bordes, después de la eliminación de los cuales, el gráfico se divide en dos componentes conectados .

Si se viola la propiedad (1), entonces el gráfico debe apilarse por separado de acuerdo con los componentes conectados. Si se viola la propiedad (2), entonces el gráfico es un árbol y es trivial dibujar su aplanamiento.

El caso de violación de la propiedad (3) se considerará con más detalle. Si hay puentes en el gráfico, entonces deben cortarse, cada componente conectado debe aplanarse por separado y luego conectarse mediante puentes. Aquí puede surgir una dificultad: durante el proceso de colocación, los vértices finales del puente pueden estar dentro de un gráfico plano. Dibujemos un componente conectado y agreguemos otros secuencialmente. Cada nuevo componente conectado se dibujará en la cara que contiene el vértice final del puente correspondiente. Dado que el gráfico de conectividad por puentes de componentes conexas es un árbol, podremos obtener un empaquetamiento plano.

Teorema

El gráfico à es plano si y solo si el algoritmo gamma lo coloca en el plano.

Prueba

En la dirección opuesta, la prueba es obvia.

Vamos a demostrarlo directamente. Si el grafo Γ es plano, entonces el subgrafo H dispuesto en el plano puede completarse hasta el trazado del grafo Γ . En particular, para el último paso esto significa que el gráfico Γ está completamente dispuesto en el plano.

Sea la gráfica Γ plana. Entonces, cualquier ciclo del gráfico Γ se representa como un polígono cuando se apila. Este polígono está incluido en la disposición del gráfico Γ en el plano.

Deje que la afirmación sea verdadera hasta la enésima iteración del algoritmo.

Opciones:

  1. S cabe en la única cara de la gráfica H , la gráfica H se completa hasta el pliegue de la gráfica G , y en este pliegue el segmento S se encuentra en la única cara. En consecuencia, la incrustación de cualquier camino gamma C del segmento S en esta cara conduce a la unión del gráfico H con C , que puede extenderse a la teselación Г.
  2. Cada segmento tiene varias caras válidas.

Sea S  un segmento con caras admisibles F 1 y F 2 . El subgrafo H se completa al trazado del grafo Г por la hipótesis inductiva. En este caso, el segmento S encaja en una de las caras admisibles. Sin pérdida de generalidad, sea esta cara F 1 . Probemos que existe una extensión de H hasta el trazado de la gráfica à en la que el segmento S está en la cara F 2 . Dado que F 1 y F 2  son caras adicionales, ambas contienen todos los vértices de contacto del segmento S . Por lo tanto, todos los vértices de contacto del segmento S se encuentran en el conjunto de vértices comunes F 1 y F 2 . Sean S 1 ,..,S k  todos los segmentos contenidos en F 1 . Sean S ' 1 ,..,S ' m  todos los segmentos de F 2 que contienen uno de los vértices. Deje que el segmento S ' i tenga un vértice de contacto y otro vértice de contacto que no pertenezca a F 1 . Entonces las caras admisibles S ' i es la cara F 2 , y este es el supuesto del punto (2). De la contradicción se sigue que todos los vértices de contacto S ' i (similarmente a S i ) se encuentran en el conjunto de vértices de los segmentos S ' 1 ,.., S ' m .

Por lo tanto, en la colocación del gráfico G , es posible mover los segmentos S 1 ,..,S k a F 2 , y S ' 1 ,..,S ' m a F 1 , esto conducirá a la colocación del gráfico à en el que el segmento S está en la cara F 2 .

Por lo tanto, el algoritmo ajustará cualquier gráfico plano al plano. Que es lo que se requería.

Véase también

Literatura