Arboles

Grafo conexo que no contiene ningún ciclo, existiendo siempre entre dos vértices una cadena.
Igualmente se denominan así a un procedimiento frecuentemente utilizado para tratar problemas de enumeración y probabilidad.
- Elementos de un árbol
*Raíz: Vértice del que sale uno o más áreas 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 mas arcos de los que entran.
*Nodo eslabón: Nodo del que salen y entran de igual cantidad de áreas.
*Nodo eslabón simple: Es el que entra en un arco y sale en otro.

Arboles binarios.
Propiedades:
a) El grafo es conexo.
b) El grafo no tiene ciclos
c)Si V es el número de vértices; V-1 sera el número de aristas.
d) Si se agrega una arista entre 2 vértices no adyacentes se forman 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 conecta.

Con frecuencia se usa un árbol con raíz para especificar relaciones jerárquicas. Cuando se usa un árbol de esta manera, si un vértice A esta en un nivel uno menos que el nivel del vértice By A y B son adyacentes, entonces A están "justo arriba" de B y existe una relación lógica entre Ay B: A domina a B ó B es subordinado de A en alguna forma.

Isomorfismo de gráfica

Las siguientes instrucciones se da a dos personas que no pueden ver el papel de la otra: "dibuje y etiquete 5 vértices: a, b, c, d, e. conecte a-b, b-c, c-d, d-e, e-a"

Las gráficas producidas se aprecian en la sig figura de arriba. Sin duda estas figuras  definen la misma gráfica en cuanto parecen diferentes. se dice que estas gráficas son isomorfas
 Las gráficas G1 y G2 son isomorfas si existe una función f1 a 1 y sobre los vértices de G1 a los vértices de G2 y una función que 1 a1 y sobre el de los aristas de G1 a los aristas de G2 de manera que un arista  E es incidente en V y W en G1 si y solo si la arista G (E) es incidente en F(V) nombre de la isomorfosis de G1 y G2.

Al diseñar circuitos impresos es presiable tener el menor número de cruces posibles; el diseñador de circuitos impresos se enfrenta con el problema de gráficas planas. si una gráfica plana conexa se dibuja en el plano,  este se divide en regiones contiguas llamadas caras. Una cara se caracteriza por el ciclo que forma su contrario.

Vértices, grafos y aristas

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

El diagrama representativo de un grafo es una figura constituida por puntos unidos entre si, por segmentos o flechas,

Los diagramas de flujo y los arboles son cosas particulares del grafo.

Dirección: En ciertos gráficos se explica la dirección de las lineas con una flecha originalmente hacia los grafos no orientados.

Las gráficas en las que las lineas no tienen orientación se denominan graos no orientados.

Aristas: Lineas que se conectan dos puntos en un grafo no orientado

Arco: Linea con dirección que se conecta 2 puntos en un grafo orientado.

Circuitos de Guler y circuito de Hamilton

Sea G un grafo sin vértices aislados, un circuito que contiene todos los aristas de G, recibe el nombre de eiteriano.

Un circulo euleriano es una trayectoria que empieza y termina en el mismo vértice y recorre cada arista exactamente una vez.

Grado de vértice

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

b) Un circulo es una trayectoria que inicia y termina en el mismo vértice.

c) Una gráfica es conexa si cualquiera de sus vértices se puede unir con una trayectoria, si una gráfica no es conexa se le denomina como disconexa, a los pedazos de una gráfica se les llamara componentes.

Ordenadas y no ordenadas

Comenzaremos con un recorrido por la combinatoria  elemental contando de cuántas maneras diferentes se pueden seleccionar un cierto número de elementos de un conjunto, para contar este número es preciso fijar los criterios de una selección a otra. Aquí tendremos en cuenta 2 tipos de criterio: el orden de los elementos y el número de veces que puede aparecer cada uno si dividimos 2 selecciones cuando tienen elementos diferentes, hablemos de permutaciones. en cambio si no distinguimos 2 selecciones y solo difieren en la ordenación de los elementos, entonces hablamos de combinaciones. Por otra parte, si cada elemento puede aparecer como mucho 1 vez , hablemos de seleccionar sin repetición, mientras que si no hay esta restricción hablemos de selecciones sin repetición.

Podemos formar 16 permutaciones con repetición de dos elementos

Pueden repetirse 2 de los elementos que solo una vez sin importar el orden.

12 permutaciones, sin repetición de 2 elementos

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

Tabla 

.

Principios de conteo

Propiedad de la multiplicación
Propiedad conmutativa
Cuando se multiplican 2 números, el producto es el mismo sin importar el orden de los multiplicandos.

Ejemplo
 - 4*2=2*4 y 6*5=5*6

Propiedad asociativa
Cuando se multiplican 3 ó mas números, el producto es el mismo sin importar como se agrupan los factores.

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

Propiedad de elemento neutro
El producto de cualquier número multiplicando por 1 es el mismo número.

Ejemplo
 - 1*5=5 y %*1=¨5

