Teoria De Grafos

Teoría de grafos

Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada). Típicamente, un grafo está diseñado por una serie de puntos (losvértices) conectados por líneas (las aristas).

Tabla de contenidos
• •

• • • • •

1 Historia 2 Definiciones o 2.1 Grafo o 2.2 Aristas dirigidas y no dirigidas o 2.3 Ciclos y caminos hamiltonianos o 2.4 Caracterización de Grafos 2.4.1 Grafos Simples 2.4.2 Grafos Conexos 2.4.3 Grafos Completos 2.4.4 Grafos Bipartitos o 2.5 Árboles o 2.6 Grafos ponderados o 2.7 Teorema de los cuatro colores o2.8 Coloración de Grafos o 2.9 Grafos planos o 2.10 Diámetro 3 Algoritmos importantes 4 Aplicaciones 5 Investigadores relevantes en Teoría de grafos 6 Véase también 7 Enlaces externos

[editar]

Historia
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado como uno de los primeros resultados de la teoría de grafos. También se considera uno delos primeros resultados topológicos en geometrí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, utilizandosolamente 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.[editar]

Definiciones
[editar]

Grafo
Artículo principal: Grafo

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }. Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas. Para simplificar, notaremos la arista {a, b} como ab. En teoría de grafos, sólo queda lo esencial deldibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro. Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy legibles. Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, unared eléctrica o un alcantarillado. [editar]

Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos quecontienen aristas dirigidas se denominan grafos orientados, como el siguiente: Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido). En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional,y corresponde a dos aristas orientadas. Aquí V = { a, b, c, d, e }, y A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }. Se considera la característica de "grado" (positivo o negativo) de un vértice, como la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas que tocan este...