Teor A De Grafos

Teoría de Grafos

Tania Guzmán García
Luis González Varela
Alexandre González Rivas

Índice:
1. Introducción
2. Conceptos matemáticos con
ejemplos
3. Explicación del modelo ilustrada
con un ejemploIntroducción :
El primer ejemplo de trabajo con grafos fue este
trabajo que surgió para resolver un problema en la
ciudad de Königsberg (Rusia). La ciudad estaba
dividida en cuatro partes por dosbrazos del río
Pregel estando conectadas por siete puentes.
La pregunta que se hizo L. Euler fue: ¿Es posible
recorrer los siete puentes pasando por todos ellos
una única vez, partiendo y llegando almismo
sitio?

Conceptos matemáticos :
Grafo. Informalmente, un grafo es
un conjunto de objetos llamados
vértices o nodos unidos por enlaces
llamados aristas o arcos, que
permiten representarrelaciones
binarias entre elementos de un
conjunto.

Tipos:
Grafo simple:
Multigrafo:

Pseudografo:

Grafo dirigido:

Terminología:
Etiquetado. Distinción que se hace a los vértices
y/o aristas mediante unamarca que los hace
unívocamente distinguibles del resto, es decir,
asignarle a cada vértice o arista un nombre.
Adyacencia. Se dice que dos vértices son
adyacentes si hay una arista que los conecteentre ellos.
Grado de un vértice. El grado de un vértice es
un número natural de 0 al infinito que designa el
número de aristas le conectan con otros vértices.

Incidencia. Una arista es incidente a unvértice
si ésta lo une a otro.
Ponderación. Corresponde a una función que a
cada arista le asocia un valor (costo, peso, longitud,
etc.), para aumentar la expresividad del modelo.

Camino. Un caminoes una secuencia de aristas que
comienzan en un vértice del grafo y recorren parte o la
totalidad del grafo conectando vértices adyacentes.

Circuito. Cuando existe un camino que empieza
y acaba en elmismo vértice.
Isomorfismo. Si dos grafos son isomorfos sólo varía la
apariencia, es decir, que se mantienen las adyacencias,
estructura, caminos, ciclos, número de vértices y número de
aristas....