Teoria De Grafos


ESCUELA SUPERIOR POLITECNICA DEL LITORAL

ALGEBRA LINEAL


PROYECTO
TEORIA DE GRAFOS CADENAS Y TRAYECTORIAS


INTEGRANTES
DANIELA HIDALGO
ADEMIR ARRATA



INDICE
GRAFOS
Historia ……………………………………………………………………….
Teoria de Grafos …………………………………………………………
Definición (Grafo de manera Formal)
CARACTERIZACION DE LOS GRAFOS
Grafo simple
Grafo convexo
Grafos completos
Grafos bipartidos
CLASIFICACION DEGRAFOS
Grafo Dirigido y no dirigido ……………………………………
Orden de un Grafo
Grado de un Vértice
Teorema 1 ( Relación entre el número de aristas con el orden de los vértices del grafo)…………………………………………………………………………………………..
ETIQUETADO CONSISTENTE
Definicion
Teorema 2
Trayectoria
Teorema 3
TEOREMA 4
Representacion de los grafos ……………………………………………….
Aplicaciones…………………………………..









HISTORIA
Lossiete puentes de la isla Kueiphof
La isla Kueiphof en Koenigsberg (Pomerania) el río que la rodea se divide en dos brazos. Sobre los brazos estaban construidos siete puentes y para los habitantes era motivo de distracción descubrir un itinerario de manera que pudieran regresar al punto de partida, después de haber cruzado por los siete puentes pero pasando sólo una vez por cada uno de ellos.Leonardo Euler estudió el asunto, representó las distintas zonas A, B, C y D por medio de puntos, mientras que los puentes estaban representados por líneas que unían estos puntos. A la figura la llamó grafo, a los puntos los llamó vértices y a las líneas las denominó aristas. Estudió si una figura lineal se podía dibujar con un solo trazo, sin levantar el lápiz del papel y sin pasar dos veces por elmismo sitio.
Llegó a la siguiente conclusión:
1. Es imposible si hay más de dos vértices impares.
2. Es posible cuando:
a) Todos los vértices son pares y el punto de partida puede ser cualquiera.
b) Cuando no hay más de dos vértices impares y en este caso el comienzo del recorrido comienza en uno de ellos y termina en el otro. (Impar es un vértice si de él parten un número impar de caminos).
A laisla A llegan 5 puentes; a la B llegan 3 puentes; a la orilla C llegan 3 puentes y a la orilla D llegan 3 puentes, por tanto, según las conclusiones anteriores, el problema no tiene solución.
Ejemplos: Estos dibujos pueden hacerse de un solo trazo:






Estos no pueden hacerse en las condiciones exigidas:

Este estudio de Euler dio origen a la teoría de los grafos, que se emplean en el estudiode los circuitos eléctricos, en problemas de transporte, programación con ordenador, etc.
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 unproblema de ingeniería.
En 1852 Francis Guthrie 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 lateoría de grafos. Al tratar de resolverlo, 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, medianteun grafo árbol donde los vértices representan átomos y las aristas la existencia de enlaces químicos.
El término «grafo», proviene de la expresión H«graphic notation» usada por primera vez por Edward Frankland y posteriormente adoptada por Alexander Crum Brown en 1884, y hacía referencia a la representación gráfica de los enlaces entre los átomos de una molécula.









TEORIA DE GRAFOS
La...