Teor A De Grafos 3

Teoría de grafos

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Este aviso fue puesto el 30 de enero de 2014.
Puedes añadirlas o avisar al autor principal del artículo en su página de discusión pegando: {{subst:Aviso referencias|Teoría de grafos}} ~~~~



Losgrafos son el objeto de estudio de esta rama de las matemáticas. Arriba el grafo pez, en medio el grafo arco y abajo el grafo dodecaedro.
La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos (también llamadas gráficas, que no se debe confundir con las gráficas que tienen unaacepción muy amplia) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no.
La teoría de grafos es una rama de la Matemática discreta y de las aplicadas, y es un tratado que usa diferentes conceptos de diversas áreas como Análisis combinatorio, Álgebra abstracta, probabilidad,geometría de polígonos, aritmética y topología.
Actualmente ha tenido mayor preponderancia en el campo de la informática, las ciencias de la computación y telecomunicaciones.
Índice
1 Historia
2 Aplicaciones
3 Tipos de grafos
4 Representación de grafos
4.1 Estructura de lista
4.2 Estructuras matriciales
5 Problemas de teoría de grafos
5.1 Ciclos y caminos hamiltonianos
5.2 Grafos planos
5.3Coloración de grafos
5.3.1 Teorema de los cuatro colores
6 Caracterización de grafos
6.1 Grafos simples
6.2 Grafos conexos
6.3 Grafos completos
6.4 Grafos bipartitos
6.5 Homeomorfismo de grafos
6.6 Árboles
6.7 Grafos ponderados o etiquetados
6.8 Diámetro
7 Algoritmos importantes
8 Investigadores relevantes en Teoría de grafos
9 Véase también
10 Referencias
11 Enlaces externos
12 Enlaces externosHistoria


Los 7 puentes del río Pregel en Königsberg.
El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, el cual consistía en encontrar un camino que recorriera los siete puentes del río Pregel (54°42′12″N 20°30′56″E) en la ciudad de Königsberg, actualmente Kaliningrado, de modo que se recorrieran todos los puentes pasando una sola vez por cadauno de ellos. El trabajo de Leonhard Euler sobre el problema titulado Solutio problematis ad geometriam situs pertinentis1 (La solución de un problema relativo a la geometría de la posición) en 1736, es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra laprofunda relación entre la teoría de grafos y la topología.
Luego, en 1847, Gustav Kirchhoff utilizó la teoría de grafos para el análisis de redes eléctricas publicando sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos, conocidas como leyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería.
En 1852 FrancisGuthrie planteó el problema de los cuatro colores el cual afirma que 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 en 1976, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar deresolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.
En 1857, Arthur Cayley estudió y resolvió el problema de enumeración de los isómeros, compuestos químicos con idéntica composición (fórmula) pero diferente estructura molecular. Para ello representó cada compuesto, en este caso hidrocarburos saturados CnH2n+2, mediante un grafo árbol donde los vértices...