Windows

TRABAJO DE TEORIA DE GRAFOS

PRESENTADO POR:

CESAR AUGUSTO LOSADA CARDONA

CORPORACION UNIVERSITARIA DEL HUILA CORHUILA

NEIVA HUILA

AÑO 2010

GRAFOS

BREVE HISTORIA:

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos engeometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.

En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos.

En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores,colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.

QUE ES UN GRAFO:

Un grafo, G,es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices.
Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar variascosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc.
La notación G = A (V, A) se utiliza comúnmente para identificar un grafo.
Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.
EJEMPLOS
G1 = (V1, A1)
V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4),(3, 4)}
G2 = (V2, A2)
V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}
G3 = (V3, A3)
V3 = {1, 2, 3} A3 = { , , }
Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:
[pic]
• Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.
Por ejemplo, el primero de los siguientesgrafos es 3-regular, el segundo es 2-regular y el tercero no es regular
• Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es
• Grafo completo: Aquel con una arista entre cada par de vértices. Ungrafo completo con n vértices se denota Kn.
A continuación pueden verse los dibujos de K3, K4, K5 y K6
• Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.
A continuación ponemos los dibujos de K1,2, K3,3, y K2,5
• Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vérticesaislados.
[pic]
• Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.
[pic]

• Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, eldodecaedro y el icosaedro.
[pic]
• Grafos eulerianos.
Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo.
Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. Como...