Teorema de transición de árboles

VICTOR NICOLAS SCHVOLLNER; DANIEL A. JAUME; ADRIÁN PASTINE

Mendoza

Congreso; SUMA 2019; 2019

La secuencia de grados de un grafo es la lista de los grados de sus vértices. El 2-switch es una operación que altera las aristas de un grafo, pero preserva su secuencia de grados. En 1973 Berge demostró que dados dos grafos cualesquiera con la misma secuencia de grados, existe una sucesión de 2-switches que transforma uno en el otro. Esta es una herramienta fundamental para comprender los comportamientos de los grafos que comparten una secuencia de grados. En particular, si tomamos dos árboles, este teorema nos asegura poder transformar uno en el otro por medio de 2-switches, pero no asegura que los grafos intermedios sean árboles. En este trabajo presentamos un teorema del estilo de Berge, que nos permite convertir un árbol en cualquier otro por medio de 2-switches de manera tal que todos los grafos intermedios también sean árboles. Además, presentamos un algoritmo que permite determinar una sucesión de 2-switches que realiza la transformación.