ARBOLES, PROPIEDADES, SISTEMAS

ARBOLES

ÁRBOLES

Grafo conexo que no contiene ningún ciclo, existiendo siempre entre dos vértices una cadena. Igualmente se denomina así a un procedimiento frecuentemente utilizado para tratar problemas de enumeración y probabilidad.

*Elementos de un árbol

-Raíz: vértice del que salen uno o más arcos pero no entran.

-Brote: vértice en el que termina uno o más arcos, pero del que no sale ninguno.

-Nodo raíz: es cuando salen más arcos de los que entran.

-Nodo brote: es cuando entran más arcos de los que salen.

-Nodo eslabón: nodo del que salen y entran igual cantidad de arcos.

-Nodo eslabón simple: es el que entra en un arco y sale en otro.

Ejemplo:

¿Cuáles de los grafos de la figura 6.2  son árboles?

PROPIEDADES DE LOS ÁRBOLES

A) el grafo es conexo.

B) el grafo no tiene ciclos.

C) si v es el número de vértices; v-1 será el número de aristas.

D) si se agrega una arista entre dos vértices no adyacentes se forma un ciclo.

E) si suprimimos una arista cualquiera, el grafo deja de ser conexo.

F) para cada par de vértices hay una sola cadena que los conecte.

El cumplimiento de dos cualesquiera de estas propiedades define a un árbol.

SISTEMAS OPERATIVOS DE COMPUTADORA

Los sitemas operativos de las computadoras modernas organizan las carpetas y los archivos usando una estrictira de árbol. Una carpeta contiene otras carpetas y archivos. La figura muestra el explorador de Windows con él despliegue de carpeta a la izquierda y los archivos a la derecha en una computadora en particular. La figura ilustra la misma estructura como un árbol con raíz. La raíz se llama Desktop (escritorio). Abajo de Desktop están My Computer, Internet Explorer, y otros (My computer es lo único desplegado en la figura 9.1.7). Abajo de My Computer están 3 un medio Floppy (A:), Micron (C:) y otros que no se muestran. Abajo de plug-ins, que están resaltados están los archivos Afill32.api, aform.js y otros, que aparecen a la derecha de la figura 9.1.7.

GRÁFICAS PLANAS

GRÁFICAS PLANAS

Una gráfica es plana si se puede dibujar en el plano sin que sus aristas se crucen.

Al diseñar circuitos impresos es deseable tener el menor número de cruces posibles; así, el diseñador de dircuitos impresos se enfrenta con el problema de gráficas planas.

Si una gráfica plana convexa se dibuja en el plano, este se divide en regiones contiguas llamadas caras. Una cara se caracteriza por el ciclo que forma su frontera. Por ejemplo; en la siguiente gráfica, la cara A tiene como límite el ciclo (cinco, dos, tres, cuatro, cinco) y el límite de la cara C es el ciclo (uno, dos, cinco, uno). La cara exterior D se considerada limitada por el ciclo (uno, dos, tres, cuatro, seis, uno). La gráfica de la figura tiene f=4 caras, e=8 aristas y v=6 vértices. Obsérvece que f,e y v satisfacen la ecuación f=e-v+2.

En 1972, Euler probó que la ecuación se cumple para cualquier gráfica conexa plana.

f=e-v+2

f=8-6+2

4=2+2

4=4

ISOMORFISMO DE GRAFOS

 ISOMORFISMO DE GRAFOS

Definición:

Dos grafos G1 y G2 son isomorfos si existe una función biyectiva f entre los vértices de G1 y G2, y una función biyectiva g entre lados de G1 y G2 tales que un lado e es incidente a v y w en G1 si solo si el lado g(e) es incidente a los vértices f (v) y f (w) en G2. Al par de funciones f y g se le denomina isomorfismo.

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

CONSTRUCCIÓN DE TABLAS

 CONSTRUCCIÓN DE TABLAS

Lógica para la solución de problemas.

En esta clase de problemas se maneja otro tipo de variables, la variable lógica, tiene dos características fundamentales.

1. Expresa una presencia o ausencia de una relación cierta entre dos variables y por tanto solo pueden tomar los valores verdadero y falso