Propiedad distributiva
La sum de 2 por un tercero es igual a la suma de casa sumando por el tercer número

Ejemplo
 - 4*(6+3)=4*9=36

Calculo de compuesto

El compuesto de un número en complemento a 1 es un complemento a 1
Ejemplo:
 - 210 con 5 dígitos es 11101, su opuesto es 210 1210 con 12 dígitos es 01100 su opuesto -1210 
El complemento A2 de un número binario se obtiene tomando el complemento A1 y sumando 1 al bit menos significativo.

Conversiones de sistemas numéricos

Sistemas Numéricos

 - Binario = 2

Los números binarios son en "base 2" en lugar de "base 10". Empiezas contando 0, después 1, ¡ya se te acabaron los dígitos! Así que vuelves al 0, pero aumentamos en 1 el número de la izquierda.

 - Octal = 8

En el sistema de numeración octal, los números se representan mediante ocho dígitos diferentes: 0, 1, 2, 3, 4, 5, 6 y 7. Cada dígito tiene, naturalmente, un valor distinto dependiendo del lu­gar que ocupen. El valor de cada una de las posiciones viene determinado por las potencias de base 8.

 - Hexadecimal = 16

Los números hexadecimales son interesantes. ¡Hay 16 dígitos diferentes! Son como los decimales hasta el 9, pero después hay letras ("A',"B","C","D","E","F") para los valores de 10 a 15.

 - Decimal = 10

Los números decimales son valores que denotan números racionales e irracionales, es decir que los números decimales son la expresión de números no enteros

Conjuntos

Un conjunto es un grupo de elementos u objetos especificados en tal forma que se puede afirmar con certeza si cualquier objeto dado pertenece o no a la agrupación. Para denotar a los conjuntos se usan letras mayúsculas. Cuando un elemento X, pertenece a A se expresa de una forma simbólica como X1 pertenece a  A X1EA. En caso de que un elemento no pertenezca a este mismo conjunto, se utiliza la anotación X1E/A.

Existen 4 formas de enunciar a los conjuntos:

* Por extensión numérica  y numeración (los elementos son encerrados entre llaves y separados por comas) por ejemplo: 1(x1, x2, x3... xn).

*Por comprensión: (los elementos se determinan a través de una condición que se establece entre las llaves. En este caso se emplea el símbolo siguiente "talque"(1)) 2{x1, x2, x3... xn} A={x|p(x)}={x1, x2, x3... xn).

*Diagrama de Been ( son regiones cerradas que sirven para visualizar el contenido de un conjunto a las relaciones entre conjunto)

*Por descripción verbal( es un enunciado que describe la característica que es común para los elementos) ejemplo: dada la descripción verbal "el conjunto de as letras vocales.

Ejemplo de los 4 conjuntos:

1) A= {a,e,i,o,u}

2) A= {x|x es una vocal}

3) 

4) "El conjunto de letras vocales"

Si cada elemento de un conjunto A es también un conjunto del conjunto B, si dice qie A es un subconjunto del B las anotaciones acb significa que A esta en incluido en B y se lee: A es un subconjunto de B o A esta contenido en B.Si no todos los elementos de un conjunto A son elementos del conjunto B, se dice que A no es un subconjunto de B, sus anotaciones Ac/B lo cual significa que A no es un subconjujnto deB

La coordinalidad de in conjunto se define como el número de elementos que posee, se denota por medio de los simbolos n ó #.

Un conjunto vacio o nulo es aquel que no posee elementos. Se denota por los simbolos 0,{}. El conjunto vacío siempre forma parte de otro, así que es un conjunto de cualquier conjunto.

Ejemplo:

 - 0={x|x son los dinosaurios que vienen la actualidad}

 - {}= {x|x son los hombres mayores a 300 }

 - 0= {x|x son números positivos menores que 0}

Conjunto universal

Es aquel que contiene a todos los elementos bajo consideración, se nota con la letra "U" y gráficamente se le representa como un triángulo.

Ejemplo:

 - U={x|x son los días  de la semana}={Lunes, Martes, Miércoles, Jueves, Viernes, Sábado, Domingo}

  -  A={x|x son los días de la semana inglesa}={Lunes, Martes, Miércoles, Jueves, Viernes}

  -  B={x|x son los días fines de semana}={Sábado y Domingo}

  -  C={x|x son los días de la semana con menos de 7 días}={Lunes, Martes, Viernes y Sábado}

Nótese: AcU, BcU, CcU.

Conjunto finito

Es aquel cuyos elementos pueden ser contados.

Ejemplo:

 - J={x|x es el número de días del mes de Noviembre}

 - K={x|x 2=y}

 - L={x|x es la cantidad de autos en el DF}

Conjuntos iguales

Se tienen exactamente los mismos elementos y se denota con el símbolo igual.

Ejemplo:

 - R= {1,2,3,4,5,6,7,}

 - S={x|x es un dígito}

Conjunto desiguales

