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.
La posición de los vértices no importa, y se
puede variar para obtener un grafo más claro.
Prácticamente cualquier red puede ser modelada
con un grafo: una red de carreteras que conecta
ciudades, una red eléctrica o un alcantarillado.
Uno de los primeros problemas que fueron modelados usando grafos
fue el que confrontó Leonard Euler (1736). En la ciudad de
Kaliningrado (antigua Königsberg) había siete puentes sobre el río
Pregel. Uno de los puentes conectaba dos islas entre sí. Una de las islas
estaba conectada a una ribera por dos puentes y otros dos puentes la
conectaban con la otra costa. La otra isla poseía un puente hacia cada
ribera. Euler se preguntó si sería posible comenzar un paseo desde
cualquier punto y atravesar cada puente una y sólo una vez, regresando
al punto departida.
Aplicando grafos se puede
encontrar una mejor manera de
regresar a nuestro punto de
partida con el menor tiempo y en
el caso de los puentes esfuerzo.
Utilizando el modelo de la
figura, donde
los vértices representan los
puntos de tierra y las aristas
representan los puentes.
Cuando un grafo o multigrafo se puede dibujar en un plano sin que
dos segmentos se corten, se dice que es plano.
Se dibujan tres casas y tres pozos. Todos los vecinos de las casas tienen el
derecho de utilizar los tres pozos. Como no se llevan bien en absoluto, no
quieren cruzarse jamás. ¿Es posible trazar los nueve caminos que juntan las tres
casas con los tres pozos sin que haya cruces?. Respuesta NO
Un grafo es plano si
se puede dibujar sin
cruces de aristas.
En 1852 Francis Guthrie planteó el problema de los 4 colores,
resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken.
El teorema de cuatro colores establece que cualquier
mapa geográfico puede ser coloreado con cuatro
colores diferentes, de forma que no queden regiones
adyacentes con el mismo color. Dos regiones se dicen
adyacentes si comparten un segmento de borde en
común, no solamente un punto.
La forma precisa de cada país no importa; lo único relevante es
saber qué país toca a qué otro. Estos datos están incluidos en el
grafo donde los vértices son los países y las aristas conectan los
que justamente son adyacentes. Entonces la cuestión equivale a
atribuir a cada vértice un color distinto del de sus vecinos.
Si se empieza por el país central a y
se esfuerza uno en utilizar el menor
número de colores, entonces en la
corona alrededor de a alternan dos
colores. Llegando al país h se tiene
que introducir un cuarto color. Lo
mismo sucede en i si se emplea el
mismo método.
Los grafos se utilizan en aplicaciones muy diversas (redes de
comunicaciones, redes de transporte, circuitos, planificación de tareas)
cada una de las cuales utiliza una noción distinta de grafo.
Los grafos de pueden clasificar atendiendo
Al número de arcos que puedan existir entre dos nodos:
 Grafos múltiples (vuelos entre aeropuertos)
 Grafos simples (líneas de ferrocarril)
A la orientación de los arcos:
 Grafos orientados (vuelos entre aeropuertos)
 Grafos no orientados (red de carreteras, líneas de teléfono)
A la existencia de funciones definidas sobre los arcos o los nodos:
 Grafos no valorados
 Grafos valorados (red de carreteras con kms, vuelos con
duración)
Al visitar una pagina web y hacer click a
un enlace, visto como un grafo los
vértices son los sitios, y cuyas aristas son
lógicamente los enlaces.
Gracias a la teoría de Grafos se pueden resolver diversos problemas como
por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de
apertura.
Los grafos se utilizan los mismos también para modelar trayectos como el
de una línea de autobús a través de las calles de una ciudad, en el que
podemos obtener caminos óptimos para el trayecto aplicando diversos
algoritmos como puede ser el algoritmo de Floyd.
Para la administración de proyectos, utilizamos técnicas como PERT en las
que se modelan los mismos utilizando grafos y optimizando los tiempos
para concretar
1) http://es.wikipedia.org/wiki/Grafos#Grafo
2) Documento PDF “cap3.pdf ”, Autor Oscar Meza
3) Documento PDF “temaVII”, Autor Juan Miguel Figueroa
Descargar

Diapositiva 1 - Pagina del servidor yaqui