Grafos

Introducción

Con este trabajo se pretende dar a conocer la unidad numero cinco del programa de matemáticas discretas con el fin de conocer lo que es un grafo, sus propiedad, los tipos que existen además de la definición de árboles junto con todas sus propiedades para al momento de aplicarlo conocerlo a fondo y saber el por que.

Grafos, Diágrafos y Multigrados

Un grafo consta de doscosas:
Un conjunto N cuyos elementos se llaman nodos, puntos o vértices.
Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas segmentos, aristas o arcos.
Denotaremos un grafo por G =(N, S) cuando queremos destacar las dos partes de G.
Los nodos u y v se llaman adyacentes si hay un segmento {u, v}.
Representaremos de una manera natural los grafos por diagramas en el plano. O sea,cada nodo v de N se representa por un punto (o pequeño círculo) y cada segmento s = {v1, v2} se representa por una curva que conecta sus terminales v1 y v2.

Dos vértices vi., vj son adyacentes si son los extremos de una arista, es decir, si el par de
Vértices V es un elemento de E.
[pic] V= {v1, v2, v3}
E= {v1v2, v2v3, v1v3}

#V es elnúmero de vértices.
#E es el número de aristas.
Un grafo es finito si #V es finito.

Tipos de grafos:
· Multigrafo: es un grafo con varias aristas entre dos vértices.
V= {v1, v2, v3}
E= {v1v2, v2v3, v2v3, v1v3, v1v3}
[pic]

Pseudo grafo: tiene aristas cuyos extremos coinciden (origen y fin en el mismo vértice),
Tales aristas se denominan lazos.
V= {v1, v2, v3}
E= {v1v1, v1v2, v2v2, v1, v3}[pic]
Dígrafo (grafo dirigido): A cada arista se le asigna un orden en sus extremos, en el
Dibujo se indica con una flecha. Los pares que forman los elementos de E están
Ordenados.
[pic]

V= {v1, v2, v3}
E= {v1v2, v2v3, v3v1}

Nodo
Si v es una Terminal de un segmento s, decimos que s es incidente en v. El grado de v, escrito gr (v),es igual al numero de segmentos que inciden en v. (Un nodo de grado cero, o sea un nodo que no pertenece a ningún segmento, se llama nodo aislado)
Teorema 1.- La suma de los grados de los nodos de un grafo es igual al doble del número de segmentos.

Caminos
En un grafo G es una sucesión finita de vértices y aristas alternos, donde cada arista
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 que contiene.
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 de vértices no hay ninguno repetido.
Un ciclo
Esun camino cerrado donde el primero y último vértice es el mismo (camino simple
Cerrado). En un multigrafo se considera ciclo a aquellos caminos cerrados que no
repiten aristas.
Un circuito
Es un camino cerrado que no repite aristas.
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 circuitoeuleriano.
Un grafo euleriano,
Es aquel grafo conexo que admite un circuito euleriano.
LEMA:
1. En un grafo euleriano, 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 euleriano si y solo si cada vértice tiene grado par.
LEMA:
3. Sea H un grafo tal que todo vérticede H tiene grado par. si u y v son dos vértices
de H que son adyacentes entonces existe un circuito g que contiene 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 una arista con extremo en el circuito anterior y repetir el proceso.
3. Unir los distintos...