Teoria de Grafos

Estudié Ciencias de la computación en la Facultad de Ciencias
Respondió 31 Mar. 2018
La Edad de Piedra o etapa lítica es el periodo de la prehistoria que

abarca desde que los seres humanos empezaron a
elaborar herramientas de piedra hasta el descubrimiento y uso de los
metales. (1)
La madera, los huesos y otros materiales también fueron
utilizados (cuernas, cestos, cuerdas, cuero, etc.), pero la piedra (y, en
particular, diversas rocas de rotura concoidea, como el sílex, el cuarzo, la
cuarcita, la obsidiana) fue utilizada para fabricar herramientas y armas,
de corte o percusión.
Más allá del uso de la piedra como herramientas, lo que fue muy
importante fue la decisión de unir estas piedras con palos mediante hilos.
Es así que con el ingenio del cazador recolector uniendo hilos surgen las
bases para lo que en el siglo XXI llamamos la Teoría de Grafos, cuyo
precursor fue precisamente Leonard Euler.
En 1736, época en la que vivió en Prusia, Euler resolvió el problema

conocido como el Problema de los siete puentes de Königsberg. En el pueblo
de Königsberg, en Prusia, hay una isla llamada Kneiphof, rodeada por
dos ramas del río Pregel: Hay siete puentes, a, b, c, d, e, f, y g cruzando
las dos ramas, como se muestra en la figura:
La pregunta es si una persona puede caminar de tal forma que pueda
cruzar cada uno de estos puentes una vez, pero no más que una vez.
Muchos insistían en que esto es imposible y otros tenian dudas, y nadie
era capaz de afirmar que era posible. Euler continúo en su trabajo
formulando una teoría general que resuelve el problema particular y da
origen a toda una nueva rama de las matemáticas, llamada la Teoría de
grafos.
El origen de la palabra grafo es griego y su significado etimológico es
“trazar” (del griego grafos: dibujo, imagen).
La Teoría de Grafos, una rama de la Topología, es el estudio de
estructuras matemáticas que se usan para modelar relaciones entre
objetos de una colección.
Los grafos modelan las conexiones en una red y son ampliamente

aplicables a una variedad de sistemas físicos, biológicos y de
información. Se puede utilizar grafos para modelar las neuronas en un
cerebro, los patrones de vuelo de una aerolínea y en muchas más tales
como:
 Redes de comunicaciones, diseño, ruteo.
 Problemas de distribución y ruteo de vehículos.
 Planificación de la producción.
 Redes de tráfico
 Demostración de teoremas.
 Verificación y testeo de programas
 Very Large Scale Integrated Systems VLSI
 Descifrado de Códigos
 Ingeniería de Software
 Bases de datos
 Biología Computacional
La estructura de un grafo está formada por nodos y aristas. Cada nodo
representa una entidad, y cada borde representa una conexión entre dos
nodos.
En matemáticas y ciencias de la computación, un grafo es un conjunto de
objetos llamados vértices o nodos unidos por enlaces llamados aristas o
arcos, que permiten representar relaciones binarias entre elementos de
un conjunto. Son objeto de estudio de la teoría de grafos.
Grafos en Química y Fisica

En la química cada fórmula define un compuesto a partir de los diferentes
átomos que contiene. En 1811, el químico francés Joseph Louis Gay-
Lussac (1778-1850), observó que existían sustancias distintas que
poseían la misma composición química, por lo que sus átomos tendrían
que estar enlazados de diferente manera.
En 1857, el polímata británico Arthur Cayley (1821-1895) y gran experto

en teoría de grafos (2) decidió utilizar sus conocimientos matemáticos en
el estudio de los isómeros de alcanos, de fórmula CnH2n+2. Cayley deseaba
enumerar todas las posibles configuraciones. Su manera de abordar el
problema fue la de asignar a cada alcano un árbol, es decir, un grafo, un
conjunto de vértices y aristas uniendo algunos de ellos, en el que dos
vértices están conectados por exactamente un camino de aristas. Dado
un alcano, Cayley ignoraba los átomos de hidrógeno, y construía un árbol
tomando como vértices los átomos de carbono y como aristas los
enlaces entre ellos. Su teoría dependía del número de ‘centros’ del
alcano.
Grafos en la arquitectura
El sistema de carreteras de un pueblo o ciudad se puede representar por
una red en la cual se puede aplicar el análisis usual de red de flujos y
capacidades. Sin embargo, en las fases iniciales del diseño de tales
sistemas de carreteras, es a menudo importante considerar la disposición
espacial de las carreteras y el esquema espacial que definen. (3)
Los conjuntos de posibilidades para redes de carreteras pueden ser
considerados del mismo modo que para modelos de planta, pero ahora
las aristas de los grafos planos representan carreteras. Se pueden dar
interpretaciones diferentes a las diferentes características del grafo, y las
operaciones de ornamentación pueden ser modificadas para incorporar
los detalles de las uniones de carreteras. Las disecciones rectangulares,
en particular, pueden considerarse como sistemas de carreteras
exhibidos en una cuadrícula, en la cual las carreteras definen los límites
de los bloques rectangulares. (4)

Teoria de Grafos

Cargado por

Copyright:

Formatos disponibles

Teoria de Grafos

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Teoria de Grafos

Cargado por

Copyright:

Formatos disponibles

Estudié Ciencias de la computación en la Facultad de Ciencias

Respondió 31 Mar. 2018

La Edad de Piedra o etapa lítica es el periodo de la prehistoria que

En 1736, época en la que vivió en Prusia, Euler resolvió el problema

Los grafos modelan las conexiones en una red y son ampliamente

Grafos en Química y Fisica

En 1857, el polímata británico Arthur Cayley (1821-1895) y gran experto

También podría gustarte