Dos conjuntos son desiguales si por lo menos definen un elemento, es decir, si no tienen exactamente los mismos elementos y se denota con el símbolo:

 - D= {x|x2=9}

 - E= {2-2}

 - D(símbolo)E

Conjuntos equivalentes

Dos conjuntos son equivalentes y tienen la misma cantidad de elementos, es decir si poseen la misma cantidad.

 - D={x|x  son las estaciones del año}

 - E={x|x es un punto cardinal}

 - DequivalenteE

Operaciones de conjunto

La unión de los conjuntos A y B, es el conjunto de todos los elementos de A con todos los elementos de B sin repetir ninguno y se denota A unión B (AUB).

 - A={mango, ciruela, naranjo, uva, manzana, sandia}

 - B={durazno, melón, uva, naranja, sandia, platano}

 - AUB={mango, ciruela, naranja, manzana, sandia, melón, platano} 

La intersección de conjuntos Ay B es el conjunto de los elementos de A que tambien pertenecen a B y se denota "AnB={x|xEAoXEB}

Conjuntos ajenos

Dos conjuntos son ajenos cuando su intersección en el conjunto vacio, es dcir que no tienen nada en común.

 - AnE={}

 - AnE=0

Ejemplo: 

 - A={mango, ciruela, uva, naranja, manzana, sandía}

 - B{limón, fresa, mandarina, cereza}

 - AnE={}o AnB=0

Complemento

El complemento del conjunto A con respecto al conjunto universal es el conjunto de todos los elementos de U que no están en  A.

 - U={mango, kiwi. ciruela, uva, pera, naranja, cereza, manzana, sandia, durazno, limon, melón}

 - A={mango, ciruela. uva. naranja. manzana, sandía}

 - A`={kiwi, pera. cereza, durazno, limón, melón, plátano}

Este grupo se puede notar como n(A)+N(A`)=n(U)

Diferencia de conjuntos

La diferencia de los conjuntos A y B ( en ese orden ) es el conjunto de los elementos que pertenecen a A, no pertenecen a B y se denota como A-B

 - A={mango, ciruela, uva, naranja, manzana, sandía}

 - B={durazno, melón, uva, naranja, sandía, plátano}

 - A-B={mango, ciruela, manzana}

 - B-A={durazno, melón, plátano}

Inducción matemática

La inducción es un razonamiento que permite demostrar una infinidad de proposiciones a una proposición que depende de un parámetro n que forma una infinidad de valores, usualmente en el conjunto de los enteros naturales.

Ejemplo:

       n= 1

       n!>=2n-1

       1!>=2(1)-1

       1>=1

n=9,12

(n+1)!=(n+1)(n!)>=(n+1)2n-1>=2*2n-1>=2n

(9+1)!=(9+1)(9!)>=(9+1)2(9)-1>=2*2(9)-1>=2(9)

(10)!=(10)(362880)>=(10)2(9)-1>=2*2(9)-1>=2(9)

(362880)=(10)(362880)>=179>=35>=18

362880=362880>=179>=35>¨=18

Tabla de verdad

NO ( -,` etc)

Una sentencia que es modificada con el conector no es llamada negación de la sentencia original.

Y ( ^ )

La conjunción de p, q es denotada p^q la conjunción es verdadero solo si p y q son verdaderos.

O ( v )

La disyunción de p, q e denotada pvq. La disyunción es verdadera si alineas uno de sus elementos verdaderos.

Implicación ( -> )

Para dos declaraciones p->q decimos que p implica a q y se escribe p->q. La expresión p es llamad la hipótesis antecedente de la implicación de la q es llamada la conclusión o consecuencia de la implicación.

Doble implicación ( <->)

Otra declaración común en matemáticas es p si y sólo si q, o simbólicamente p<->q. Esto es llamado la equivalencia de dos proposiciones si p entonces q y si q entonces pq es una condición necesaria y suficiente para p.

Ejemplo:

Lógica

Lógica

La resolución de problemas, diseños de algoritmos y programación requieren un razonamiento lógico completo. La lógica trata los métodos y el arte del razonamiento sistemático

Lógica Proposicional

Proposiciones Simples

Una proposición es una sentencia declarativa que es verdadera o falsa pero no ambas.

Ejemplo:

- La mañana es fría

- Un girasol es amarillo

Proposiciones Compuestas

Una proposición que es indivisible se conoce como proposición primitiva las sentencias derivadas de las primitivas y de varios conectores lógicos como "No, Y, O, Si ... Entonces, Si y solo si"; se conoce como preposiciones compuestas.

Ejemplo: 

-Una gallina no es un cuatripedo

-Las hojas son rojas y azules

-El traje es negro o azul

-Si te mojas entonces te enfermas

-Un insecto vuela si y solo si tiene alas

Criterio de evaluación durante el semestre

Matemáticas Discretas

M. en C. E. Jorge Alfredo Luján Casillas

Examen 40%

Asistencia 10%

Series 15%

Tareas 10%

Participación 25%