Isoformismo de graficas

Tecnológico de la laguna.
Ingeniera Bertha Alicia Salazar castro

Materia: matemáticas discretas

Un camino
En un grafo G es una sucesión finita de vértices y aristas alternos, donde cadaarista
tiene por extremos los vértices adyacentes.
(v0, v0v1, v1, v1v2,..., vn-1, vn-1vn, vn)
A v0 y vn se les denomina extremos del camino.
Longitud del camino
Es el número de aristas quecontiene.
Camino cerrado
Los extremos coinciden, v0=vn.
En un grafo (no un multigrafo), un camino puede expresarse por la sucesión de vértices
(v0, v1,..., vn-1, vn)
Camino simple:
En la sucesión devértices no hay ninguno repetido.
Un ciclo
Es un camino cerrado donde el primero y último vértice son el mismo (camino simple
cerrado). En un multigrafo se considera ciclo a aquellos caminos cerradosque no
repiten aristas.
Un circuito
Es un camino cerrado que no repite aristas.
2.2. Grafos eulerianos y hamiltonianos
Un camino euleriano:
Es un camino que conecta todas las aristas,apareciendo cada una de ellas una sola vez,
si sus extremos coinciden se trata de un circuito euleriano.
Un grafo euleriano,
Es aquel grafo conexo que admite un circuito euleriano.
LEMA:
1. En un grafoeuleriano, todos los vértices tienen grado par.
2. Hay grafos conexos no eulerianos que admiten camino euleriano, si dos de sus
vértices tienen grado impar.
Teorema:
Un grafo conexo es eulerianosi y solo si cada vértice tiene grado par.
LEMA:
3. Sea H un grafo tal que todo vértice de H tiene grado par. si u y v son dos vértices
de H que son adyacentes entonces existe un circuito g quecontiene la arista uv.
Para saber si un grafo es euleriano:
1º Todos sus vértices tienen grado par.
2º Algoritmo para obtener el circuito euleriano:
1. Obtener un circuito euleriano.
2. Elegir unaarista con extremo en el circuito anterior y repetir el proceso.
3. Unir los distintos circuitos obtenidos y tendremos el circuito buscado.
En un grafo euleriano pueden existir varios circuitos...