Generando todos los H-paseos Eulerianos a partir de uno dado

Ponente(s): Juana Imelda Villarreal Valdés

Sea G una multigráfica sin lazos, y H una gráfica posiblemente con lazos. Decimos que G es una multigráfica H-coloreada si existe una función c: A(G) → V(H). Un camino (respectivamente, trayectoria, paseo) W = (v_0, e_0, v_1, e_1, . . . , e_{k−1}, v_k) en G es un H-camino (respectivamente, H-trayectoria, H-paseo) si y sólo si (c(e_0), c(e_1), . . . , c(e_{k−2}), c(e_{k−1})) es un camino en H. W es un H-camino cerrado (respectivamente H-paseo cerrado) si y sólo si W es un H-camino (respectivamente, H-paseo) tal que v_0 = v_k, y c(e_{k−1})c(e_0)∈ A(H). Decimos que un H-paseo, T, es un H-paseo Euleriano si A(T) = A(G). Note que un paseo propiamente coloreado es un H-paseo cuando H es una gráfica completa sin lazos. Como un caso particular si H es la gr aca K_2 entonces G es una multigráfica 2-arista-coloreada. En 1995 Pevzner define las transformaciones de orden, las cuales permiten generar todos los paseos Eulerianos propiamente coloreados de una multigráfica 2-arista-coloreada, iniciando desde alguno. En esta platica se explicarán algunas condiciones suficientes sobre el coloreado de aristas de G para obtener todos los H-paseos Eulerianos, comenzando por uno fijo. Y se proporcionará un algoritmo para hacerlo.