2. La segunda, son mutuamente excluyentes, es decir, que una vez que se da una relación cierta entre los valores de dos variables, no puede ocurrir otra relación verdadera entre los valoresde ese mismo par de variables.

Esta estrategia se utiliza para resolver problemas de dos variables cualitativas sobre las cuales pueden definirse una variable lógica, con base a la verdad o falsedad de las relaciones, entre las variables cualitativas.

Establecimiento de la existencia o no de una relación entre variables.

A través de varios procesos de pensamiento se establece la relación o no entre las variables, como por ejemplo, se emplea la deducción, la inducción, la comparación, las diferencias así como la intuición o exclusión de posibilidades, se trata de lograr concientización mediante el análisis y la verbalización de los procedimientos utilizados para llevar a cabo.

 

TEOREMA DE EULER

TEOREMA DE EULER

A) si una gráfica tiene más de dos vértices de grado impar, entonces no puede tener una trayectoria de euler.

B) si una gráfica convexa tiene exactamente dos vértices de grado par, entonces tiene por lo menos una trayectoria de euler.

Cualquier circuito de euler debe iniciar en uno de los vértices de grado por si termina en el otro.

A) el grado de un vértice es el número de aristas que se encuentra en ese vértice.

B) un circuito es una trayectoria que inicia y termina en el mismo vértice.

C) una gráfica es convexa si cualquiera de sus vértices se puede unir por una trayectoria. Si una gráfica no es convexa se le denominará como disconexa, a los pedazos de una gráfica se les llamará componentes.

Postulados

CIRCUITOS DE EULER Y DE HAMILTON

CIRCUITOS DE EULER Y DE HAMILTON

CIRCUITO DE EULER

Sea G un grafo sin vértices aislados, un circuito que tiene todas las aristas de G recibe el nombre de circuito euleriano. Un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice y recorre cada arista exactamente una vez.

Teorema: Si G es un grafo, G contiene un circuito euleriano si y solo si:

-G es un conexo

-Cada vértice de G es de grado par

Entonces si G (un grafo) tiene un vértice de grado 1 no puede tener circuitos (x-x no se repite arista). Tampoco tiene grado impar porque no se puede salir y entrar en n par de veces.

*Trayectoria de Euler debe comenzar en un vértice de grado impar y terminar en otro.

Hamilton (1805-1865) inventó (y patentó) un juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro.

Un circuito hamiltoniano, o de Hamilton, es un grafo G es un camino que comienza y termina en un mismo vértice, pasando exactamente una vez por cada vértice.

CICLO DE HAMILTO

Hamilton (1805-1865) inventó (y patentó) un juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro.

Un circuito hamiltoniano, o de Hamilton, es un grafo G es un camino que comienza y termina en un mismo vértice, pasando exactamente una vez por cada vértice.

GRAFOS

GRAFOS

Es una estructura que posee elementos de una sola estructura, relacionados por vínculos de una misma base, a estos elementos les llamaremos puntos y líneas.

El diagrama representativo de un grafo es una figura constituida por puntos unidos entre sí, por segmentos o flechas. Los diagramas de flujo y los árboles son casos particulares de grafos.

Dirección: en ciertos gráficos se indica la dirección de las líneas con una flecha originándose hacia los grafos no orientados.

Los gráficos en los que las líneas no tienen dirección se denominan grafos no orientados.

Arista: línea que conecta dos puntos en un grafo no orientado.

Arco: Línea con dirección que conecta dos puntos en un grafo orientado.

                

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.
Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.
Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
Cruce: Son dos aristas que cruzan en un punto.

Vértices

Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.
Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
Vértice Aislado: Es un vértice de grado cero.

Vértice Terminal: Es un vértice de grado 1.

BINOMIO

BINOMIO

Un binomio es un polinomio que consta de dos monomios.

P(x) = 2x2 + 3x

Binomio al cuadrado
Un binomio al cuadrado es igual es igual al cuadrado del primer término más, o menos, el doble producto del primero por el segundo más el cuadrado segundo.
(a + b)2 = a2 + 2 · a · b + b2
(x + 3)2 = x 2 + 2 · x ·3 + 3 2 = x 2 + 6 x + 9
(a − b)2 = a2 − 2 · a · b + b2
(2x - 3)2 = (2x)2 + 2 · 2x · 3 + 3 2 = 4x2 + 12 x + 9

