Free Web Hosting Provider - Web Hosting - E-commerce - High Speed Internet - Free Web Page
Search the Web

Grafos
Principal Arriba Sumador Completo Teoria de numeros Grafos Directorios recursivos Metodos Combinatorios Grafos y arboles

 

Arriba

Introducción a la teoría de grafos

 

 

Tema 1 : GRAFOS

 

Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados por un conjunto de líneas (aristas). Otros conceptos básicos son:

 

Dos vértices son adyacentes si comparten la misma arista.

Los extremos de una arista son los vértices que comparte dicha arista.

Un grafo se dice que es finito si su numero de vértices es finito.

 

Clases de grafos

 

Un multigrafo es un grafo con varias aristas entre dos vértices.

Un pseudografo es un grafo en el que hay aristas (lazos) que tienen el mismo extremo.

Un digrafo es un grafo donde a cada arista se le indica un sentido mediante una flecha.

Los multidigrafos o pseudomultidigrafos son combinaciones de los anteriores.

 

Teoremas

 

Dos grafos son isomorfos si tienen el mismo numero de vértices y aristas y, estas se corresponden con los mismos extremos.

El grado del vértice de un grafo (gr) es el numero de aristas que tienen por extremo dicho vértice.

Si dos grafos son isomorfos, los vértices que se corresponden tienen el mismo grado.

 

Primer Teorema de la Teoría de Grafos: todo grafo contiene un numero par o cero de vértices de grado impar.

 

Un subgrafo es un grafo que esta contenido dentro de otro grafo y que se obtiene eliminando algunas aristas y vértices del grafo principal.

Un grafo es regular si todos sus vértices tienen el mismo grado k (k-regular).

Un grafo es completo si cada par de vértices son los extremos de una arista.

Dos grafos completos con el mismo numero de vértices son isomorfos.

 

 

Tema 2 : CAMINOS

 

Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo. Otras definiciones básicas son:

 

Los extremos son los vértices inicial y final del camino.

La longitud de un camino es el numero de aristas que contiene.

Un camino es cerrado si sus extremos coinciden.

Un camino es simple si en la sucesión de vértices no hay ninguno repetido.

Un ciclo es un camino cerrado donde los únicos vértices repetidos son el primero y el ultimo.

Un circuito es un camino cerrado que no repite aristas.

Si en un grafo existe un camino que conecta dos vértices distintos, entonces existe un camino simple con extremos en dichos vértices.

Un grafo es conexo si para cada par de vértices, existe un camino con extremos en dichos vértices.

 

Tipos de caminos

 

Camino euleriano: es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los vértices tienen grado impar.

Camino hamiltoniano: es un camino simple que contiene todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.

 

 

Tema 3 : EXPLORACION

 

Los grafos son utilizados con frecuencia para representar vías y redes de comunicación. Aquí se ofrece una forma matricial de representar un grafo. Se denomina matriz de adyacencia a una matriz cuyas entradas son unos y ceros siguiendo una ley: a cada entrada mij le corresponde la arista dada por vivj. Según sea grafo o digrafo será:

 

GRAFO

DIGRAFO

mij = 1 si vivj forma arista

mij = 1 si vivj forma arista orientación = vi ® vj

mij = 0 si vivj no forma arista

mij = 0 si vivj no forma arista orientación = vj ® vi

 

Teoremas

 

* Dos grafos con la misma matriz de adyacencia son isomorfos.

* Un árbol es un grafo conexo sin ciclos.

Un grafo es un árbol si y solo si cada dos vértices distintos se conectan por un único camino simple.

Un grafo es etiquetado si sus aristas tienen asignado un numero.

Se llama distancia de un grafo etiquetado a la longitud mínima del camino entre dos vértices dados.

 

Algoritmo de Dijkstra

 

Es un algoritmo que sirve para hallar la distancia mas corta entre dos vértices de un digrafo. Sus reglas básicas son:

 

Se toma el vértice inicial y se comprueba todas las direcciones posibles de salida.

Se elige entre todos los vértices el de la distancia mínima y se accede a el.

Desde el siguiente vértice se efectúa el mismo paso hasta llegar al vértice final.

El algoritmo recorre todos los caminos posibles hasta tener la distancia mínima entre ambos vértices.

 

 

Tema 4 : MAPAS

 

Definiciones

 

Un grafo se dice que es plano si admite una representación gráfica en el plano de modo que cada arista corta únicamente a otra arista en un vértice que sea extremo de ambas.

Una representación de un grafo con estas condiciones se dice que es un mapa.

Un mapa es conexo si el grafo que representa es conexo.

Las regiones son las divisiones en varias partes de un plano.

El grado de una región es la longitud del camino que la bordea.

La suma de los grados de las regiones de un mapa es igual al doble del numero de aristas del grafo que representa.

 

Formula de Euler

 

Sea M un mapa conexo con #R (numero de regiones) que representa al grafo G con #V (numero de vértices) y con #E (numero de aristas), entonces:

 

#V - #E + #R = 2

 

Teoremas

 

Si un grafo es plano conexo con #V > 2, entonces #E <= 3#V - 6.

Si en un grafo plano conexo con #V > 2, no existe ningún subgrafo isomorfo k3-regular, entonces #E <= 2#V - 4.

Dos regiones son adyacentes si los caminos que las bordean tienen alguna arista en común.

Una coloración es una aplicación de tal manera que dos vértices contiguos no puedan tener el mismo color.

Todo grafo plano admite una coloración con cuatro colores.

Un grafo es bipartito si existe una coloración con solo dos colores, o si y solo si no tiene ciclos con longitud impar.