Navegante Solitario

UNIVERSIDAD POLITECNICA DE TAPACHULA


ING. DESARROLLADOR DE SOFTWARE

MATEMATICAS DISCRETAS

TEORÍA DE GRAFOS
















23 DE NOVIEMBRE DEL 2011.



Título Página
Introducción…………………………………………………………………..4

Conceptos básicos degrafos….………………………………………….5

Clasificación de los grafos………………………………………………….8

Representación de estructura……………………………………………19

Algoritmo de recorrido y búsqueda..…………….……………………….23

Árboles………………………………………………………………………25

Redes..………………………………………………………………………31

Aplicaciones de los grafos……...…………………………………………34

Conclusión…….……………………………………………………………35

Bibliografía…………………………………………………………………36La teoría de grafos tiene su origen en el problema de los siete puentes de Königsberg resuelto por Leonhard Euler, el cual se planteaba el problema de cómo recorrer los siete puentes una solo vez y regresar al mismo punto de salida.
Más tarde, otros problemas influyeron en el desarrollo de la teoría de grafos como el estudio de las redes eléctricas, la enumeración de isómeros dehidrocarburos, etc.
Hoy en día es rara la disciplina científica o humanística que no utiliza la teoría de grafos.
Dibujar un grafo para resolver un problema es un reflejo muy común, que no precisa conocimientos matemáticos. Un grafo se parece a la figura siguiente, y consta de vértices y de aristas que reúnen algunos de ellos.
En la teoría de los grafos, sólo se queda lo esencial del dibujo: la forma delas aristas no son relevantes, sólo importan sus extremidades (o cabos); la posición de los vertices tampoco, y se puede variar para obtener un grafo más claro, y hasta sus nombres se pueden cambiar. Estos cambios se llaman isomorfismos de grafos. Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy leíbles.

Grafo: Un grafo es un conjunto, no vacío, deobjetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas que pueden ser orientados o no.
Una arista “e” en un grafo asociada a vértices “a” y “b”, se dice, que es incidente en “a” y “b” y viceversa, que “a” y “b” son incidentes en “e”. Y por lo tanto que “a” y “b” son vértices adyacentes en “e”.
Si “G” es un grafo con vértices “V” y aristas “E”, entonces G = (V,E).
Ejemplo de un grafo:

1

2

3

4

5
a
b
c
d
e
f
g
h
i

1

2

3

4

5
a
b
c
d
e
f
g
h
i

Observamos:
V = {1, 2, 3, 4, 5} Vértices
A = {a, b, c, d, e, f, g, h, i } Aristas
G = { (1, 2), (3, 2), (5, 3), (4, 5), (1, 4), (2, 4), (2, 5), (1, 3), (5, 1)} Grafo

Lazo: Es una arista incidente en un sólo vértice. Ejemplo: a6 = (V5, V5).
AQUÍ ENCONTRAMOSARISTAS PARALELLAS
AQUÍ ENCONTRAMOS ARISTAS PARALELLAS
AQUÍ ENCONTRAMOS UN LAZO
AQUÍ ENCONTRAMOS UN LAZO

Aristas paralelas: Cuando dos o más aristas están asociadas con el mismo par de vértices. Ejemplo: las aristas a2 y a3 están asociadas al mismo par de vértices. Es decir: a2 = (V1, V3) y a3 = (V1, V3).

Grado o valencia: de un vértice “v”. Es el número de aristas incidentes en “v”.Como ejemplo en la figura anterior tenemos que:
V1 | V2 | V3 | V4 | V5 |
3 | 3 | 5 | 1 | 3 |

Vértice aislado: El vértice que no es incidente en alguna arista.
Ejemplo:

Subgrafos: Subgrafos son las partes en que se pueden dividir un grafo.

Ejemplo, algunos subgrafos de este grafo serían los siguientes:


Grafo dirigido: Llamado también dígrafo tienen un conjunto de vértices V(nodos) y un conjunto de aristas E (arcos o lados), tal que cada arista se asocia a un par ordenado de vértices.

Grafo no dirigido: Tienen un conjunto de aristas E (arcos o lados), tal que cada arista se asocia a un par no ordenado de vértices.
Ejemplo:

Grafo pesado, ponderado ó etiquetado: Un grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre,...