Date post: | 05-Apr-2018 |
Category: |
Documents |
Upload: | andres-molina |
View: | 252 times |
Download: | 0 times |
of 106
7/31/2019 proyecto matematicas discretas
1/106
7/31/2019 proyecto matematicas discretas
2/106
Lo mas valioso no es lo que tienen en susvidas, si no a quin tienen en sus vidas
annimo
7/31/2019 proyecto matematicas discretas
3/106
GRUPO 2
Integrantes:Santiago PearretaDiego Celi
Roberto ParedesOscar Muoz
Anderson JimnezMariuxi Granda
Jorge UlloaJorge Medina
Amparo Collaguazo
7/31/2019 proyecto matematicas discretas
4/106
PROYECTOMATEMTICAS
DISCRETAS
7/31/2019 proyecto matematicas discretas
5/106
TEMASCAPITULO 1.- LOGICA PROPOSICIONAL
EJERCICIOSCAPITULO 2.- LOGICA DE PREDICADOS
APLICACIONESCAPITULO 3.- ALGEBRA BOOLEANA
TEORIACAPITULO 4.- SISTEMAS NUMERICOS
EJERCICIOSCAPITULO 5.- TEORIA DE GRAFOS
APLICACIONESCAPITULO 6.- ARBOLES
TEORIACAPITULO 7.- MODELOS DE REDES
EJERCICIOS
7/31/2019 proyecto matematicas discretas
6/106
Siempre habr alguien mejor o peor
que t NO RENIEGES DE TU VIDA Annimo
7/31/2019 proyecto matematicas discretas
7/106
7/31/2019 proyecto matematicas discretas
8/106
7/31/2019 proyecto matematicas discretas
9/106
7/31/2019 proyecto matematicas discretas
10/106
7/31/2019 proyecto matematicas discretas
11/106
7/31/2019 proyecto matematicas discretas
12/106
()
7/31/2019 proyecto matematicas discretas
13/106
1. x = 4 y 6 < z
2. Franco lee pero Juan escribe
3. 4 < 7 no obstante 9>4
4. Hace frio sin embargo Jackeline estudia
5. El fuego calienta e ilumina
7/31/2019 proyecto matematicas discretas
14/106
DISYUNCIN(o", "al menos ,como mnimo, u, o bien)
1. Estudias o pierdes el ao
2. Miguel lee, al menos escribe
3. hace sol, como mnimo hace frio
4. Marcos tiene una empresa u organizacin
5. A es una vocal o bien es una letra mayscula
7/31/2019 proyecto matematicas discretas
15/106
Si hace frio entonces llueve
Hace frio solo si llueve
Hace frio si llueve
Hace frio si es necesario para que llueva
Hace frio implica que llueve
Cada vez que hace frio llueve
Llueve siempre que hace frio
Hace frio cuando llueve
CONDICIONAL(Sientonces, .solo si.,.si.,
es necesario para que,.implica.,cada vez que, siempre
que,.cuando.)
7/31/2019 proyecto matematicas discretas
16/106
Marcos trabaja si y solo si Juan estudia
Marcos trabaja solo y cuando Juan estudia
Marcos trabaja cuando y solo cuando Juan estudia
BICONDICIONAL(si y solo si, solo y cuando,cuando y solo cuando)
7/31/2019 proyecto matematicas discretas
17/106
SIMBOLIZACINY
TABLAS DE VERDAD
7/31/2019 proyecto matematicas discretas
18/106
NEGACIN()
1. Laura no estudia (p)2. 5 no es un numero par (q)
3. No es cierto que 4 > 1(r)
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Negacion1.jpg7/31/2019 proyecto matematicas discretas
19/106
CONJUNCIN ( ^ ) 1.Juan canta y estudia (p ^ q)2.Carlos y Kevin son hermanos (q ^ r)3.Lorena sonre y x + 2 = 7 (r ^ s )
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Conjuncion1.jpg7/31/2019 proyecto matematicas discretas
20/106
DISYUNCIN (V)
1.Maana llueve o hace sol (p v q)2.Maria sonre o bien Luis es amigo de Rosa (q V r)
3.Marcos canta o Pedro trabaja (r V s)
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Disyuncion1.jpg7/31/2019 proyecto matematicas discretas
21/106
CONDICIONAL( ) 1. Si x + 2 = 7, entonces z > 9 (p r)2. Si llueve entonces es una ciudad (s t)3. 6 es numero para, entonces 6 < 9 cuando 9 es un nmero
impar ( p q) r
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:C.jpg7/31/2019 proyecto matematicas discretas
22/106
BICONDICIONAL()
1. Z > 9 si y solo si Z > 9 (p q)2. si nieva cuando y solo cuando llueve (s t)
3. 2 + 3 = 5 si y solo si 2 < 10 (p q)
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Bicondicional01.jpg7/31/2019 proyecto matematicas discretas
23/106
TAUTOLOGIA
[(P V q ) ^ ( q V p)] p
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Contingencia2.jpg7/31/2019 proyecto matematicas discretas
24/106
CONTINGENCIA
(P V P) ^ (q V p)
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Contingencia2.jpg7/31/2019 proyecto matematicas discretas
25/106
CONTRADICCIN
q ^ q
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Contradiccion1.jpg7/31/2019 proyecto matematicas discretas
26/106
EQUIVALENCIA
(pVq)pq Si se escriben las tablas de verdad para P=(pVq) y Q=, se puedeverificar que ; a partir de cualesquiera valores de verdad para p yq, P y Q son ambas verdaderas o P y Q son ambas falsas.
Entonces P y Q son equivalentes lgicos
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Equivalencia1.jpg7/31/2019 proyecto matematicas discretas
27/106
SIMPLIFICACION de PROPOSICIONES
PASO1.- Aplicamos [ Morgan] ^ [( ) ^Morgan] ^ [condicional]
PASO2.- Aplicamos conmutativa ^ [ complemento] [asociativ a]
PASO3.- Aplicamos 1 ^ [ qvr] ^ [idenpotencia v p vq]
PASO4.- Aplicamos 1 ^ [ qvr] ^ [asociativa v q]
PASO5.- Aplicamos 1 ^ [ qvr] ^ [Morgan v q ]
PASO6.- Aplicamos 1 ^ [ qvr] ^ [conmutativa]
PASO7.- Aplicamos [ asociativa] complemento
PASO8.- Aplicamos [ conmutativa ]^1
PASO9.- Aplicamos (complemento) 1
PASO10.-- Aplicamos (complemento ) y esto
es el mnimo es decir el resultado
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Simplificacion1.jpghttp://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Simplificacion1.jpg7/31/2019 proyecto matematicas discretas
28/106
Qu sentido tiene corrercuando estamos en lacarretera equivocada?
Annimo
7/31/2019 proyecto matematicas discretas
29/106
2.- LOGICA DE PREDICADOS _APLICACIONES
1.- A nivel profesional; se lo aplica en un programa llamado LISP, elcual sirve como constructor de sistemas expertos.
7/31/2019 proyecto matematicas discretas
30/106
La primera regla para poder amar es tenercario por uno mismo
Annimo
7/31/2019 proyecto matematicas discretas
31/106
2.- La lgica tambin es aplicada para ensear a programar en losdiferentes lenguajes de programacin. Por ejemplo java, c++, etc.
7/31/2019 proyecto matematicas discretas
32/106
Nunca es tarde para bien hacer; has lo queno hiciste ayer
Annimo
7/31/2019 proyecto matematicas discretas
33/106
ALGEBRA BOOLEANAS Y CIRCUITOSCOMBINATORIOS
Constituyen un rea de las matemticas que hapasado a ocupar un lugar prominente con eladvenimiento de la computadora digital.
Son usadas ampliamente en el diseo de circuitos dedistribucin y computadoras, y sus aplicaciones vanen aumento en muchas otras reas. En el nivel delgica digital de una computadora, lo quecomnmente se llama hardware, y que est formadopor los componentes electrnicos de la mquina, setrabaja con diferencias de tensin, las cualesgeneran funciones que son calculadas por loscircuitos que forman el nivel.
7/31/2019 proyecto matematicas discretas
34/106
CIRCUITOS COMBINATORIOS
En una computadora digital solo hay dos posibilidades, quese escriben como 0 y 1, para el objeto indivisible mspequeo. En ltima instancia, todos los programas y datosse pueden reducir a combinaciones de bits.
A travs de los aos se ha usado una variedad dedispositivos en las computadoras digitales para almacenarbits. Los circuitos electrnicos permiten que estosdispositivos de almacenamientos se comuniquen entre si.Un bit en una parte del circuito es trasmitido a otra partedel circuito como un voltaje. Entonces se necesitan dosniveles de voltajes; por ejemplo, un voltaje alto puedecomunicar un 1 y un voltaje bajo, un 0.
7/31/2019 proyecto matematicas discretas
35/106
DEFINICIN 1:
Una compuerta AND recibe entradas X1 y X2,donde X1 y X2 son bits, y produce una salidadenotada X1 X2, donde
1 si X1= 1 y X2=1X1 X2 = 0 de otra manera
Una compuerta AND se dibuja como se indicaen la figura 1
7/31/2019 proyecto matematicas discretas
36/106
X1 X2
7/31/2019 proyecto matematicas discretas
37/106
DEFINICIN 2:
Una compuerta OR recibe entradas X1 y X2,donde X1 y X2 son bits, y produce una salidadenotada X1 X2, donde
X1 X2 = 1 si X1= 1 o X2=10 de otra manera.
Una compuerta OR se dibuja como se indicaen la figura 2.
7/31/2019 proyecto matematicas discretas
38/106
X1 X2
7/31/2019 proyecto matematicas discretas
39/106
DEFINICIN 3:
Una compuerta NOT (o inverso) recibe unaentrada X, donde X es un bits, y produce unasalida denotada por
= 1 si X = 00 si X = 1.
Una compuerta NOT se dibuja como se indicaen la figura 3
7/31/2019 proyecto matematicas discretas
40/106
7/31/2019 proyecto matematicas discretas
41/106
Tabla lgica
La tabla lgica de un circuito combinatorio lista todas lasentradas posibles junto con las salidas posibles.
ANDX1 X2 X1 X21 1 11 0 00 1 00 0 0
7/31/2019 proyecto matematicas discretas
42/106
X1 X2 X1 X2
1
1
0
0
1
0
1
0
1
1
1
0
X
1
O
0
1
OR
NOT
7/31/2019 proyecto matematicas discretas
43/106
Aprende de quienes puedanensearte
Annimo
7/31/2019 proyecto matematicas discretas
44/106
4.- SISEMAS DE NUMERACIN_
EJERCICIOS DECIMALES A BINARIOS En esta conversin se tiene un nmero enforma decimal dicho numero se lo dividirpara 2 tantas veces como sea posible y setomara como numero binario el residuo quedeje este y se lo tomara en cuenta desde
abajo hasta arriba, teniendo en cuenta que elnumero siempre se dividir para el numero 2nicamente.
7/31/2019 proyecto matematicas discretas
45/106
7/31/2019 proyecto matematicas discretas
46/106
DECIMALES A OCTALES En esta conversin se tiene un nmero enforma decimal dicho numero se lo dividirpara 8 tantas veces como sea posible y setomara como numero octal el residuo quedeje este y se lo tomara en cuenta desde
abajo hasta arriba, teniendo en cuenta que elnumero siempre se dividir para el numero 8nicamente.
7/31/2019 proyecto matematicas discretas
47/106
7/31/2019 proyecto matematicas discretas
48/106
DECIMALES A HEXAGESIMALES En esta conversin se tiene un nmero enforma decimal dicho numero se lo dividirpara 16 tantas veces como sea posible y setomara como numero hexagesimal el residuoque deje este y se lo tomara en cuenta desdeabajo hasta arriba, teniendo en cuenta que elnumero siempre se dividir para el numero 16nicamente y se remplazara los nmerosmayores a 9 con sus respectivas letras.
7/31/2019 proyecto matematicas discretas
49/106
7/31/2019 proyecto matematicas discretas
50/106
RESTA
7/31/2019 proyecto matematicas discretas
51/106
Divisin
7/31/2019 proyecto matematicas discretas
52/106
DECIMALES:0 al 9
BINARIOS:1 al 0
OCTAL:0 al 7
HEXADECIMAL:0 al 9 y del alfabeto de la A a
la F
EQUIVALENCIAS DEESTOS ENUNCIADOS
7/31/2019 proyecto matematicas discretas
53/106
Convertir binarios a decimales
Convertir decimales a binarios
Convertir decimales a octales
Convertir decimales a hexadecimales
Convertir binarios a octales
Convertir octales a binarios
Convertir binarios a hexadecimales
Convertir hexadecimales a binarios
TABLA DE NUME RACION: TABLA DE NUME RACION: TABLA DE NUME RACION:
7/31/2019 proyecto matematicas discretas
54/106
TABLA DE NUMERACIN:
7/31/2019 proyecto matematicas discretas
55/106
7/31/2019 proyecto matematicas discretas
56/106
En esta tabla yo descubr una forma de aprender masrpido los nmeros binarios la clave esta en darse cuentasimplemente en los 3 primeros nmeros que son 01 10
11 y en que la tabla los nmeros mas altos son el 100 y el1000 y el resto simplemente se le sustituye los dos ltimosnmeros por los nmeros de las tres primeras filas es decirpor ejemplo con el 100 dense cuenta que el numero que lesigue es 101 y hay ya contiene al primer numero que es 01el numero que le sigue es 110 hay ya contiene al 10 y el otroque le sigue es 111 y hay ya contiene al 11. En la del 1000 esigual hasta el 1011 despus de este numero esta 1100simplemente hacemos de cuenta como si fuera 100 y elproceso es el mismo.
7/31/2019 proyecto matematicas discretas
57/106
BINARIOS A OCTALES
7/31/2019 proyecto matematicas discretas
58/106
En esta conversin los nmeros tienen que seragrupados de 3 en 3 desde la derecha y en casode que no hubiese como agrupar al ultimogrupo de tres por circunstancia de que faltasenmeros se le debe aumentar los ceros quesean necesarios para completar la agrupacin.Luego de esto a los nmeros agrupados de tresen tres se los va sustituyendo por los nmerosque representen segn la tabla con el ejemplose entender mejor.
7/31/2019 proyecto matematicas discretas
59/106
EJERCICIOS:
7/31/2019 proyecto matematicas discretas
60/106
Como pueden darse cuenta es similar al anterior solo queahora los nmeros de azul son remplazados a ceros yunos y ese cero que esta de rojo en el segundo ejercicio lopuse de ese color para explicarles que tambin alremplazar esos nmeros pro binarios siempre tienen quequedar conformados de 3 nmeros y en caso de alpasarlo a binario solo quede de 2 nmeros tenemos queaumentar un cero para que quede conformado de tres
nmeros
7/31/2019 proyecto matematicas discretas
61/106
BINARIO A HEXADECIMA
7/31/2019 proyecto matematicas discretas
62/106
Antes de empezar tengo de decirles que este es igual debinario a octal simplemente lo nico que cambia es que
aqu se agrupa de 4 en 4
7/31/2019 proyecto matematicas discretas
63/106
EJERCICIOS:
7/31/2019 proyecto matematicas discretas
64/106
Como podemos darnos cuenta solo lo nico quecambio fue el numero de agrupacin y nada maslo ceros en rojo son los que tuve que agregar
para completar la agrupacin. Y tambin nospodemos dar cuenta que aqu esos nmerosbinarios a sido una letra es lo nico que tambincambia que aqu aparecen letras.
7/31/2019 proyecto matematicas discretas
65/106
HEXADECIMAL A BINARIO
7/31/2019 proyecto matematicas discretas
66/106
Es similar al de octal a binario lo nico quecambia es que aparecen letras y las letrastambin son sustituidas por nmeros binarios
7/31/2019 proyecto matematicas discretas
67/106
EJERCICIOS:
7/31/2019 proyecto matematicas discretas
68/106
COMVERTIR UNA BASE DE CUALQUIER TIPO A DECIMAL
7/31/2019 proyecto matematicas discretas
69/106
Ahora les explicare mejor los nmeros de colorazul son los nmeros que nos fueron dados los
verdes son las posiciones de los azules segn laenumeracin que les di empezando desde laderecha y comenzando desde cero los nmeros deamarillo son el procedimiento ya explicado hay
vemos que el tres que es el numero ya dado se lomultiplica por la base y la base es elevada segn laposicin del numero que en este caso seriaelevada a dos
7/31/2019 proyecto matematicas discretas
70/106
OPERACIONES BINARIAS
Las operaciones que veremos sern las cuatrooperaciones que son las siguientes:
7/31/2019 proyecto matematicas discretas
71/106
SUMA:
Las reglas a cumplir sern las siguientes:
7/31/2019 proyecto matematicas discretas
72/106
NOTA: (En este caso en la respuesta no secolocara el 10 en si solo se colocara el 0 y eluno se le sumara al nmero de alado pero
siguiendo las reglas solo se colocara el 10 encaso de ser ya el ltimo nmero sumado). Parasu mejor entendimiento aqu les dejo unosejercicios resueltos y explicados:
7/31/2019 proyecto matematicas discretas
73/106
EJERCICIOS:
Para las siguientes sumas de este tamao tenemos que sumar lasfilas de 2 en 2 para no confundirnos es decir la fila 1 y 2 y se saca elresultado luego la fila 3 y 4 y se saca el resultado y as sucesivamenteluego de la misma forma se suma los resultados es decir el resultado
de la fila 1 y 2 con el resultado de la fila 3 y 4 y se saca un resultado yese resultado con la fila 5 como seria en el caso del ejercicio a realizarque esta debajo
7/31/2019 proyecto matematicas discretas
74/106
MULTIPLICACION:Las reglas a cumplir sern las
7/31/2019 proyecto matematicas discretas
75/106
g psiguientes:
7/31/2019 proyecto matematicas discretas
76/106
En la multiplicacin de estas operacionesbinarias no cambien en nada su metodologacomn es decir que estas se multiplican tal ycomo si se estuviera multiplicando en unaoperacin normal pero siguiendo las reglasplanteadas. Y para multiplicar con decimales esigual simplemente se cuenta cuantos nmeroshay despus de la coma tanto de multiplicadorcomo del multiplicando y segn la cantidad dedichos nmeros en el resultado final se comienzaa contar los nmeros desde la derecha y secoloca la coma a continuacin unos ejercicios:
7/31/2019 proyecto matematicas discretas
77/106
EJERCICIOS:
NOTA: En este ejercicio voy a explicar mejor lo de los decimalescuenten cuantos nmeros hay despus de la coma del multiplicadory multiplicando smenlos, les da un total de 4 y ahora en el resultadofinal cuenten desde la derecha los nmeros que fueron encontradosdespus de la coma del multiplicando y multiplicador y coloquen lacoma tal y como esta en el ejemplo
7/31/2019 proyecto matematicas discretas
78/106
7/31/2019 proyecto matematicas discretas
79/106
LAS FORMAS COMPLEMENTARIAS Y ESIGNO
Para hacer estos ejercicios primero el numero quenos den tenemos que convertirlo a binario luegohacer que queden en 7 dgitos en caso de no ser assimplemente se le aumenta los ceros que sean
necesarios y luego de eso si dichos nmeros estn ennegativo o alguno de ellos esta dado en negativoutilizamos el complemento 1 que consiste encambiar todos los 1 por 0 y viceversa y luegoutilizamos el complemento2 el cual consiste en; al
complemento 1 sumarle 1 y despus de todo esto sisumar los binarios y en caso de no existir ningnnmero en negativo simplemente convertir a binarioy sumar
7/31/2019 proyecto matematicas discretas
80/106
EJERCICIOS:
7/31/2019 proyecto matematicas discretas
81/106
Ahora voy a explicarles para convertir esto a binariostenemos que dividir manualmente el numero dado para 2hasta ya no poder luego el residuo es lo que pasara a serlos nmeros binarios empezando desde el ultimo nmerohasta el primero para mejor entendimiento e puesto enun circulo rojo los nmeros que pasaron a ser binarios
pero los dgitos de este tienen que constar de 7 dgitosas que la regla ser igual en todas simplementeaumentar los ceros necesarios que los e colocado enrojo. Uno vez hecho esto se pasa a sumarlos como ya lese enseado.
7/31/2019 proyecto matematicas discretas
82/106
7/31/2019 proyecto matematicas discretas
83/106
En este ejercicio estamos aplicando lo que les dije si esque un nmero es negativo pero como el nmero fue el
13 y ya tenamos convertido a binario pero en positivonos ahorramos el volver a sacar el binario y solo nos tocoaplicar los complementos pero si el numero dadohubiese sido por decir el 36 pero en negativo hubiramostenido que hacer lo mismo que hicimos con el 36 positivopara encontrar el binario y luego de eso aplicar loscomplementos y luego si la operacin
7/31/2019 proyecto matematicas discretas
84/106
7/31/2019 proyecto matematicas discretas
85/106
En este ejercicio lo que hemos hecho es la respuesta finalque nos dio negativa pasarla a positivo utilizando loscomplementos estos nos sirven para pasar nmerospositivos a negativos o viceversa este ultimo ejercicio erapara demostrar esto
7/31/2019 proyecto matematicas discretas
86/106
ACEPTA LA VIDA TAL CUALES.
ALEGRATE SI RAZONALGUNA
Giroux Andr
7/31/2019 proyecto matematicas discretas
87/106
TEORIA DE GRAFOSAPLICACIONES
CABLEADO ESTRUCTURADO
7/31/2019 proyecto matematicas discretas
88/106
CABLEADO ESTRUCTURADO
GPS PARA AUTOS
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:EDIFICIO.jpg7/31/2019 proyecto matematicas discretas
89/106
GPS PARA AUTOS
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:CARRETERA.jpg7/31/2019 proyecto matematicas discretas
90/106
Antes de juzgar a alguien, respira un poco ypiensa si vale la pena
Annimo
7/31/2019 proyecto matematicas discretas
91/106
TEORIA DE ARBOLES
7/31/2019 proyecto matematicas discretas
92/106
Un rbol es un grafo simple en el cual existe un nico camino entre cada par de vrtice.
Un rbol con raz, es un rbol que tiene un vrtice particular designado como raz.Ejemplo de rbol raz:
7/31/2019 proyecto matematicas discretas
93/106
Existen cuatro tipos de rbol binario:. b l Bi i Di i
7/31/2019 proyecto matematicas discretas
94/106
rbol Binario Distinto.rbol Binario Similares.rbol Binario Equivalentes.rbol Binario Completos.A continuacin se har una breve descripcin de los diferentes tiporbol binario as como un ejemplo de cada uno de ellos.
Se dice que dos rboles binarios son distintos cuando sus estructurdiferentes.
Dos arboles binarios son similares cuando sus estructuras son idnpero la informacin que contienen sus nodos es diferente.
Son aquellos arboles que son similares y que adems los nodos conla misma informacin.
Son aquellos arboles en los que todos sus nodos excepto los del lt
nivel, tiene dos hijos; el subrbol izquierdo y el subrbol derecho.
Los rboles binarios se utilizan frecuentemente para represen
7/31/2019 proyecto matematicas discretas
95/106
Los rboles binarios se utilizan frecuentemente para represenconjuntos de datos cuyos elementos se identifican por una clanica. Si el rbol est organizado de tal manera que la clave dnodo es mayor que todas las claves su subarbol izquierdo, y mque todas las claves del subarbol derecho se dice que este rbrbol binario de bsqueda.
7/31/2019 proyecto matematicas discretas
96/106
Una tarea muy comn a realizar con un rbol es ejecutar unadeterminada operacin con cada uno de los elementos del rbEsta operacin se considera entonces como un parmetro de tarea ms general que es la visita de todos los nodos o, como denomina usualmente, del recorrido del rbol.Si se considera la tarea como un proceso secuencial, entoncenodos individuales se visitan en un orden especfico, y puedeconsiderarse como organizados segn una estructura lineal. Dhecho, se simplifica considerablemente la descripcin de mu
algoritmos si puede hablarse del proceso del siguiente elemenel rbol, segn un cierto orden subyacente.Hay dos formas bsicas de recorrer un rbol: El recorrido en
y el recorrido en
Es aquel recorrido que recorre el rbol por niveles, en el ltimo ejemplo sera:
7/31/2019 proyecto matematicas discretas
97/106
q q p , j p
Recorre el rbol por subrboles.Hay tres .Hay tres formas: en . Cada una de ellas tiene una secuenciadistinta para analizar el rbol como se puede ver a continuacin:
Recorrer el subarbol izquierdo en enorden.
Examinar la raz.Recorrer el subarbol derecho en enorden.
Examinar la raz.Recorrer el subarbol izquierdo en preorden.recorrer el subarbol derecho en preorden.
Recorrer el subarbol izquierdo en postorden.Recorrer el subarbol derecho en postorden.Examinar la raz.
A continuacin se muestra un ejemplo de los diferentes recorridos en un rbol binario
Una de las operaciones mas importantes a realizar en un rbol binario es el recorrido de los mismos, reco
7/31/2019 proyecto matematicas discretas
98/106
Una de las operaciones mas importantes a realizar en un rbol binario es el recorrido de los mismos, recosignifica visitar los nodos del rbol en forma sistemtica, de tal manera que todos los nodos del mismo svisitados una sola vez.$Existen 3 formas diferentes de efectuar el recorrido y todas ellas de naturaleza recursiva, estas son:
En el que se procesa el nodo y despus se procesan recursivamente sus hijos.Donde el nodo dado se procesa despus de haber procesado recursivamente
hijos.En este se procesa recursivamente el hijo izquierdo, luego se procesa el nodo ac
finalmente se procesa recursivamente el hijo derecho.Hay un ltimo recorrido que implementa a estos 3.
7/31/2019 proyecto matematicas discretas
99/106
RECORRIDO POR NIVELES
Concluimos implementando el recorrido porniveles. este recorrido procesa los nodoscomenzando en la raz y avanzando en formadescendente y de izquierda a derecha.
El nombre se deriva del hecho de que primerovisitamos:
los nodos del nivel 0 (la raz),despus los del nivel 1 (los hijos de la raz),los del nivel 2 (los nietos de la raz),y as sucesivamente.
Un o es un grafoG(V, E) , en el que a cada arista se le asigna un valor real no
7/31/2019 proyecto matematicas discretas
100/106
g ( , ) , q gnegativo o Sobre el conjunto de aristas se introduce una funcin peso .El de un subgrafo de un grafo ponderado es la suma de los pesos de todas sus aristas.Dado el grafo con pesos:
El peso total del grafo es
7/31/2019 proyecto matematicas discretas
101/106
RBOLES BINARIOS ISOMORFOS : Dos rboles binarios son isomorfos si tiemisma estructura, aunque el contenido de cada uno de los nodos sea diferente .
7/31/2019 proyecto matematicas discretas
102/106
El sabio no ensea con palabras si no conActos
Annimo
7/31/2019 proyecto matematicas discretas
103/106
EJERCICIOSMODELO DE REDES
Hallar los flujos faltantes y el peso de
7/31/2019 proyecto matematicas discretas
104/106
Hallar los flujos faltantes y el peso deentrada (a) y de salida(b)
Hallar los flujos faltantes y el peso de entrada(a) y de
7/31/2019 proyecto matematicas discretas
105/106
y ysalida(b)
Hallar los flujos faltantes y el peso de
7/31/2019 proyecto matematicas discretas
106/106
Hallar los flujos faltantes y el peso deentrada(a) y de salida(b)