Proyecto de Aula Tercera Entrega
Matemáticas Discretas
INTEGRANTES DELPROYECTO:
Ramiro Andres Restrepo Garcia
FICHA
55563
DOCENTE:
Henry Niño
Corporación unificada nacional de educación superior –CUN
Matemáticas discretas
Bogotá D.C.
Introducción
Los árboles a sub clases de grafos de uso amplio, esencialmente en computación. Los grafos se
clasifican en dos grupos; los dirigidos y no dirigidos. Los árboles forman parte de los que no son
dirigidos. Sirven para organizar y relacionar los datos en una base de datos. Ejemplo, Un árbol de
definición jerárquica se utiliza para configurar una base de datos para los registros de libros
existentes en diversas bibliotecas.
2. Desarrolle Responde las siguientes preguntas, justificando las respuestas con un ejemplo:
A. Explique cómo encuentra el algoritmo de Prim un árbol de expansión mínima.
• Se marca un vértice cualquiera. Será el vértice de partida.
• Se selecciona la arista de menor peso incidente en el vértice seleccionado
• anteriormente y se selecciona el otro vértice en el que incide dicha arista.
Repetir el paso 2 siempre que la arista elegida enlace un vértice seleccionado y otro que no lo esté.
Es decir, siempre que la arista elegida no cree ningún ciclo.
El árbol de expansión mínima será encontrado cuando hayan sido seleccionados todos los vértices
del grafo.
Ejemplo de ejecución
Grafo Descripción
Este es el grafo inicial. Los números indican el peso de las
aristas. Se elige de manera aleatoria uno de los vértices que
será el vértice de partida. En este caso se ha elegido el
vértice D.
Se selecciona la arista de menor peso de entre todos los
incidentes en el vértice D, siempre que la arista
seleccionada no cree ningún ciclo. En este caso es la arista
AD.
Ahora se selecciona la arista de menor peso de entre todos
los incidentes en los vértices D y A, siempre que la arista
seleccionada no cree ningún ciclo. En este caso es la arista
DF.
Se selecciona la arista de menor peso de entre todos los
incidentes en los vértices D, A y F, siempre que la arista
seleccionada no cree ningún ciclo. En este caso es la arista
AB. Llegado a este punto, la arista DB no podrá ser
seleccionada, ya que formaría el ciclo ABD.
Se selecciona la arista de menor peso de entre todas las
incidentes en los vértices D, A, F y B, siempre que la arista
seleccionada no cree ningún ciclo. En este caso es la arista
BE. Llegado a este punto, las aristas DE y EF no podrán ser
seleccionadas, ya que formarían los ciclos ABED y ABEFD
respectivamente.
Se selecciona la arista de menor peso de entre todas las
incidentes en los vértices D, A, F, B y E, siempre que la
arista seleccionada no cree ningún ciclo. En este caso es la
arista EC. Llegado a este punto, la arista BC no podrá ser
seleccionada, ya que formaría el ciclo BEC.
Solo que disponible el vértice G, por lo tanto, se selecciona
la arista de menor peso que incide en dicho vértice. Es la
arista EG. Como todos los vértices ya han sido
seleccionados el proceso ha terminado. Se ha obtenido el
árbol de expansión mínima con un peso de 39.
B. Muestre, cómo el algoritmo de Kruskal encuentra árboles de expansión mínima
Para generar el árbol de mínima expansión se va a partir desde el siguiente Grafo.
• Seleccionar el arco o arista de menor valor
• Seleccionar la arista con menor valor de toda la red incluyendo los nodos que la conforman
• Los dos pasos anteriores se lo debe hacer con todo el grafo y cuando se empiezan a formar
ciclos, estos se deben eliminar
• En este caso se han generado dos soluciones como se observa a
Continuación
Solución 1
• Solución 2
• Se deben sumar el valor de las aristas de las dos soluciones encontradas
Solución 1
Solución 2
En este caso se encontraron 2 soluciones óptimas del algoritmo de Kruska
• C. Qué son los Isomorfismos de árboles
Isomorfismo de árboles
Decimos que dos grafos simples son isomorfos si existe una función dentro de los
conjuntos de vértices que cumpla con que la función sea biyectiva y que las imágenes de dos
vértices adyacentes también sean adyacentes.
Es decir que si se corresponden vértice con vértice y aristas con aristas, si hacemos una
correspondencia entre los vértices de uno y los vértices de otro y las aristas de uno y las aristas
de otro tenemos que los grafos son isomorfos.
Dicho esto podemos decir que la característica más importante en los isomorfismos es la
manera en que los vértices están unidos con las aristas, a eso lo llamaríamos la
estructura de un grafo.
Ejemplo:
Sean los siguientes
grafos G1 y G2
Un isomorfismo para los grafos anteriores G1 y G2 esta definido por:
f (a) = A
f (b) = B
f (c) = C
f (d) = D
f (e) = E
y g(Xi) = Yi, i = 1, ... , 5
Los grafos G1 y G2 son isomorfos si y solo si para alguna ordenación de vértices y lados sus
matrices de incidencia son iguales. Veamos las matrices de incidencia de los grafos anteriores:
3. Resuelve los siguientes problemas
A. Dé un ejemplo de un árbol de juego completo (posiblemente hipotético) en el que un vértice terminal es 1
si el primer jugador gana y 0 si el primer jugador pierde con las siguientes propiedades: hay más ceros que
unos en los vértices terminales,
1. Árbol de juego
En este ejemplo la X representa una jugada del segundo jugador y el O una jugada del primer
jugador, en los vértices terminales, etiquetado con 1 si el primer jugador gana y 0 si el primer
jugador pierde, los vértices terminales están etiquetados con 1 si el primer jugador gana y
0 si el primer jugador pierde, hay más ceros que unos en los vértices terminales, pero el primer
jugador siempre puede ganar si sigue una estrategia óptima. Esta estrategia sería elegir siempre
el camino con el menor número de ceros, esto es, jugar siempre en el camino que lleva al vértice
con la etiqueta 1, y garantiza ganar el juego.
En el ejemplo que proporcionas, los vértices terminales son los que se encuentran al final
de cada rama del árbol. Estos son los vértices que no tienen ramas adicionales que salgan de
ellos. Los vértices terminales en el ejemplo son los que están etiquetados con 1 o 0.
Los nodos etiquetados con 1 y 0 representan los estados finales del juego, en los cuales
no hay más acciones disponibles. En el ejemplo proporcionado, los vértices etiquetados con 1
representan un estado en el cual el primer jugador gana, y los vértices etiquetados con 0
representan un estado en el cual el primer jugador pierde. Estos estados son terminales ya que no
hay más acciones disponibles en ellos, el juego ha terminado y la victoria o derrota está
determinada.
0 si el primer jugador pierde, hay más ceros que unos en los vértices terminales, pero el primer
jugador siempre puede ganar si sigue una estrategia óptima. Esta estrategia sería elegir siempre
el camino con el menor número de ceros, esto es, jugar siempre en el camino que lleva al vértice
con la etiqueta 1, y garantiza ganar el juego.
En el ejemplo que proporcionas, los vértices terminales son los que se encuentran al final
de cada rama del árbol. Estos son los vértices que no tienen ramas adicionales que salgan de
ellos. Los vértices terminales en el ejemplo son los que están etiquetados con 1 o 0.
Los nodos etiquetados con 1 y 0 representan los estados finales del juego, en los cuales
no hay más acciones disponibles. En el ejemplo proporcionado, los vértices etiquetados con 1
representan un estado en el cual el primer jugador gana, y los vértices etiquetados con 0
representan un estado en el cual el primer jugador pierde. Estos estados son terminales ya que no
hay más acciones disponibles en ellos, el juego ha terminado y la victoria o derrota está
determinada.
En este caso el juego es un poco más complejo, ya que el primer jugador tiene más
posibilidades de jugar con el símbolo O y el segundo jugador con el símbolo X. pero sigue
siendo el mismo principio, elegir el camino con mayor cantidad de unos para garantizar ganar.
B. Dibuje un árbol de juego completo para una versión de nim en la que la posición inicial consiste en una
pila de seis fichas y un turno consiste en tomar una, dos o tres. Asigne valores a todos los vértices de manera
que el árbol obtenido sea análogo al de la figura 1. Suponga que el último jugador en tomar una ficha pierde.
¿Ganará siempre el primero o el segundo jugador siguiendo una estrategia óptima? Describa una estrategia
óptima para el jugador que gana.
El primer jugador ganará siempre y cuando tenga como estrategia dejar
5 fichas, de esta manera podría quitar 1 ficha, su contrincante 2 fichas y el
primer jugador 1 ficha ganando así la partida, otra opción podría ser que de las
5 fichas el primer jugador quita 2 fichas su contrincante1 ficha y el jugador
número 1 otra ficha. De esta manera el primer jugador siempre continuara
ganando.
4. Planteé un crucigrama o sopa de letras mínimo con 20 términos sobre la Teoría de grafos
y los árboles
X R Q A R B O L E S B I N A R I O S C E G V Ñ D Z G
Y E S F D Ñ Z Q O O D B H A MI L T O N I A N O Q R
B D R T C V S Q X C X Q E R Y U O P Q C L Q T C V A
C U Q W E V O E W R E I X N V G R A F O S Y F J Q F
X N B G Z U N I S S I M P L E D F I Y H C V J A D O
Z D N X C O E P L K Z X C A Q X A L T Z A K N P W D
M A G N C G H J L Q A Z M O P E D Ñ E Q S E Q I U I
X N A K H T C A R I S T A S L D Y J O A R U A H J R
A T Q L O U R Y U O P Q A R Y U A M R U Q L U H Y I
R E S A J I Q W R T Y O T N E Q C D E P B E P G Q G
B S U P M U L T I G R A F O U Q E F M H N R H F L I
O E B I J H G S N Y P E R D Y Z N V A G G E G D K D
L C A V U H C O J V L S D O T R C D I K A S F S N O
O P R B O P Q C L Q T Ñ Y S Q N I Q W A B Ñ D Q H X
T B B N A G Y C B O P Q S C T R A U I J H G S N Y P
E N O H R L U H C O J V L S D I P Y Z X E C C M Ñ L
R M L T Q I G M C W V T W Q I L O U H C O J V L S D
M V U A B E E O I E P Z C O N J U N T O S A B P Q F
I Q I Z N F S R I J H G S N N Ñ Y Q I P P N Ñ Y I
N W P B I B Ñ T O I P E R I S O M O R F O I H B T E
A E P W W S I U H C T Q I L O U H C B T E H T X R F
L T Ñ T I C T C V S Ñ M A E WC I C L O S H A W T B
E Y J T E L K Z X C A O P Y Z X E C I Q G Z A E W
S I L S L Q A Z M O P L E S Q E R Y U O P S X Q R T
P O A S I P L A N O S L P T B M A T R I Z W C L P T
Bibliografía
Fuentes, N. A., & Andrés, A. G. (2009). Jerarquización Sectorial De La Economía
Mexicana: Un
Enfoque De Teoría De Grafos. Problemas Del Desarrollo. Revista Latinoamericana de
Economía, 40(158), 137–159.
Grafos: árbol parcial mínimo con algoritmo de PRIM. (2021).
Grafos:Árbol parcial mínimo con algoritmo de KRUSKAL. (2021).
Alejo, J. F. (2013). Algoritmo de Kruskal. Monografia, Universidad Nacional del
Altiplano .
Alonso Revenga, J. M. (2008). Flujo en Redes y Gestión de Proyectos. Teoría y Ejercicios
Resueltos.
Cantillo, S. R. (Septiembre de 2010). DESARROLLO DE APLICACIONES BASADAS
EN WSN. Obtenido de [Link]
%20DESARROLLO%20DE%20APLICACIONES%20BASADAS%20EN%[Link]
Capella Hernandez, J. V. (2010). Redes inalámbricas de sensores:una nueva arquitectura
eficiente y robusta basada en jerarquía dinámica de grupos. Valencia:
Editorial Universitat Politècnica de València. Cárdenas, J. R., Perez, F., & Barrera, E. (25
de Agosto de 2010). slideshare. Obtenido de [Link]
kruskal-y-prim
[Link]
12/[Link]
