CICLOS Y CIRCUITOS DE GRAFOS

Ciclo, es una cadena simple, cuyos dos vértices extremos, inicial y terminal, coinciden (no tiene en cuenta la orientación). Si queremos describir la orientación en un ciclo designamos como: u+ = {ui : ui orientada en el sentido del ciclo} u- = {ui : ui orientada en el sentido contrario al ciclo} 

Ciclo elemental, es un ciclo donde no se repite ningún vértice (salvo el primero que coincide con el último). Lo notamos uE = (u1,...,un). 

Propiedad 1: Todo ciclo uC es una suma de ciclos elementales sin aristas comunes. 

Propiedad 2: Un ciclo es elemental si y solo si es un ciclo minimal (es decir que no se pueden deducir otros ciclos por supresión de aristas).

Seudociclo, es una cadena donde los extremos coinciden pero que una misma arista puede figurar más de una vez (también consecutivamente). 

Cociclo del conjunto de vértices A, es el conjunto de aristas incidentes a A, del tipo I(A) no vacío y particionado en dos clases I+(A) y I-(A). 

Ciclo Euleriano es aquel que incluye todas las aristas del grafo una sola vez, conteniendo cada vértice por lo menos una vez. 

Cadena Euleriana, es aquella que recorre todas las aristas una sola vez ( = simple) tocando todos los vértices del grafo. 

Todo multigrafo que posee un ciclo Euleriano es conexo y todos sus vértices tienen grado par . 

A partir del siguiente ejemplo daremos una idea del mecanismo utilizado por Euler para demostrar que la conexidad y el grado par de todos los vértices de un multigrafo, son condiciones necesarias y suficientes para garantizar la existencia de un ciclo Euleriano. Tenemos este grafo que es conexo y sus vértices tienen grado par.

1) Primero se comienza por trazar un camino simple desde un vértice, p. ej a. Supongamos que recorremos a-d-j-n-o-k-l-h-f-e-b-a. Volvimos a a.

La propiedad del grado par, significa que siempre podemos abandonar cada vértice al que entramos, exepto a. Es decir que cualquier cadena que trazemos desde a debe volver a a, formando un ciclo.

2) Las restantes aristas del grafo inicial , conforman un grafo no conexo, pero todos sus vértices mantienen el grado par, ya que al retirar el ciclo encontrado, se redujo cada grado en una cantidad par . Cada subgrafo conexo posee un ciclo Euleriano: d-c-i-j-k-e-d y h-g-m-h

. 3) Estos dos ciclos pueden ser insertados en el ciclo encontrado en 2) en los vértices comunes d y h respectivamente, originando un ciclo Euleriano a-d-c-i-j-k-e-d-j-n-o-kl-h-g-m-h-f-e-b-a, en el grafo original.

Cibegrafía:

https://www.fing.edu.uy/inco/grupos/bioinf/bioinfo1/teorico/grafos.pdf