Binomio al cubo
Un binomio al cubo es igual al cubo del primero más, o menos, el triple del cuadrado del primero por el segundo más el triple del primero por el cuadrado del segundo más, o menos, el cubo del segundo.
(a + b)3 = a3 + 3 · a2 · b + 3 · a · b2 + b3
(x + 3)3 = x 3 + 3 · x2 · 3 + 3 · x· 32 + 33 =
= x 3 + 9x2 + 27x + 27
(a − b)3 = a3 − 3 · a2 · b + 3 · a · b2 − b3
(2x - 3)3 = (2x)3 - 3 · (2x)2 ·3 + 3 · 2x· 32 - 33 =
= 8x 3 - 36 x2 + 54 x - 27

Diferencia de cuadrados
Una diferencia de cuadrados es igual a una suma por diferencia.
a2 − b2 = (a + b) · (a − b)
4x2 − 25 = (2x)2 − 52 = (2x + 5) · (2x - 5)

Suma de cubos
a3 + b3 = (a + b) · (a2 − ab + b2)
8x3 + 27 = (2x + 3) (4x2 - 6x + 9)

PERMUTACIONES Y COMBINACIONES

PERMUTACIONES Y COMBINACIONES

SELECCIONES ORDENADAS Y NO ORDENADAS

Comenzaremos con un recorrido por la combinatoria elemental contando de cuantas maneras diferentes se pueden seleccionar un cierto número de elementos de un conjunto.

Para contar este número es preciso fijar los criterios que diferencian una selección de otra. Aquí tendremos en cuenta dos tipos de criterios: el orden de los elementos y el número de veces que puede aparecer cada uno.

Si distinguimos dos selecciones: cuando tienen elementos diferentes o bien, cuando los elementos aparecen en un orden diferente, hablaremos de permutaciones. En cambio, si no distinguimos dos selecciones que solo difieren en la ordenación de sus elementos, entonces hablaremos de combinaciones. Por otra parte, si cada elemento puede aparecer como mucho una vez, hablaremos de selecciones sin repetición, mientras que si no hay esta restricción hablaremos de selecciones con repetición.

Por ejemplo, en el conjunto x=

X= {1, 2, 3, 4}

Podemos formar 16 permutaciones, con repetición de dos elementos.

11 12 13 14

21 22 23 24

31 32 33 34

41 42 43 44

Pueden repetirse dos de los elementos, pero solo una vez sin importar el orden.

12 permutaciones, sin reprepetición, de dos elementos.

12 13 14

21 23 24

31 32 34

41 42 43

No pueden repetirse los elementos y no importa el orden de los elementos.

10 combinaciones con repetición de dos elementos.

11 12 13 14

22 23 24

33 34

44

Se repiten los elementos una vez, pero si importa el orden de estos.

6 combinaciones sin repetición, sin repetición de dos elementos.

12 13 14

23 24

34

No se repiten los elementos.

PROPIEDADES DE LA ADICION

PROPIEDADES DE LA ADICION

Leyes conmutativas

Las "leyes conmutativas" sólo quieren decir que puedes intercambiar los números cuando sumas.
a + b = b + a
Ejemplos:
Puedes intercambiarlos cuando sumas: 3 + 6 = 6 + 3

Leyes asociativas
Las "Leyes asociativas" quieren decir que no importa cómo agrupes los números (o sea, qué calculas primero) cuando sumas o cuando multiplicas.

(a + b) + c = a + (b + c)

Ejemplo:

Esto: (2 + 4) + 5 = 6 + 5 = 11
da el mismo resultado que esto: 2 + (4 + 5) = 2 + 9 = 11

Leyes Distributivas 

Quiere decir que la respuesta es la misma cuando: sumas varios números y el resultado lo multiplicas por algo, o haces cada multiplicación por separado y luego sumas los resultado

Ejemplo: 

