Inicio | Registro | Ayuda | Contacto
El portal de la educación no formal

Dibujar un grafo para resolver un problema es un reflejo muy común, que no precisa conocimientos matemáticos. Un grafo se parece a la figura siguiente, y consta de vértices y de aristas que únen algunos de ellos.
En la teoría de los grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importan sus extremidades (o cabos); la posición de los vértices tampoco, y se puede variar para obtener un grafo más claro, y hasta sus nombres se pueden cambiar. Estos cambios se llaman isomorfismos de grafos. Generalmente, se considera que colocar los vertices en forma de polígono regular da grafos muy legibles.
Formalmente: 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, la arista {a,b} se denota ab.

Una red de carreteras que conectan ciudades, una red elétrica, un alcantarillado se pueden modelar con grafos.
En algunos casos es necesario imponer un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. Las aristas son entonces pares ordenados de vértices, con (a,b) ≠ (b,a), y se define así grafos orientados

En este grafo se ha autorizado una arista que tiene sus dos cabos idénticos: es un rizo (o bucle), y aparece también una arista sin flecha: significa que la arista se puede recorrer en cualquier sentido: es bidirreccional, y corresponde o dos aristas orientadas.
Aquí V = { a, b, c, d, e }, y A = { (a,c), (a,d), (a,e), (b,e), (c,a),(c,c), (d,b) }.
Del vértice d sólo salen vértices: es una fuente. Al vértice e sólo entran vértices: es un agujero, o pozo.
Un ciclo es un camino, es decir una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todas los vértices. Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).
Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano.

Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano.

Un grafo que no tiene circuito y que conecta a todos los puntos, se llama un árbol.

En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay nn-2 árboles posibles.
Los árboles son grafos que conectan vértices utilizando el menor número posible de aristas, de ahí su interés concreto.
En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado.
Formalmente, es un grafo con una función v: A → R+.
Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia entre ellas.
Y, de momento, no se conocen métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde a hasta b, sin más condición.
Otro problema famoso relativo a los grafos: ¿Cuántos colores son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacentes no puedan tener el mismo color? Se supone que los países son de un solo pedazo, y que el mundo es esférico o plano. En un mundo en forma de toro.
Teorema de los cuatro colores: Cuatro colores son siempre suficientes para colorear un mapa.(Véase también:Colorear un mapa con 4 colores)
Tres colores no bastan: 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.

La forma precisa de cada país no importa; lo único relevante es saber cual país toca cual 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 adyacientes. Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos.

Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fácil. Pero el teorema de los cuatro colores no es nada obvio. prueba de ello es que se ha tenido que emplear los ordenadores para acabar la demostración (se ha hecho un programa que permitió verificar una multitud de casos , lo que ahorró muchísimo tiempo a los matemáticos). Fue la primera vez que la comunidad matemática aceptó una demostración asistida por ordenador.
Un juego muy conocido es el siguiente: Se dibuja tres casas y tres pozos. Los vecinos de las casas tienen todos 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 ?

Cualquier disposición de las casas, los posos y los caminos implica la presencia de al menos un cruce.
Se nota Kn el grafo completo con n vértices, es decir en el cual cada par de vértices están conectadas por una arista. Kn,p es el grafo compuesto de un grupo de nvértices y otro de p, tal que cada vértice del primer grupo está conectado con cada del segundo, y no hay más aristas.
El juego anterior equivale a descubrir si el grafo K3,3 es planario (se dice también plano), es decir si se puede dibujar en un plano sin que haya cruces. Y la respuesta es no.
Establecer qué grafos son planarios no es obvio, y tiene que ver con la topología.

En un grafo, La distancia entre dos vértices es el menor número de aristas de un recorrido entre ellos. El diámetro, en una figura como en un grafo, es la mayor distancia entre dos puntos de la misma.
El diámetro de los Kn es 1, y el de los Kn,p es 2. Un diámetro infinito puede significar que el grafo tiene una infinidad de vértices o simplemente que no es conexo. También se puede considerar el diámetro promedio, como el promedio de las distancias entre dos vértices.
El mundo de Internet ha puesto de moda esa idea del diámetro: Si descartamos los sitios que no tienen enlaces, y escogemos dos paginas web al azar: ¿ En cuántos clics se puede pasar de la primera a la segunda? El resultado es el diámetro de la Red, vista como un grafo cuyos vértices son los sitios, y cuyas aristas son lógicamente los enlaces.
En el mundo real hay una analogía: tomando al azar dos seres humanos del mundo, ¿En cuántos saltos se puede pasar de uno a otro, con la condición de sólo saltar de una persona a otra cuando ellas se conocen personalmente? Con esta definición, se estima que el diámetro de la humanidad es de ... ¡ocho solamente!
Este concepto refleja mejor la complejidad de una red que el número de sus elementos.

De Wikipedia, la enciclopedia libre.