Teoria de graficas

En los últimos años se ha dedicado mucha atención a un área relativamente nueva de investigación matemática denominada teoría de gráficas. Las gráficas, que se definirán en breve, son útiles en el estudio de la forma en la cual se interrelacionan las componentes de las redes que surgen en el comercio, las ciencias sociales, la medicina y otras áreas más. Por ejemplo, las gráficas resultande utilidad en el estudio de las relaciones familiares en una tribu, la propagación de una enfermedad contagiosa o una red de vuelos comerciales que comunican a un número dado de ciudades importantes. La teoría de graficas es un tema de gran amplitud. En esta sección se presentaran únicamente algunas definiciones y se mostrara la cercanía de relación entre la teoría de gráficas y lateoría de matrices.
A continuación se ilustrara de qué manera surge una gráfica en la práctica
EJEMPLO 1 REPRESENTACION DE UN SISTEMA DE COMUNICACIÓN MEDIANTE UNA GRAFICA
Suponga que se esta analizando un sistema de comunicaciones unido por líneas telefónicas. En este sistema hay cinco acciones. En la siguiente tabla de indican la líneas disponibles en dirección ‘’a’ , y provenientes‘’de’’ las estaciones:
Estación | 1 | 2 | 3 | 4 | 5 |
1 | | • | | | |
2 | • | | | | • |
3 | | | | • | |
4 | | • | • | | |
5 | • | | | • | |

Por ejemplo la marca del cuadro (1,2) indica que hay una línea de la estación 1 a la estación 2. La información en la tabla se puede representar por una grafica dirigida como la que se ilustra en la figura 1.9.
En generaluna grafica dirigida es una colección de n puntos denominados vértices, denotados por V1, V2,… Vn, junto con un numero finito de aristas que unen distintos pares de vértices. Cualquier grafica dirigida se puede representar mediante una matriz de n * n en donde el numero de la posición ij es el numero de aristas que unen el vértice i con el vértice j.2
3
1

5 4

EJEMPLO 2 REPRESENTACION MATRICIAL DE UNA GRAFICA DIRIGIDA
La representación matricial dela gráfica en la figura 1.9 es:
0 1 0 0 0
1 0 0 0 1
A = 0 0 0 1 00 1 1 0 0
1 0 0 1 0

EJEMPLO 3 REPRESENTACION MATRICIAL DE DOS GRAFICAS DIRIGIDAS

Encuentre las representaciones matriciales de la graficas dirigidas en la figura 1.10.a





0 1 0 1 b
A = 0 0 0 1
0 1 0 1 0 0 0 1 0 1
0 1 0 00 0 0 0 1 1
A = 1 1 0 0 1 1
0 1 1 0 1 0
0 1 0 0 0 0...