Esto:(2 + 4) × 5  =  6 × 5  =  30da el mismo resultado que esto:2×5 + 4×5  =  10 + 20  =  30

RESTA DE NUMEROS BINARIOS

RESTA DE NÚMEROS BINARIOS

RESTA DE NÚMEROS BINARIOS 

La técnica de la resta en binario es, nuevamente, igual que la misma operación en el sistema decimal. Pero conviene repasar la operación de restar en decimal para comprender la operación binaria, que es más sencilla. Los términos que intervienen en la resta se llaman minuendo, sustraendo y diferencia.

-	0	1
0	0	1
1	1 + 1	0

Las restas 0 - 0, 1 - 0 y 1 - 1 son evidentes:

0 – 0 = 0

1 – 0 = 1

1 – 1 = 0

PRINCIPIOS DE CONTEO

PRINCIPIOS DE CONTEO

PROPIEDADES DE LA MULTIPLICACIÓN

*PROPIEDAD CONMUTATIVA

Cuando se multiplican dos números el producto es el mismo, sin importar el orden de las multiplicaciones.

Ejemplo: 4*2=2*4, 6*5=5*6

*PROPIEDAD ASOCIATIVA

Cuando se multiplican tres o más números, el producto es el mismo sin importar como se agrupen los factores.

Ejemplo: (2*3)*4=2*(3*4)

*PROPIEDAD DEL ELEMENTO NEUTRO

El producto de cualquier número multiplicado por 1 es el mismo número.

Ejemplo: 5*1=5

*PROPIEDAD DISTRIBUTIVA

La suma de dos números por un tercero es igual a la suma de cada sumando por el tercer número.

Ejemplo: 4*(6+3)=(4*6)+(4*3)

PROPIEDADES DE LA ADICIÓN

PROPIEDADES DE LA ADICIÓN

*CONMUTATIVA

El orden de los sumandos no altera la suma o el total, por ejemplo

:

Ejemplo: 5+4=9 ó 4+5=9

*ASOCIATIVA

La forma de agrupar más de dos sumandos no altera la suma o total.

Ejemplo: (8+7)+6=21 = 8+(7+6)=21

*ELEMENTO NEUTRO:

A cualquier número que se le adicione un cero, el resultado es el mismo.

Ejemplo: 9+0=9 = 0+9=9

COMPLEMENTO A1 Y A2

                       COMPLEMENTO A1

El compuesto de un número del complemento A1.

Ejemplo:

-210 con 5 dígitos es 11101, su opuesto es 210

1210 con 5 dígitos es 01100, su opuesto es -1210

En otras palabras el complemento A1 de un número binario se obtiene cambiando cada 0 por 1 y viceversa. Se cambia cada bit del número por su complemento.  

COMPLEMENTO A2

El complemento A2 de un número binario se obtiene tomando el complemento A1 y sumándole 1 al bit menos significativo.COMPLEMENTO A1 Y A2

SUMA DE BINARIOS

SUMA DE BINARIOS

0+0=0

0+1=1

1+0=1

1+1=0 y pasas 1

Las sumas 0 + 0, 0 + 1 y 1 + 0 son evidentes:

ejemplo:

SISTEMA HEXADECIMAL A BINARIO

SISTEMA HEXADECIMAL A BINARIO

La conversión de números hexadecimales a binarios se hace del mismo modo, reemplazando cada dígito hexadecimal por los cuatro bits equivalentes de la tabla. Para convertir a binario, por ejemplo, el número hexadecimal 1F616 hallaremos en la tabla las siguientes equivalencias:

116 = 00012

F16 = 11112

616 = 01102

y, por tanto: 1F616 = 0001111101102

Ejercicio 12:

Convierte a binario los números hexadecimales siguientes: 7A5D16, 101016, 8F8F16

SISTEMA OCTAL A DECIMAL

SISTEMA OCTAL A DECIMAL

La conversión de un número octal a decimal es igualmente sencilla, conociendo el peso de cada posición en una cifra octal. Por ejemplo, para convertir el número 2378 a decimal basta con desarrollar el valor de cada dígito:

2*82 + 3*81 + 7*80 = 128 + 24 + 7 = 15910

2378 = 15910