Unidad 6 Matematicas Discretas

Instituto Tecnológico Superior de los Ríos
Balancán, Tabasco



NOMBRE DEL ALUMNO: EDGAR DIAZ VELASCO



CARRERRA: ING. EN SISTEMAS COMPUTACIONALES



CATEDRATICO: DANY CAMBRANO ARCOS


UNIDAD 6
TEORIA DE GRAFOS





FECHA: 12 DE NOVIEMBRE DEL 2012

INDICE
Contenido
UNIDAD 6 3
TEORIA DE GRAFOS 3
COMPONENTES DE UN GRAFO (VÉRTICES, ARISTAS, BRAZOS, VALENCIA) 3TIPOS DE GRAFOS (SIMPLES, COMPLETOS, BIPARTIDOS, PLANOS, CONEXOS, PONDERADOR) 4
REPRESENTACION DE LOS GRAFOS 6
REPRESENTACIÓN MATEMÁTICA DE LOS GRAFOS 7
REPRESENTACIÓN COMPUTACIONAL DE LOS GRAFOS 8
EL CAMINO MAS CORTO 9
ARBOLES 11
COMPONENTES (RAIZ, HOJA, PADRE, HIJO, DESCENDIENTES, ANCENTROS) 11
PROPIEDADES DE LOS ARBOLES 12
CLASIFICACION (ALTURA, NUMERO DE NODOS) 12
RECORRIDO DE UN ARBOL 13BIBLIOGRAFIA 15

 
UNIDAD 6
TEORIA DE GRAFOS

Los grafos son representaciones de las redes, y por medio de ellos se puede expresar en forma visual y sencilla la relación entre los elementos de distinto tipo, por ejemplo se pueden usar para representar la estructura de una empresa en lo que se conoce como “organigrama”, o bien, para modelar una red eléctrica, telefónica, de carreteras, deagua potable, de alcantarillado, etc. Los vértices pueden ser postes, transformadores, teléfonos, ciudades, centrales telefónicas, válvulas, registros, y las aristas que tienen relación entre estos vértices pueden ser cables, tubos y carreteras, entre otras cosas. Por medio de la teoría de grafos, se pueden aprovechar mejor los recursos eliminando conexiones redundantes y reduciendo costos ydistancias.
COMPONENTES DE UN GRAFO (VÉRTICES, ARISTAS, BRAZOS, VALENCIA)
Un grafo (G) es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L).
Considérese el siguiente grafo:

A partir de esta figura se definen los siguientes elementos:
Vértices (Nodos):
Se indican por medio de un pequeño círculo y se les asigna un número o letra. En el grafo anterior los vérticesson: V = (a, b, c, d).
Lados (ramas o aristas):
Son las líneas que unen un vértice con otro y se les asigna una letra, un número o una combinación de ambos. En el grafo anterior los lados son: L = (1, 2, 3, 4, 5, 6).
Lados Paralelos:
Son aquellas aristas que tienen relación con un mismo par de vértices. En el grafo anterior los lados paralelos son: P = (2, 3).
Lazo:
Es aquella arista que salede un vértice y regresa al mismo vértice. En el grafo anterior se tiene el lazo: A = (6).
Valencia de un vértice:
Es el número de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:
Valencia (a) = 2
Valencia (b) = 4
Valencia (c) = 2
Valencia (d) = 3
Hay que observar como en el caso del vértice (d) el lazo solo se considera una vez, entrada osalida pero no ambos.
TIPOS DE GRAFOS (SIMPLES, COMPLETOS, BIPARTIDOS, PLANOS, CONEXOS, PONDERADOR)

Grafos simples:
Son aquellos grafos que no tienen lazos ni lados paralelos.


Grafo completo de n vértices (Kn):
Es el grafo en donde cada vértice está relacionado con todos los demás, sin lazos ni lados paralelos. Se indica como Kn, en donde n es el número de vértices de grafo.

Lavalencia en cada uno de los vértices de los grafos completos es (n-1), y el número de lados está dado por la expresión:
Núm. de lados = (n(n-1))/2
En donde n es el número de vértices del grafo.

Grafo bipartido:
Es el grafo que está compuesto por dos conjuntos de vértices, A = (aa, a2, a3,…. An), en donde los elementos del conjunto A se relacionan con los del conjunto B, pero entre los vérticesde un mismo conjunto no existe arista que los una.

Una forma muy sencilla de saber si un grafo es bipartido es aplicar el hecho de que nunca tiene un ciclo de longitud impar, además de que debe de cumplir con la característica mencionada anteriormente.

Grafos planos:
Un grafo plano es aquel que se puede dibujar en un solo plano y cuyas aristas no se cruzan entre sí.
Por otro lado la...