22
GRAFOS (por Andy, la Gurisa y el Masi)
GRAFOS(por Andy, la Gurisa yel Masi)
¿QUÉ ES UN GRAFO?
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) 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.
¿PARA QUE SE UTILIZAN?
Los grafos permiten estudiar las interrelaciones entre
unidades que interactúan unas con otras. Por ejemplo,
una red de computadoras puede representarse y
estudiarse mediante un grafo, en el cual los vértices
representan terminales y las aristas representan
conexiones (las cuales, a su vez, pueden ser cables o
conexiones inalámbricas).
Prácticamente cualquier problema puede representarse
mediante un grafo.
VEAMOS UN PAR DE EJEMPLOS:
VEAMOS UN CASO...
LOS SIETES PUENTES DE KÖNIGSBERG.SEAMOS LEONARD EULER
EEEEHAY UNA ISLA A Y UN RÍO QUE LA RODEA QUE ESTÁ DIVIDIDO EN DOS BRAZOS.
ESTOS ESTÁN CRUZADOS POR SIETE PUENTES.
EL DESAFÍO ERA EL SIGUIENTE...
¿QUIÉN PODÍA TRAZAR UN RECORRIDO TAL QUE PASARA POR CADA PUENTE UNA SOLA VEZ Y NO MÁS.
GRAFICO DEL PROBLEMA
MÉTODO DE RESOLUCIÓN
1) Designar con letras mayúsculas cada una de las porciones de tierra.
2) Designar cada puente con letras minúsculas.
El paso de una región A (salida) a otra B (llegada), a través de un puente,se denota AB.
Si se realiza un paso sucesivo de A a B y de B a D, la denotación sería: ABD (B: llegada/salida).
Primera conclusión:
Al pasar por tres regiones, se utilizan........puentes??
Y al pasar por cuatro regiones??
5,6,...,n??
Entonces??
VAMOS QUE PODEMOS!!!
n= número de puentes
n+1= número de regiones.
ENTONCES...Los puentes son siete.
Usando la fórmula anteriormente deducida, n+1= cantidad de regiones,deducimos que tendríamos que tener un recorrido de ocho letras.
Donde:La sucesión A Y B (unidas por dos puentes), aparece dos veces.
La sucesión A Y C (unidas por dos puentes), aparece dos veces.
La sucesión A Y D (unidas por un puente), aparece una vez.
La sucesión B Y D (unidas por un puente), aparece una vez.
La sucesión C Y D (unidas por un puente), aparece una vez.
BUSCAMOS UNA REGLA
Nos basamos solo en A.
Si A tiene 1 puente.........aparece 1 vez.
Si A tiene 3 puentes.......aparece 2 veces.
Si A tiene 5 puentes.......aparece 3 veces.
Conclusión:
Si el número de puentes, como en este problema, es impar,(n+1)/2 determina la cantidad de veces que aparece A.
PARA FINALIZAR:
A tiene 5 puentes aparece......
B tiene 3 puentes aparece......
C tiene 3 puentes aparece......
D tiene 3 puentes aparece......
EL PROBLEMA NO TIENE SOLUCIÓN!!!!
¿Y si Königsberg hubiera tenido un puente menos?
Probemos suprimiendo un puente cualquiera... Por
ejemplo, el d.
x
Ya no todas las porciones de tierra tienen un número impar de puentes: mientras B y D
tienen 3 puentes cada una, A tiene 4 y C tiene 2.
x
Necesitamos crear otra regla: en esta oportunidad, para conocer cuántas veces aparece A cuando el número de puentes que
conducen a ella es par.
Si A tuviera 2 puentes, aparecería 1 vez.Si A tuviera 4 puentes, aparecería 2 veces.Si A tuviera 6 puentes, aparecería 3 veces.
(Consideramos que el camino empieza en una región distinta de A)
Entonces, si el número de puentes de A es par, la letra aparece n/2 veces.
Esta situación sí puede resolverse. Antes de explicar por qué, imaginemos un posible recorrido:
D g C c A a B b A e D f B
¿Cuántos puentes tenemos? ¿Cuántas letras mayúsculas? ¿Cuántas minúsculas?
Recordemos que A tenía 4 puentes y C, 2. Por lo tanto, debían aparecer n/2 veces. ¿Cumple?
A su turno, B y D tenían 3 puentes cada uno. Y aparecen (n+1)/2 veces.
Euler generalizó esta situación, y propuso un método aplicable a cualquier grafo, sin importar la cantidad de "regiones de tierra", ni de "puentes", ni sus respectivas
posiciones.
Observemos su método:
x
II. le suma 1, y lo llama "número encabezador";
III. escribe el número de puentes que lleva a cada porción de tierra;IV. calcula la cantidad de veces que debe aparecer cada letra (impar: (n+1)/2; par: n/2);
V. efectúa la suma de estos últimos valores: el recorrido es posible si y sólo si resulta un número menor o igual que el "número encabezador".
I. anota la cantidad de puentes;
"Con este método se podrá juzgar fácilmente, por complicado que sea el caso, si se puede pasar por todos los puentes una sola vez o no. Voy a dar, sin embargo, una manera mucho más fácil de averiguarlo, la cual se deduce sin dificultad de esta última..." (Euler, 1736)
Para simplificar aún más la cuestión, Euler observó que la suma de puentes por letra es el doble de la cantidad total de puentes. ¿A qué se debe esto? ...Además, si siempre es el doble del total de puentes, este número (12, en el ejemplo) debe ser par en todos los casos.
...¿En qué casos la suma de naturales resulta par? ¿Cómo deben ser los sumandos?
...
En virtud de estas y otras consideraciones, Euler concluyó que:
"Si son más de dos las regiones a las cuales el número de puentes que conducen es impar, entonces puede afirmarse con certeza que este recorrido no se da.
"Si solamente hay dos regiones con un número impar de puentes que conducen a ellas, entonces el recorrido es posible, con tal que empiece en una de estas regiones."Si, por último, no hay ninguna región a la cual conduzca un número impar de puentes, entonces puede establecerse el recorrido deseado, con su inicio en cualquiera de las regiones".
