Fusión de gráficos

En teoría de grafos , la fusión de una gráfica es una relación entre dos gráficas (una gráfica es la fusión de otra). Relaciones similares incluyen subgrafos y menores . Las fusiones pueden proporcionar una forma de reducir un gráfico a un gráfico más simple manteniendo intacta cierta estructura. La fusión se puede utilizar para estudiar las propiedades del gráfico original en un contexto más fácil de entender. Las aplicaciones incluyen incrustaciones, ^[1] computación de distribución de género, ^[2] y descomposiciones hamiltonianas .

Definición

Sean y dos gráficos con el mismo número de aristas donde tiene más vértices que . Entonces decimos que es una amalgama de si hay una biyección y una sobreyección y lo siguiente se sostiene:${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle H}$${\displaystyle G}$ ${\displaystyle \phi :E(G)\to E(H)}$ ${\displaystyle \psi :V(G)\to V(H)}$

• Si , son dos vértices en donde , y ambos y son adyacentes por el borde hacia adentro , entonces y son adyacentes por el borde hacia adentro .${\displaystyle x}$${\displaystyle y}$${\displaystyle G}$${\displaystyle \psi (x)\neq \psi (y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle e}$${\displaystyle G}$${\displaystyle \psi (x)}$${\displaystyle \psi (y)}$${\displaystyle \phi (e)}$${\displaystyle H}$
• Si es un bucle en un vértice , entonces es un bucle en .${\displaystyle e}$${\displaystyle x\in V(G)}$${\displaystyle \phi (e)}$${\displaystyle \psi (x)\in H}$
• Si se une , dónde , pero , luego hay un bucle activado . ^[3]${\displaystyle e}$${\displaystyle x,y\in V(G)}$${\displaystyle x\neq y}$${\displaystyle \psi (x)=\psi (y)}$${\displaystyle \phi (e)}$${\displaystyle \psi (x)}$

Tenga en cuenta que si bien puede ser un gráfico o un pseudógrafo , generalmente será el caso que sea ​​un pseudógrafo.${\displaystyle G}$${\displaystyle H}$

Propiedades

Los colores de los bordes son invariantes a la fusión. Esto es obvio, ya que todos los bordes entre los dos gráficos están en biyección entre sí. Sin embargo, lo que puede no ser obvio es que si es un gráfico completo de la forma , y coloreamos los bordes para especificar una descomposición hamiltoniana (una descomposición en caminos hamiltonianos , entonces esos bordes también forman una descomposición hamiltoniana en .${\displaystyle G}$${\displaystyle K_{2n+1}}$${\displaystyle H}$

Ejemplo

FIGURA 1: Una fusión de la gráfica completa en cinco vértices.

La figura 1 ilustra una fusión de . La invariancia de la coloración de los bordes y la descomposición hamiltoniana se puede ver claramente. La función es una biyección y se da como letras en la figura. La función se muestra en la siguiente tabla.${\displaystyle K_{5}}$${\displaystyle \phi }$${\displaystyle \psi }$

${\displaystyle v\in V(G)}$	${\displaystyle \psi (v)}$
${\displaystyle v_{1}}$	${\displaystyle u_{2}}$
${\displaystyle v_{2}}$	${\displaystyle u_{2}}$
${\displaystyle v_{3}}$	${\displaystyle u_{1}}$
${\displaystyle v_{4}}$	${\displaystyle u_{3}}$
${\displaystyle v_{5}}$	${\displaystyle u_{2}}$

Descomposiciones hamiltonianas

Una de las formas en que se pueden utilizar las amalgamaciones es encontrar descomposiciones hamiltonianas de gráficos completos con 2 n  + 1 vértices. ^[4] La idea es tomar un gráfico y producir una amalgama que tenga los bordes coloreados en colores y satisfaga ciertas propiedades (llamada descomposición hamiltoniana de contorno). Entonces podemos 'revertir' la amalgama y nos quedamos coloreados en una descomposición hamiltoniana.${\displaystyle n}$${\displaystyle K_{2n+1}}$

En ^[3] Hilton describe un método para hacer esto, así como un método para encontrar todas las descomposiciones hamiltonianas sin repetición. Los métodos se basan en un teorema que proporciona que establece (aproximadamente) que si tenemos un esquema de descomposición hamiltoniana, podríamos haber llegado a él comenzando primero con una descomposición hamiltoniana del gráfico completo y luego encontrando una amalgama para él.

Notas

1. Bruto, Tucker 1987
2. Bruto 2011
3. Hilton 1984
4. Bahmanian, Amin; Rodger, Chris 2012

Referencias

• Bahmánico, Amin; Rodger, Chris (2012), "¿Qué son las fusiones de gráficos?" , Universidad de Auburn
• Hilton, AJ W (1984), "Descomposiciones hamiltonianas de gráficos completos , Journal of Combinatorial Theory , Serie B 36, 125-134
• Gross, Jonathan L .; Tucker, Thomas W. (1987), Teoría de gráficos topológicos, Publicaciones de Courier Dover , 151
• Gross, Jonathan L. (2011), "Distribuciones de género de gráficos planos exteriores cúbicos" , Revista de algoritmos y aplicaciones de gráficos , vol. 15, no. 2, págs. 295–316