Teoria de Grafos

TEORÍA DE GRAFOS

Los grafos son representaciones de las redes, y por medio de ellos se pueden expresar en forma visual y sencilla la relación entre 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, de agua potable, de alcantarillado, etc. Los vértices pueden ser postes, transformadores, teléfonos, ciudades, centrales telefónicas, válvulas, registros, y los 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 y distancias.

En computación los grafos se utilizan para mostrar las relaciones entre archivos (en las bases de datos), entre registros (en la estructura de datos), entre computadoras y entre redes como lo hace la red internet.

Los grafos son relaciones, que resultan muy utiles gracias a la forma en la que se les puede representar ya que es mas claro ver la relación entre dos elementos en un grafo que en una matriz o en un conjunto.

Componente de un Grafo

PARTES DE UN GRAFO

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értices son 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 numero 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 sale de 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 numero 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 del lazo solo se considera una vez, entrada o salida pero no ambos.

TIPOS DE GRAFOS (Simples, Completos, Bipartidos)

TIPOS DE GRAFOS

GRAFOS SIMPLES
Son aquellos grafos que no tienen lazos ni lados paralelos.

GRAFO COMPLETO DE N VÉRTICES (k_n)
Es el grafo en donde cada vértice está relacionado con todos los demás sin lazos ni lados paralelos. Se indica como k_n  en donde n es el número de vértices del grafo.

La valencia en cada uno de los vértices de los grafos completos es (n – 1), y el numero de lados esta dado por la expresión

                     Núm. De lados = n(n – 1)

                                                     2
en donde n es el numero de vértices del grafo.

COMPLEMENTO DE UN GRAFO (G‘)
Es el grafo que le falta al grafo G, de forma que entre ambos formas de grafo completo de n vértices. Este grafo no tiene lazos ni ramas paralelas.

GRAFO BIPARTIDO
es el grafo que esta compuesta por dos conjuntos de vértices, A ={a₁,a_2, a₃…, a_n} y B = {b₁,b₂,…, b_m} en donde los elementos del conjunto B, pero entre los vértices de 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 cumplir con la característica mencionada anteriormente.

GRAFO BIPARTIDO COMPLETO (K_{n, m})
Es el grafo que esta compuesto por dos conjuntos de vértices, uno de ellos A ={a₁,a_2, a₃…, a_n} Y otro B= {b₁,b₂,…, b_m), y en el cada vértice de A esta unido con todo los vértices de B, pero entre los vértices de un mismo conjunto no existe arista que los una. El grafo bipartido completo se indica como  k_{n, m}.

Representacion de los Grafos

REPRESENTACION MATRICIAL

El uso de matrices para representar sistemas de ecuaciones, relaciones o grafos permite una rápida y una clara manipulación de la información, así como el de determinar  algunas propiedades de los grafos que de otra manera serian mas difíciles el manejo de matrices, ya que se pueden tratar como arreglos o lista doblemente ligadas.

A continuación se describen las representaciones matriciales de los grafos 

MATRIZ DE ADYACENCIA (M_a)
Es una matriz cuadrada en la cual los vértices del grafo se indica como filas y como columnas: el orden de los vértices es el mismo que guardan las filas y las columnas de la matriz.se coloca un 1 como elemento de la matriz cuando existe una relación entre uno y otro vértice , o bien un 0 cuando no exista relación alguna.

MATRIZ DE INCIDENCIA (M₁)
En esta matriz se colocan los vértices del grafo como filas y las aristas como columnas.