GRAFOS

MATEMÁTICA DISCRETA.
GRAFOS
Muchas situaciones de la vida real pueden ser esquematizadas por medio de diagramas construidos por puntos (vértices o nodos) y líneas (aristas) que conectan algunospares de vértices. Eventualmente, alguna línea puede unir un vértice consigo misma.
Estos esquemas, que facilitan la comprensión del problema a resolver, aparecen frecuentemente en diferentesdisciplinas y bajo nombres diversos, por ejemplo: redes (en ingeniería, economía), sociogramas (en sicología), organigramas (en economía y planificación), diagramas de flujo (en programación), etc.
La teoríaque se ocupa del estudio de estos diagramas se conoce con el nombre de Teoría de Grafos.
Los grafos son estructuras discretas que constan de vértices y de aristas que conectan entre si los vértices.El número de vértices del grafo G se denomina orden del grafo. El número de lados o aristas del grafo G se conoce como tamaño del grafo. Un grafo es finito si los vértices y aristas son finitos.
Ungrafo G es un par ordenado (V, A) donde V es un conjunto (cuyos elementos son llamados vértices) y A es otro conjunto, que puede tener elementos repetidos (cuyos elementos son llamados aristas) y,donde cada arista es de la forma .
Geométricamente, un grafo G es un conjunto de puntos en el espacio, algunos de los cuales están unidos entre sí mediante líneas. Así, por ejemplo la siguiente figuraes un grafo. A


B

C D
Este grafo puede representar diferentes situaciones de la vida real. Podría simbolizar un mapa de carreteras, un circuito electrónico, unamolécula química, etc.
Es importante comentar que un grafo contiene únicamente información topológica, es decir, información sobre conectividades entre puntos, pero carece de información geométrica enel sentido de distancias, ángulos, etc.
Si dos vértices están unidos por una misma arista, se dice que son adyacentes. Por otra parte, se dice que dos lados son adyacentes si tienen algún vértice...