historia grafos

8/19/2019 Historia Grafos

1/13

Algoritmos y Estructuras de Datos III

(Historia Grafos)

2do cuatrimestre 2012


2/13

GRAFOS

• Un grafo G = (V,X) es un par de conjuntos, donde V es un

conjunto de puntos o nodos y X es un subconjunto del

conjunto de pares no ordenados de elementos distintos de

V .

• Los elementos de X se llamas aristas o ejes o arcos.


3/13

Aplicacioes de gra!os

Qué es un modelo matemático?

• Problemas que pueden modelarse usando grafos.

• La noción de grafos fue planteadaindependientemente por arios cient!ficos de

diferentes disciplinas.


4/13

"istoria

"#rap$ %$eory& 1'()*1+(), -iggs,Lloyd, ilson,

/ford Uniersity Press, 1+').


5/13

Euler (#$%&)& Problema de los puentes de onigsberg.

• odelo usando grafos

'rimer teorema de teora de gra!os 3ay un circuitoque pasa por todas las "l!neas del grafo una y sólo

una e4 si y sólo si cada punto tiene un n5mero par

de "l!neas incidentes.

Euler planteó el teorema, pero sólo probó que la condición es necesaria.


6/13

• *ieer, #+$%, Laberintos.

• Vadermode, #$$#, Problema de los

caballos en un tablero de ajedre4.

• ir-ma, #+.&, circuitos en poliedros,

pionero en formular el problema de

encontrar un circuito que pase por todos losnodos de un grafo.


7/13

"amilto, #+.+ juego& dar la vuelta al mundo! sin

pasar dos veces por la misma ciudad.

• Pasar por todos los 6rtices de un dodecaedro una y sólo una

e4 y oler a la ciudad de origen.

• #enerali4ación& circuitos $amiltonianos.

• Problema del 7iajante de 8omercio

• Problema "computacionalmente no resuelto en el caso

general.


8/13

/eyes de irsc00o!! (#+1$)

• 9ntrodujo el concepto de :rboles para resoler el sistema de

ecuaciones lineales que describen el flujo de la corriente

el6ctrica en cada rama de cada circuito en una red el6ctrica.

• odeló la red compuesta de resistencias, condensadores,

inductancias, etc, con un grafo.

• ;o todas las ecuaciones son necesarias porque el sistema no esindependiente.


9/13

2ayley, #+.$& 9sómeros =u!micos.

"uántos compuestos qu#micos diferentes pueden

corresponder a una misma fórmula?

E3emplo & isómeros de 8n32n>2 ?parafinas@•


10/13

Ejemplo$ para n % & dos de los compuestos son$

-utano

9sobutano


11/13

'ro4lema de los cuatro colores se puede pintar

cualquier mapa con cuatro colores sin que dos

pa#ses que ten'an como frontera una l#nea ten'an el

mismo color?.

• /rigen ago. Primer planteo conocido&Be organ1CD2. Entecedentes de 1CA0.

• Primera "supuesta demostración, empe 1C'+

• Frror descubierto por 3eaGood, 1C+0, quedemostró el %eorema para D colores.


12/13

'ro4lema a4ierto por m5s de #66 a7os

• Eances de la teor!a de grafos alrededor de este

problema.

• Bemostración en 1+'), Eppel y 3aHen.

• Uso de la computadora en esta demostración.

• Bemostraciones posteriores.


13/13

Aplicacioes actuales

• Iedes de comunicaciones, diseJo, ruteo.

• Problemas de distribución y ruteo de e$!culos.

• Planificación de la producción.

• Iedes de tr:fico

• Bemostración de teoremas.• 8orrectitud de programas

• 7L

historia grafos

Documents