TEMA 1: LOGICA Y DEMOSTRACIONES

A. PROPOSICIONES

Proposición: oración declarativa correcta o falsa, nunca ambas a la vez. Tienen un valor de
verdad: “Verdadero” o “Falso”. Área de la lógica que trata a las proposiciones → cálculo o lógica
proposicional.

Tabla de Verdad (TV): herramienta o representación de la relación entre valores de verdad de

proposiciones. Útil para la construcción de proposiciones desde otras más simples.

• Combinación de proposiciones.
1. Negación → ¬p
2. Conjunción ( y ) → p ∧ q
3. Disyunción ( o inclusivo ) → p ∨ q (una sea verdad)
4. O exclusivo ( ⊕ ) → no se cumple cuando ambas son verdad
5. Implicación → p → q (“Si p, q”; “si p entonces q”, “p solo si q”)
❖ Inversa: ¬ p → ¬ q
❖ Recíproca: q → p
❖ Contrarrecíproca: ¬ q → ¬ p == Implicación
6. Bicondicional/Doble implicación → p ↔ q (“ si y solo si”; “es necesario y suficiente”)

p q p∧q p∨q p⊕q p→q q→p p↔q

F F F F F V V V
F V F V V V F F
V F F V V F V F
V V V V F V V V

• Precedencia:
No, y, o , si entonces, si y solo si

El lenguaje natural es ambiguo → formalización es trasladar el lenguaje natural a proposiciones

lógicas

• Representación de la información en los ordenadores:

❖ Usan bits → 1 = V y 0 = F
❖ La información es una cadena de bits y su longitud es el número de bits.
❖ Variable booleana → variable con dos valores (V/F)
❖ ¬ , ∧, ∨ y ⊕ == NOT, AND, OR y XOR

B. EQUIVALENCIAS LÓGICAS.

• Fórmulas básicas:
❖ Tautología: siempre es verdad, no importa el valor de verdad de las proposiciones
componentes.
❖ Contradicción: siempre es falsa.
❖ Contingencia: no es ni tautología ni contradicción.
• Definiciones:
❖ Fórmulas que tienen los mismos valores de verdad en todos los casos posibles son
lógicamente equivalentes.
 • Leyes lógicas:

p∧V≡p
Leyes de identidad
p∨F≡p
p∨V≡V
Leyes de dominación
p∧F≡F
p∧p≡p
Leyes idempotentes
p∨p≡p
Ley de la doble negación ¬ (¬p) ≡ p
p∧q≡q∧p
Leyes conmutativas
p∨q≡q∨p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Leyes asociativas
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Leyes distributivas
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
¬ (p ∧ q) ≡ ¬p ∨ ¬q
Leyes de Morgan
¬ (p ∨ q) ≡ ¬p ∧ ¬q
p ∨ (p ∧ q) ≡ p
Leyes de absorción
p ∧ (p ∨ q) ≡ p
p ∨ ¬p ≡ V
Leyes de negación
p ∧ ¬p ≡ F

C. CUANTIFICADORES.
• Predicado: Para cada valor de x, P(x) se convierte en una proposición con un valor de
verdad.
• Lógica de predicados/1er Orden: Área de la Lógica que trata con Predicados y
Cuantificadores
• Cuantificación:
❖ Universal → para todo… ∀ Existencial → ∃

Si todos los elementos del dominio se pueden enumerar:

❖ ∀x P(x1 , x2, ….., xn) = P(x1 ,)∧ P( x2)∧ …,∧P( xn)

❖ ∃ x P(x1 , x2, ….., xn) = P(x1 ,) ∨ P(x2) ∨ …, ∨ P( xn)

Negación Equivalencias Verdadera Falsa

¬ ∀x P(x) ∃x¬ P(x) Hay un x para el que P(x) es falsa P(x) es verdadera para todo x

Hay un x para el que P(x) es

¬ ∃ x P(x) ∀x¬ P(x) Para cada x P(x) es falsa verdadera

• Cuantificadores con más de una variable ≡ pensar en bucles anidados = ∀x ∀y P(x, y)

D. DEMOSTRACIONES.

• Demostración → secuencia de sentencias que constituyen un argumento, que

determina que un teorema es verdadero
• Reglas de inferencia: justifican los pasos dados para dar una conclusión desde una hipótesis.

Nombre RI
p
Adición
∴p∨q

p∧q
Simplificación
∴p
p
Conjunción q
∴p∧q
p
Modus ponens p→q
∴q
¬p
Modus tollens q → ¬p
∴ ¬q
p→q
Silogismo hipotético q→r
∴p→r
p∨q
Silogismo disyuntivo ¬p
∴q
p∨q
Ley de resolución ¬p∨ r
∴q∨r

Nombre Regla de Inferencia

∀x P(x)
Particularización universal
∴ P(c)

P(c) para un c arbitrario

Generalización universal
∴ ∀x P(x)

∃x P(x)
Particularización existencial
∴ P(c) para algún elemento de c

P(c) para algún elemento de c

Generalización existencial
∴ ∃x P(x)

• Argumentos válidos.

Argumento deductivo es CORRECTO si con hipótesis verdaderas la conclusión también lo es.

 • Métodos para demostrar teoremas.

❖ Demostraciones Directas: La implicación p → q se puede demostrar viendo que si p es

verdadera entonces q lo debe ser también

❖ Demostraciones Indirectas: s La implicación p → q también se puede demostrar viendo

que su contrarrecíproca, ¬ q → ¬ p, es verdadera, ya que sabemos que son equivalentes.

❖ Demostraciones Vacuas y Triviales: Supongamos que p es falsa, entonces la implicación

p → q tiene la forma F →F o F →V y en cualquier caso es verdadera. Luego si se puede
demostrar que p es falsa, entonces se da una demostración vacua. Suelen utilizarse para
establecer casos especiales de teoremas. La demostración trivial se da cuando q es
verdadera, y se puede demostrar esto, ya que tenemos una sentencia de la forma V →V
o F →V, y eso es siempre verdadera.

❖ Demostraciones por Reducción al Absurdo: La implicación p → q también se puede

demostrar si se puede encontrar una contradicción q tal que ¬ p → q sea verdadera,
esto es ¬ p → F. Luego ¬ p tiene que ser falsa y p, será verdadera.

❖ Demostración por Casos: transformando la misma en una hipótesis como una formula
combinada de implicaciones y demostrar cada una de las implicaciones que la
componen.

❖ Demostraciones de Existencia: Afirman la existencia de “algo”; Tª del tipo ∃x P(x).

o Constructiva: Encontrar un a ∋ P(a) sea V.

o No Constructiva: No encontramos un a ∋ P(a) sea V. Se muestra que la negación
de la cuantificación existencial implica una contradicción
o Contraejemplos: Los usamos para demostrar que una sentencia ∀x P(x) es falsa.
Es un ejemplo que desmonta el que dicha sentencia es verdadera.

E. INDUCCIÓN MATEMÁTICA.

Técnica que se usa para demostrar proposiciones de la forma ∀n P(n), donde el dominio es el
conjunto de los enteros positivos.

Demostración por inducción de que P(n) es verdadera:

❖ PASO BASE: Se muestra que P(1) es verdadera

❖ PASO de INDUCCIÓN: Se muestra que P(k)→ P(k + 1) es verdadera ∀ entero positivo k

• Propiedad del Buen Orden: Todo conjunto de enteros no negativos tienen un elemento
mínimo.
TEMA 2: CONJUNTOS Y RELACIONES.

A. INTRODUCCIÓN A LA TEORÍA DE CONJUNTOS.

Conjuntos: estructura discreta fundamental sobe la que se construyen todas las demás
estudiadas.

Conjunto: colección desordenada de objetos (George Cantor, 1985)

Objetos: elementos o miembros de un conjunto. Un conjunto contiene a sus elementos.

Descripción de un conjunto:

❖ Nombre → conjunto de vocales del alfabeto

❖ Enumerando → {a, e, i, o, u}
❖ Notación por extensión: propiedad que cumplen todos los elementos del conjunto →
O = {x | x es un entero positivo menor que 100} (imposible numerar todos los elementos)

Dos conjuntos son iguales si, y solo si tienen los mismos elementos:

❖ No importa el orden.
❖ Pueden estar repetidos.

Representación gráfica: Diagramas de Venn.

❖ Conjunto Universal → rectángulo

❖ Conjuntos → círculos o formas geométricas

Conceptos y notaciones:

❖ Pertenencia → a ∈ V; b ∉ V
❖ Conjunto vacío o conjunto nulo → (∅) o { }
o No confundir el conjunto vacío con el conjunto unitario: {∅}, cuyo único
elemento es el conjunto vacío.

Subconjunto: el conjunto A se dice que es un subconjunto de B si, y solo si, todo elemento de A
lo es también de B → A ⊆ B.

❖ A ⊆ B si, y solo si, la cuantificación universal Ɐ x(x ∈

A →x ∈ B) es V
❖ Cuando A ≠ B notificación A ⊂ B y se dice que A es
un subconjunto propio de B.

Teorema: todo conjunto no vacío, tiene al menos dos subconjuntos, el conjunto vacío y el
mismo.

Cardinal de un conjunto: nº de elementos distintos = n → |S|

❖ Conjunto finito: n es un número entero positivo.

❖ Conjunto infinito: cuando no es finito.

Conjunto de las partes de un conjunto (S): conjunto de todos los subconjuntos de S → P(S). Si
un conjunto tiene n elementos, el conjunto de sus partes tiene 2𝑛 .
Colección ordenada. Los elementos no están ordenados. El orden puede ser importante:

❖ Necesidad de una estructura diferente para colecciones ordenadas → n-tuplas

❖ La n-tupla ordenada es la colección en la que 𝑎1 es su primer elemento hasta 𝑎𝑛
❖ Dos n-tuplas se dicen que son iguales si, y solo si, cada par correspondiente de sus
elementos lo son: 𝑎𝑖 = 𝑏𝑖 . (Las 2-tuplas se llaman “pares ordenados”)
o Pares ordenados iguales si: (a,b) = (c,d) → a=c y b=d
o El orden es importante en los pares ordenados: (a,b) ≠ (b,a) a no ser que b=a

Producto Cartesiano de dos conjuntos, A y B (A x B) es el conjunto de pares ordenados (a,b)

donde a ∈ A y b ∈ B.

A X B = {(a, b)| a ∈ A ∧ b ∈ B}

❖ Ej: A = {1, 2} Y B = {a, b}

A X B = {(1, a), (1, b), (2, a), (2,b)}

Relación del conjunto A en el conjunto B se obtiene del producto cartesiano de conjuntos. Es un

subconjunto R.

❖ Elementos de R → pares ordenados tal que el primer elemento pertenece a A y el

segundo a B.

Producto cartesiano de n conjuntos A1 , A2 ,…..,An denotado por A1 X A2 X…..XAn = {(a1 , a2

,…..,an) | ai ∈ Ai para i = 1, 2, … , n}

B. OPERACIONES CON CONJUNTOS.

1. Unión de conjuntos: A ∪ B = elementos de A, B o ambos.

o A ∪ B = {x| x ∈ A ∨ x ∈ B}

2. Intersección de conjuntos: A ∩ B = elementos que están en A y en B.

o A ∩ B = {x|x ∈ A ∧ x ∈ B}
o Conjuntos disjuntos → A ∩ B = ø

3. Principio de inclusión-exclusión.
o ∣AUB∣=∣A∣+ ∣B∣ - ∣A ∩ B∣

4. Diferencias de conjuntos: A – B = elementos que están en A pero no en B.

o La diferencia de A y B es el complementario de B con respecto a A (B̅ ).
o A - B= { x ∣ x ∈ A ∧ x ∉ B}

5. Conjunto complementario: Sea U el conjunto universal. El conjunto complementario de

A, A̅ , es el complementario de A con respecto a U. O sea, el complementario del conjunto
A es U - A.
o A̅ = { x | x ∉ A}
 C. IDENTIDADES DE CONJUNTOS.

A∪∅=A
Leyes de identidad
A∩U=A
A∪U=U
Leyes de dominación
A∩∅=∅
A∪A=A
Leyes idempotentes
A∩A=A
Ley de complementación (A̅̅ ) = A
A∪B=B∪A
Leyes conmutativas
A∩B=B∩A
A ∪ (B ∪ C) = (A ∪ B) ∪ C
Leyes asociativas
A ∩ (B ∩ C) = (A ∩ B) ∩ C
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Leyes distributivas
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
̅̅̅̅̅̅̅̅̅
A ∪ B = A̅ ∩ B̅
Leyes de Morgan ̅̅̅̅̅̅̅̅̅
A ∩ B = A̅ ∪ B̅
A ∪ (A ∩ B) = A
Leyes de absorción
A ∩ (A ∪ B) = A
A ∪ A̅ = U
Leyes de negación
A ∩ A̅ = ∅

Las identidades entre conjuntos se pueden demostrar, también, utilizando tablas de

pertenencia. Si un elemento pertenece a un conjunto se usa un 1. Para indicar que el elemento
no está en el conjunto, se usa un 0

Uniones e Intersecciones Generalizadas: Como la unión e intersección de conjuntos satisfacen

la ley asociativa, los conjuntos A U B U C y A ∩ B ∩ C, están correctamente definidos para los
conjuntos A, B y C.

❖ Se puede también considerar uniones e intersecciones de un número arbitrario de

conjuntos:
o La unión de una colección de conjuntos es el conjunto que contiene aquellos
elementos que son miembros de al menos, uno de los conjuntos de la colección.
o La intersección de una colección de conjuntos es el conjunto que contiene
aquellos elementos que son miembros de todos los conjuntos de la colección.

D. REPRESENTACIÓN DE CONJUNTOS EN UN ORDENADOR.

Método para almacenar elementos utilizando una ordenación arbitraria para los elementos
desordenados de U.

❖ simplifica el cálculo en operaciones entre conjuntos

❖ Sea el conjunto universal U finito (y de tamaño razonable), el número de elementos de
U no será más grande que la memoria del ordenador.
o orden arbitrario para los elementos
o subconjunto A de U mediante la cadena de bits de longitud n en la que el bit i-
ésimo es 1 si ai ; pertenece a A y 0 si no pertenece.
Representación del complementario, unión e intersección.

❖ Complementario de A: cadena de bit que representa A, cambiando los 1 a 0 y viceversa.

❖ Unión de conjuntos se obtiene haciendo la operación booleana OR entre cadenas de
bits
❖ Intersección de conjuntos equivale a una operación booleana AND entre cadenas de bits
que representan a dos conjuntos

E. FUNCIONES.

Una función ʄ de A en B es una asignación de exactamente un elemento de B a cada elemento

de A; ʄ(a) = b.

❖ Se usan para definir estructuras discretas tales como sucesiones o cadenas, etc.
❖ A es el dominio de ʄ y B el codominio. Si ʄ(a) = b, b es la imagen de a y a una preimagen
de b.
❖ El rango o imagen de ʄ es el conjunto de todas las imágenes de elementos de A.
❖ También decimos, función f de A en B, o f transforma A en B.
❖ Especificarse de distintas formas:
o Fórmula → ʄ(x) = 𝑥 2 + x + 2
o Declaración explícita → Dominio de G {Adams, Chou, Goodfriend, Rodríguez}
❖ Funciones de valores reales, = dominio, se pueden sumar y multiplicar.
o (f1 + f2 )(x) = f1 (x) + f2(x)
o (f1 f2 )(x) = f1 (x) f2(x)
❖ Se puede definir la imagen de un subconjunto de A cuando se define una ʄ de A en B.
o Sea f una función de un conjunto A en un conjunto B y sea S un subconjunto de
A. La imagen de S es el subconjunto de B formado por todas las imágenes de los
elementos de S. Denotamos por f(S) a la imagen de S, de tal forma que:
▪ ʄ (S) = { ʄ (s)| s 𝜖 S}

• Funciones inyectivas:

Una función ʄ es inyectiva si, y solo si, ʄ(x) = ʄ(y) implica que x = y para x e y del dominio de ʄ.

Una función se dice que es una inyección si es inyectiva.

❖ Inyectiva si no se repiten las imágenes → cada elemento tiene solo una imagen.
❖ Cuantificadores → ∀𝑥∀𝑦 (𝑓(𝑥) = 𝑓(𝑦) → 𝑥 = y).
❖ Tomando su contrarrecíproco, f es inyectiva ↔ f(x) ≠ f(y) entonces x ≠ y.

Inyectiva No Inyectiva
 ❖ Una función f cuyo dominio y codominio son subconjuntos del conjunto de los números
reales, se denomina:
o estrictamente creciente si 𝑓(𝑥) < 𝑓(𝑦) siempre que 𝑥 < y, estando x e y en el
dominio.
o estrictamente decreciente si 𝑓(𝑥) > 𝑓(𝑦) siempre que 𝑥 < y, estando x e y en el
dominio.

• Funciones sobreyectivas:

Una función ʄ de A a B es sobreyectiva o sobre si, y solo si Ɐ b ∈ B hay un elemento a ∈ A tal que
f(a) = b.

Una función f es una sobreyección si es sobreyectiva.

❖ Todas las imágenes tienen preimagen.

Sobreyectiva No sobreyectiva

• Función biyectiva: sobreyectiva e inyectiva a la vez.

• Función inversa:

Sea f una función biyectiva de A en B → ꓱ la función inversa de f, que es la función que asigna
un elemento de b ∈ B, el único elemento de A tal que f(a) = b.

❖ La función inversa de f se denota por 𝑓 −1

❖ 𝑓 −1 (b) = a cuando f(a) = b
❖ No biyectiva → no inversas
o Si f no es inyectiva → algún elemento b tiene dos antiimagen.
o Si f no es sobreyectiva → algún elemento b no tiene antiimagen.

• Composición de funciones:
❖ Sea g una función de A en B y f una función de B en C. Composición → (f o g) (x) = f(g(x))
❖ Condición para la existencia de la composición → la imagen de g debe estar en el
subconjunto del dominio de f
❖ No se cumple la propiedad conmutativa.
❖ (𝑓 −1 )−1= f
 • Gráfica de funciones:

Sea f una función del conjunto A al conjunto B. La gráfica de dicha función f es el conjunto de
pares ordenados {(a, b) ∣ a ∈ A y f(a) = b }

• Función parte entera:

o Función parte entera: asigna a un número real x el mayor entero que es menor
o igual que x → └ x ┘→ 0.5 = 0
o Función parte entera por exceso: asigna al número real x el menor entero que
es mayor o igual que x → ┌ x ┐→ 0.5 = 1
• Son útiles en almacenamiento y transmisión de datos.
• Propiedades:

F. RELACIONES.

• Las relaciones son una generalización de las funciones y pueden emplearse para
expresar una clase mucho más amplia de relaciones entre conjuntos.

• Una relación puede ser multívoca → un elemento de A puede estar relacionado con más
de un elemento de B.

• ꓱ las relaciones de un conjunto A en sí mismo.

• Representación:
o Enumerar sus pares ordenados
o Matrices Booleanas → Valor 1 si existe relación y
0 si no existe.
o Grafos dirigidos o dígrafos
 • Propiedades:

1. Reflexiva → ∀x ∈ A: x R x → cada elemento está relacionado consigo mismo → matriz

diagonal
2. Simétrica → ∀x,y ∈ A: x R y ↔ y R x → conmutativos → matriz simétrica → : MR =
(MR)t
3. Antisimétrica → ∀x,y ∈ A: x R y ↔ ¬ (y R x)
4. Transitiva → ∀x,y,z ∈ A: xRy ∧ yRz → x R z

Equivalente: reflexiva, transitiva y simétrica.

- Una de las RE más usadas es la “congruencia módulo m”, donde m ∈ Z+ y m > 1

o Concepto de Aritmética Modular
o Definición: a y b enteros y m entero positivo, entonces a es congruente con b
módulo m si m divide a a – b
o Notación de a congruente con b módulo m : a≡ b (mod m)
- Clases de Equivalencia. Si R es una RE en un conjunto A, el conjunto de todos los
elementos relacionados con un elemento a de A, se llama clase de equivalencia de a

• Combinación de relaciones = que en conjuntos y se hace con matrices.

• Grafos Dirigidos.

- Elementos de los conjuntos → puntos

- Relación → arista
- Propiedades:
o Reflexiva → existen bucles en todos los nodos
o Simétrica → dos aristas entre nodos
o Antisimétrica → no hay dos aristas entre nodos
o Transitiva → todos relacionados con todos
TEMA 3: COMBINATORIA Y PROBABILIDAD.

A. PRINCIPIOS BÁSICOS. MÉTODOS DE CONTEO.

Combinatoria: estudio de las posibles agrupaciones de objetos. La técnica de saber cuantos

elementos hay en un colectivo sin tener que contarlos.

• Principios básicos de la combinatoria.

- Regla del Producto (RP): se aplica cuando una tarea se compone de diferentes partes.
o Si una tarea se puede dividir en dos sub-tareas consecutivas, y hay n1 formas de
realizar la primera y n2 de realizar la segunda → formas totales = n1 * n2
o Ejemplos:
▪ Si las butacas de un auditorio se etiquetan con una letra (26
posibilidades) y un número entre el 1 y el 100, ¿cuál será el número
máximo de butacas? → 26 * 100
▪ En una sala hay 32 ordenadores. Cada ordenador tiene 28 puertos.
¿Cuántos puertos diferentes hay en la sala? → 32 * 28
▪ ¿Cuántas cadenas diferentes pueden formarse con 7 bits? → 27
▪ ¿Cuántas matrículas diferentes se pueden formar con 4 números y 3
letras? → 104 * 263
▪ ¿Cuántas funciones se pueden definir de un conjunto de m elementos
(dominio) a otro conjunto de n elementos (co-dominio/imagen)? → 𝑛𝑚

- Regla de la Suma (RS): se aplica cuando las tareas son incompatibles.

o Si una tarea se realiza de n1 formas y otra de n2 formas, siendo incompatibles
→ formas totales = n1 + n2
o Ejemplos:
▪ Supongamos que hemos de elegir un ÚNICO representante de alumnos
en la CAD del centro. El alumno debe ser elegido entre los alumnos de
tres cursos: De 2ndo curso, con 20 alumnos, de 3er curso, con 17 y 9 del
4º curso, ¿de cuántas formas se puede escoger ese representante? →
20 + 17 + 9

- Utilización simultánea de ambos:

o Ejemplos:
▪ Supongamos un autómata programable en el que los nombres de las
variables pueden incluir solo dos caracteres alfanuméricos (0-9, a-z), sin
distinción entre mayúsculas y minúsculas. Dos restricciones adicionales:
• El primer carácter debe ser una letra (26 posibilidades).
• No pueden usarse 5 posibles cadenas que corresponden con
palabras reservadas del lenguaje

¿Cuántas variables son posibles? → 26 * (26 + 10) – 5

▪ Una contraseña informática debe tener una longitud de entre 6 y 8

caracteres, cada uno de los cuales es bien un dígito (0-9) o una letra
mayúscula (26). Si una contraseña debe incluir al menos un dígito, ….
¿Cuántas contraseñas distintas son posibles?
Ptot = P6 + P7 + P8 → P6 = (10 + 26 ) ^6 – 26^6 (solo letras)
- Principio de exclusión-inclusión:
o Cuando dos tareas pueden realizarse simultáneamente no puede utilizarse la
regla de la suma, pues estaríamos contando dos veces las tareas simultáneas.
o Para evitar esto, se suman las maneras de las tareas y se restan las que se
producen simultáneamente.
o ∣AUB∣=∣A∣+ ∣B∣ - ∣A ∩ B∣

- Diagramas en Árbol:
o El diagrama se genera a partir de una raíz de la que parten ramas que
corresponden a las elecciones posibles en ese nivel.
o Los resultados posibles están representados por las hojas.
o El valor final se corresponde con los itinerarios posibles desde un nodo terminal
(hoja) del árbol hasta la raíz.

• Principio de Dirichlet o del Palomar.

o Si con k + 1 o más elementos se forman k agrupamientos, existirá un
agrupamiento que conste de dos o más elementos.
o Generalizado: si se colocan N objetos en k cajas, existe al menos una caja con
┌N/k┐ objetos → k(( N/k -1 ) + 1) = N
o El principio del palomar generalizado se puede aplicar a una rama importante
de la combinatoria, la teoría de Ramsey. En líneas generales, esta teoría trata
de la distribución de los subconjuntos de elementos de un conjunto.

B. PERMUTACIONES Y COMBINACIONES.

1. Permutaciones.
• Una permutación de un conjunto de n elementos es una ordenación concreta de todos
esos elementos.
• P(n) = n!

2. Variación de orden r.
• Una ordenación de r elementos tomados de un conjunto más amplio, de n elementos.
𝑛!
• 𝑉𝑛,𝑟 = (𝑛−𝑟)!

• Ejemplos.
o ¿Cuántas formas existen de escoger el primer, segundo y tercer clasificado de
un concurso donde participan 100 concursantes?
100!
▪ 𝑉100,3 = (100−3)!
o Supongamos que un viajante debe visitar 8 ciudades/pueblos diferentes de GC.
Debe iniciar su viaje en LPA, pero puede visitar las otras 7 en cualquier orden.
¿De cuántas formas diferentes podrá organizar su viaje? → 7!
3. Combinaciones.
• Una r-combinación de un conjunto de n elementos es una selección (no ordenada) de r
elementos de ese conjunto.
• C(n, r) = (𝑛𝑟 ) → coeficiente binomial.
• Teorema: El número de r-combinaciones de un conjunto de n-elementos, donde n es un
entero positivo y r es un entero tal que o ≤ r ≤ n :
𝑛!
▪ 𝐶𝑛,𝑟 = 𝑟!(𝑛−𝑟)!
• Sean n y r enteros no negativos tal que r ≥ n:
▪ C(n, r) = C(n, n-r)

• Ejemplos:
o ¿De cuántas formas se pueden seleccionar 5 jugadores de entre un grupo de 10
para un equipo?
10!
▪ 𝐶10,5 = 5!(10−5)!
o Treinta astronautas han sido entrenados para la primera misión a Marte.
¿Cuántas tripulaciones de 6 miembros se pueden organizar, si todos los
astronautas pueden realizar cualquier?
30!
▪ 𝐶30,6 = 6!(30−6)!
o Debemos constituir una comisión con 3 representantes del departamento de
Informática, que tiene 9 miembros, y 4 representantes del departamento de
Matemáticas, que tiene 11 miembros. ¿Cuántas comisiones diferentes pueden
seleccionarse?
9!
▪ 𝐶9,3 = 3!(9−3)!
11!
▪ 𝐶11,4 = 4!(11−4)!
▪ 𝐶9,3 ∗ 𝐶11,4

• Permutaciones con Repetición → 𝑛 𝑟

(𝑛+𝑟−1)!
• Combinaciones con Repetición → 𝐶𝑛,𝑟 = 𝑟!(𝑛−1)!

Tipo Orden Repetición Fórmula

𝑛!
Si 𝑉𝑛,𝑟 =
r-permutaciones No (𝑛 − 𝑟)!

𝑛!
r-combinaciones No No 𝐶𝑛,𝑟 =
𝑟! (𝑛 − 𝑟)!

r-permutaciones Si Sí 𝑛𝑟

(𝑛 + 𝑟 − 1)!
r-combinaciones No Sí 𝐶𝑛,𝑟 =
𝑟! (𝑛 − 1)!
• Permutaciones con objetos indistinguibles. En algunos problemas de recuento, pueden
aparecer elementos que no son distinguibles.
𝑛!
o 𝑛1!𝑛2!𝑛𝑘!

C. TEOREMA DEL BINOMIO.

• Monomio → a , 2b → elemental
• Binomio → a + b → sumas y restas
• Polinomio → a + 2b – 3ª → sumas, restas y multiplicaciones

• El teorema del binomio es una ecuación que nos dice cómo se desarrolla una expresión
de la forma (𝑎 + 𝑏)𝑛 para algún número natural n.
𝑛

(𝑎 + 𝑏) = ∑(𝑛𝑘 ) 𝑎𝑛−𝑘 𝑏𝑘
𝑛

𝑘=0

• Corolario 1: para valores de n que sean enteros no negativos.

𝑛

∑(𝑛𝑘 ) = 2𝑛
𝑘=0

• Corolario 2: Sea n un entero positivo.

𝑛

0 = ∑(𝑛𝑘 ) (−1)𝑘
𝑘=0

• Corolario 3. Sea n un entero positivo

𝑛

3 = ∑(𝑛𝑘 ) 2𝑘
𝑛

𝑘=0

• El triángulo y la Identidad de Pascal.

• Identidad de Pascal: sean n enteros +, tal que n ≥ k, entonces

(𝑛+1 𝑛 𝑛
𝑘 ) = (𝑘−1 )+ (𝑘 )

o Demostración:
▪ T = conjunto de n + 1 elementos
▪ a ϵ T, S = T - {a}
▪ Observemos que puede haber un subconjunto de k elementos en T →
(𝑛+1
𝑘 )→ puede contener a a o k elementos sin contener a a
▪ S c en (𝑛𝑘−1 ) subconjuntos de k – 1 elementos, hay los mismos
subconjuntos de T que contienen a y (𝑛𝑘 ) que no contienen a.
D. PROBABILIDAD DISCRETA.
• Introducción.
o La Tª de la probabilidad y la combinatoria tienen orígenes comunes.
o Uso inicial, s. XVII, juegos de azar (Pascal), s. XVIII-Laplace.
o Útil cálculo de complejidad algorítmica, algoritmos probabilísticos.
o Asume dado no trucado, todos igualmente probable.
o Pierre S. Laplace define la p de un evento: nº de resultados favorables / nº de
resultados posibles

• Probabilidad finita.
o La probabilidad de un suceso E, que es un subconjunto de un espacio muestral
finito S, de resultados igualmente probables es:
|𝐸|
𝑝(𝐸) =
|𝑆|

• Probabilidad de combinaciones de sucesos.

o Teorema 1: Sea E un suceso de un espacio muestral S. La probabilidad del suceso
complementario a E, E̅ , es p( E̅ ) = 1 – p(E)
o Teorema 2: Sean E1 y E2 sucesos de un espacio muestral:
P(E1 U E2)= p(E1) + p(E2) – p(E1 ∩ E2)
• Teoría de probabilidad.
o Dado S el espacio muestral de un experimento, con un número finito de posibles
resultados
o Generalización de Laplace. Se asigna una probabilidad, p(s), a cada resultado s,
verificándose dos condiciones:
▪ 0 ≤ p(s) ≤ 1
▪ ∑𝑠 ϵ S 𝑝(𝑠) = 1
o La función p, se denomina distribución de probabilidad
o Permite modelar experimentos considerando resultados igualmente probables
o no, escogiendo la p(s) adecuada
▪ Ej.
• ¿Y si la moneda estuviera trucada para obtener el doble de
caras que de cruces?
p(C)=2p(X)
p(C)+p(X)=1 → p(X)=1/3 p(C)=2/3
2p(X)+p(X)=1
o Sea S un conjunto de n elementos, la distribución uniforme asigna la
probabilidad 1/n a cada elemento de S
o Seleccionar un elemento en un espacio con distribución uniforme se denomina
selección al azar
▪ La probabilidad de un suceso E es la suma de las probabilidades de los
resultados de E → p(E) = ∑𝑠 ϵ S 𝑝(𝑠)

• Probabilidad Condicionada.
o Los teoremas 1 y 2 tienen validez para operaciones con sucesos
o Sean E y F dos sucesos tales que p(F)>0, y donde se utiliza F como el nuevo
espacio muestral, la probabilidad condicionada de E dado F se define
𝑝(𝐸 ∩ 𝐹)
𝑝(𝐸 |𝐹) =
𝑝(𝐹)

• Probabilidad Condicionada e Independencia.

o Dos sucesos son independientes si y solo si 𝑝(𝐸∩𝐹)= 𝑝(𝐸)𝑝(𝐹)

• Pruebas de Bernoulli.
o Se denomina a los experimentos con solo dos posibles resultados. Estos dos
posibles resultados suelen denominarse éxito y fracaso.
o Teorema: La probabilidad que haya k éxitos en n pruebas de Bernoulli
independientes, con éxito p y fracaso q = 1 – p, es: ( 𝑛𝑘 )𝑝𝑘 𝑞𝑛−𝑘

• Variables aleatorias.
o Una variable aleatoria es una función del espacio muestral de un experimento
en el conjunto de los números reales. Es decir, una variable aleatoria, asigna un
número real a cada posible resultado de un experimento.
o Distribución de Variable Aleatoria. La distribución de una variable aleatoria X
sobre un espacio muestral S, es el conjunto de pares (r, p(X = r)) para todo r ∈
X(S), donde p(X = r) es la probabilidad de que X tome el valor r. Generalmente,
una distribución se describe especificando p(X = r) para cada r ∈ X(S)
TEMA 4: TEORÍA DE GRAFOS.

A. DEFINICIÓN Y CONCEPTOS. CAMINOS, CICLOS Y CIRCUITOS.

• Introducción.
o Disciplina de las más importantes en matemática discreta.
o Introducidos por Euler en el S.XVIII. Resolución del problema “Los puentes de
Konigsberg”
o Aplicaciones:
▪ Ingeniería eléctrica
▪ Física y circuitos
▪ Computación, diseño y modelos
▪ Redes de ordenadores. Red telefónica
▪ Inteligencia Artificial (RNAs)
▪ Tráfico, red de transporte
▪ Redes de influencias en una organización

• Grafo simple: un grafo simple G=(V,E) es un conjunto no vacío de vértices o nodos (V),
conectados entre algunos de ellos por enlaces denominados aristas (E), que pueden ser
o no orientadas.
• Grafo trivial: grafo con 0 aristas, y 0 ó 1 vértice.
• Grafo dirigido: cuando el conjunto de enlaces, arcos, es E ⊆ V X V, entonces (V,E) es un
par ordenado y el conjunto de G = (V, E) se llama grafo dirigido o digrafo y está formado
por pares ordenados de vértices de V y arcos de E.
o Orden: total de sus vértices.
o Tamaño: total de sus arcos.
• El grafo sobre el que descansa un digrafo es su grafo subyacente.
• Aristas adyacentes: vértice común.
 • Bucle: una arista lo forma cuando está asociada a dos vértices iguales.
• Aristas/Arcos paralelos, aristas múltiples o multiaristas: cuando dos son incidentes con
los mismos vértices.
• Multigrafo: si para a,b ϵ V y a ≠ b Ǝ dos o más aristas {a, b} para un grafo o bien (a,b)
para un digrafo.
• Grafo simple: no posee aristas paralelas ni bucles.
• Grafo etiquetado: se asocia un número real o etiqueta a cada una de sus aristas o arcos
→ etiqueta = “peso” → “grafo con pesos”
• Los grafos representan un modelo de abstracción para resolver multitud de problemas.

• Camino: es una secuencia alternada de vértices vi y aristas ei de G con origen v1 y

destino vn+1 y que contienen “n” aristas.
o Se pueden repetir vértices y aristas.
o Longitud de un camino: nº total de aristas. Cuando n = 0, no existe aristas→
camino trivial
• Camino cerrado: si v1 = vn+1 y n>1, en caso contrario el camino es abierto.
• Camino simple: camino que no pasa 2 veces por la misma arista.
• Camino elemental: camino simple sin vértices repetidos (no pasa 2 veces por la misma
arista ni vértice).
• Vértice único → camino, camino simple o camino elemental.
• Ciclo: camino elemental cerrado. Al menos 3 aristas distintas.
o Longitud ≥ 3
o Todo ciclo es un circuito
o Un ciclo de longitud n en G → n-Ciclo
o Una rueda Wn se obtiene añadiéndole a un n-Ciclo un vértice adyacente a los
vértices primitivos del n-ciclo
• Cadena: camino elemental abierto.
o Cadena de longitud n en un grafo se denomina n-cadena, Pn.
• Circuito: camino simple cerrado (no arista repetida). Tiene que tener al menos 1 arista
→ 1 arista es un bucle

Aristas Vértices
Concepto Abierto Cerrado
repetidas repetidos
Camino Sí Sí Sí Sí
Camino Simple No Sí Sí Sí
Camino
No No Sí Sí
Elemental
Circuito No Sí No Sí
Cadena No No Sí No
Ciclo No No Sí No

• Grado de un vértice: número de aristas que inciden en el vértice → grad(v)

o Grado par/impar
• Grado de un grafo: suma de los grados de los vértices.
• Sea G=(V, E) un digrafo, cuyos arcos son pares ordenados de V
o Grado de entrada: nº de arcos que llegan a ese vértice
▪ Vértice fuente: grado d entrada = 0
o Grado de salida: nº de arcos que salen de ese vértice
▪ Vértice sumidero: grado de salida = 0

B. REPRESENTACIÓN MATRICIAL DE GRAFOS Y OTROS CONCEPTOS.

• La matriz de adyacencia de un grafo d en vértices es una matriz de nxn tal que aij
representa el nº de aristas entre el vértice i y j.
• Grafo no orientado → simétrica
• Grafo simple → booleana

• Teorema 1: La suma de los grados de todos los vértices de un grafo = 2*nº de aristas
o Suma de los grados siempre es PAR
• Teorema 2: sea A la matriz de adyacencia del grafo el elemento (i,j) de la matriz A^k
indica el número de caminos de longitud k que lleva del vértice i al j.
• Teorema 3: se A la matriz de adyacencia del grafo elemento (i,j) de la matriz Mk=A + A^2
+…+A^k indica el número de caminos de longitud menor o igual que k que lleva del
vértice i al j

• Matriz de Incidencia.

Sea G = (V,E) un grafo con V = {v1, v2,…,vn} como conjunto de vértices y E

= {e1, e2,…,en} como conjunto de sus lados. La matriz de incidencia de G
respecto a alas órdenes de V y E , es la matriz booleana , nxm , M = [mij],
tal que:

- 1 → si el lado ej es incidente con el vértice vi

- 0 en cualquier otro caso

C. OTROS TIPOS DE GRAFOS.

• Grafo conexo: Un grafo G es conexo si existe un camino elemental entre cualquier par
de vértices. Un digrafo es conexo si un grafo subyacente sí lo es.
• Grafo no conexo o disjunto
• Los subgrafos conexos máximos de un grafo no dirigido se llaman componentes o
componentes conexos
• El nº de sus componentes se indica por k(G)
• Grafo regular de grado k / k-regular: un grafo G o multigrafo en el que todos sus vértices
son del mismo grado k.
o Teorema: Sea G = (V, E) un grafo regular de grado k, entonces: K *|V| = 2|E|

• Grafo completo: grafo G, no digrafo y sin bucles, construidos sobre n vértices indicados
por Kn, tal que cada vértice de Kn es adyacente con los n-1 vértices restantes, está
conectado a todos los demás.
o Total de aristas → C(n, 2) = (𝑛2 )

• Grafos ciclos:

• Grafos rueda:

• Grafos cubos:
 • Grafo bipartito: G=(V,E) es aquel en el que V = V1 U V2 siendo V1 ∩ V2 = ∅ y tal que cada
lado de G es la forma {a,b}, con a pertenece a V1 y b pertenece a V2.
o Es completo si además, cada vértice de V1 está unido con cada vértice de V2. En
este caso si |V1| = m y |V2| = n, el grafo se indica por Km,n

K3,3

D. GRAFOS EULERIANOS.

Sea G = (V, E), un grafo o multigrafo sin vértices aislados.

• Camino simple de Euler o recorrido de Euler: un camino simple de G desde a hasta b que
pase por todas las aristas de G solo una vez.
• Circuito de Euler: todo circuito de dicho grafo G que pase por todas las aristas de G una
vez → grafo euleirano o recorrible
• Tienes que recorrer todo el grafo sin repetir aristas.

• Teorema de Euler: Sea G = (V,E) , un grafo o multigrafo sin vértices aislados. Entonces,
G posee un circuito de Euler si y solo sí es conexo y sus vértices son de grado par.

• Teorema: Sea G = (V, E) un grafo o multigrafo sin vértices aislados, se puede construir
un camino simple de Euler o recorrido euleriano pero no un circuito, si y solo sí G es
conexo y tiene, exactamente dos vértices con grado impar. Entonces el camino simple
de Euler puede comenzar y acabar en esos vértices. G se denomina grafo semi-
Euleriano.

• Teorema: Sea G=(V,E) un digrafo o multigrafo sin vértices aislados. Entonces, G posee
un circuito Euleriano si y solo si gra-(v) = gra+(v) ∀ 𝒗 ∈ V

• Grafo Euleriano-Construcción:
1. Tomamos un vértice cualquiera y
formamos un circuito cualquiera (entre
más grande mejor).
C1 = {E,F,D,A,B,E}
 2. Obtenemos el subgrafo H1 eliminando
las aristas de C1. Todos los vértices deberían
seguir teniendo grado par.

3. Como es conexo, alguno de los vértices

de C1 debe seguir estando en H1, por
ejemplo F. Buscamos otro circuito que
empiece y acabe en F.
C2 = {F,G,D,C,F}

4. Combinamos C1 y C2 → = {E,F,G,D,C,F,D,A,B,E}. Eliminamos aristas del circuito y vértices

de nuevo.

Proceso iterativa hasta conseguir algo como b

E. GRAFOS HAMILTONIANOS.

• Un camino Hamiltoniano es un camino que pasa por todos los vértices solo una vez.
• Un ciclo Hamiltoniano es un ciclo que pasa por todos los vértices solo una vez,
empezando y acabando en el mismo vértice.
• Un grafo Hamiltoniano es un grafo conexo que contiene un ciclo hamiltoniano

• Condiciones:
o Conexo
o No puede haber vértices de grado 1
o No pueden haber vértices de corte(aquellos que si eliminamos junto con sus
aristas convierte al grafo en no conexo)
 • Construcción de grafos Hamiltonianos
o Teorema de Dirac: Si G es un grafo simple y conexo con n vértices para n ≥ 3 tal
que todos los vértices tienen grado mayor o igual que n/2. Entonces, G es
Hamiltoniano.
▪ Es una condición suficiente, por lo que pueden existir ciclos
hamiltonianos en un grafo que no cumpla esa condición.
▪ Corolario Tª de Dirac: Sea G=(V,E) un grafo sin bucles con n ≥ 2 vértices.
Entonces G tiene un camino de Hamilton si grad(v) ≥ (n-1)2, para todo
vértice v.
o Teorema de Ore: Si G es un grafo simple y conexo con n vértices para n ≥ 3 tal
que grado(u) + grado(v) ≥ n para todos los vértices no adyacentes u y v de G.
entonces G es Hamiltoniano.
o Torema: Sea G = (V,E) un grafo simple con n≥2 vértices. Si se verifica que
grad(v)+grad(w) ≥ n-1 𝑤 ∈ 𝑉, 𝑣 ≠ 𝑤, entonces G posee un camino de Hamilton.
La existencia de posibles bucles en G no afecta al teorema.

F. CAMINOS DE LONGITUD MÍNIMA.

• Problemas relacionados con los grafos ponderados:
o Longitud de un camino en un grafo ponderado = suma de los pesos de esas
aristas
o Camino de longitud mínima
o Puede no ser único
o Circuito de longitud total mínima

• Algoritmo de Dijkstra:
o Ruta más corta entre dos vértices de un grafo ponderado.
- Algoritmo→ ejemplo

→ longitud mínima de a hasta z

1. Matriz de costes:

a b c d e z
a ∅ 2 3 ∞ ∞ ∞
b 2 ∅ ∞ 5 2 ∞
c 3 ∞ ∅ ∞ 5 ∞
d ∞ 5 ∞ ∅ 1 2
e ∞ 2 5 1 ∅ 4
z ∞ ∞ ∞ 2 4 ∅

Para construirla:

- Se ponen ∅ donde se relaciona el elemento con el mismo.

- Se pone ∞ en los vértices no adyacentes.
- Se colocan los números correspondientes a los pesos.
2. Se comienza a recorrer por los adyacentes anotando sus costes.
3. Cuando un camino sea de mayor coste se descarta
4. Se van sumando los costes.

Solución: a,b = 2 → b,c = 2 → c,d = 1 → d,z = 2 = 7

TEMA 5: ÁRBOLES.

A. INTRODUCCIÓN A LOS ÁRBOLES.

• Un árbol es un grafo conexo no dirigido y que no contiene ciclos (acíclico).
• Árbol de n vértices tiene n-1 aristas
• Teorema 1: Grafo no dirigido es árbol si, y solo si, entre cada par de vértices existe un
único camino.

• Excentricidad: la excentricidad de un vértice es la máxima distancia de ese vértice a

cualquier otro escogiendo el camino mínimo → longitud del camino simple más largo
desde ese vértice.
• Centro: vértice que tenga mínima excentricidad.
• Un árbol T = (V, E), que tiene un solo vértice y sin lados → árbol degenerado

• Se denomina árbol maximal(de expansión) , recubridor o generador del grafo conexo G

, un subgrafo maximal G que también sea árbol. Un árbol maximal de G contiene todos
los vértices de G.
• Un árbol generador se puede obtener en lugar de eliminando aristas (no el más
eficiente) sino añadiéndolas.
• Un bosque es un grafo acíclico no conexo. No obstante, cada una de sus componentes
conexas es un árbol.

B. PROPIEDADES DE LOS ÁRBOLES.

• Vértice raíz o nodo:

o Todas sus aristas están orientadas alejándose de la raíz.
o Un árbol con su raíz produce un árbol dirigido llamado árbol raíz.
o En un árbol con raíz puede omitirse el sentido de las aristas ya que sabemos que
se aleja de la raíz.
o Cada elección diferente de la raíz origina un árbol raíz distinto.

• En un árbol raíz, cada vértice v, distinto de la raíz, tiene como padre el único vértice u,
tal que hay una arista dirigida de u a v. Asimismo, v es hijo de u.
• Vértices con el mismo padre → hermanos
• Los antecesores de un vértice no raíz son todos los vértices que aparecen en el camino
desde la raíz hasta el vértice sin incluirlo a él.
• Los descendientes de un vértice son aquellos para los que v es antecesor.
• Vértices sin hijos → hojas
• Vértices con hijos → vértices internos
• La raíz es un vértice interno, si no es el único nodo del árbol. Entonces sería hoja.

• Árbol-m-ario → árbol raíz en el que todos los vértices internos tienen a lo sumo m hijos.
Si todo vértice interno tiene exactamente m hijos, entonces será un árbol-m-ario.
o M = 2, árbol bi-nario
• Árbol ordenado con raíz es en el que los hijos de cada vértice interno están ordenados
y se ordenan de izquierda a derecha
o Árbol con raíz en el hijo izquierdo = subárbol izquierdo
o Árbol con raíz en el hijo derecho = subárbol derecho
• El nivel de un vértice es la longitud del único camino desde la raíz al vértice.
• Altura es la longitud del camino más largo desde la raíz a cualquier vértice (máximo de
los niveles)

• Teorema. Un árbol m-ario completo con

o i vértices internos tiene: n = mi + 1 vértices y l = (m-1)i +1 hojas
o n vértices tiene: i = (n-1) /m vértices internos y l = [(m-1)n+1]/m hojas
o l hojas tiene: n = (ml-1) /(m-1) vértices e i = (l-1)/(m-1) vértices internos
• Un árbol m-ario de altura h tiene a lo sumo m^h hojas.

C. APLICACIONES DE LOS ÁRBOLES.

• Árboles binarios de búsqueda (ABB).
o Cada hijo de un v → hijo izquierdo y derecho
o Hijo izquierdo < hijo derecho
o Se compara desde la raíz.

- Insertar:
o Crear una nueva hoja en el caso que no esté el elemento
- Eliminar:
o Si tiene un solo hijo → el hijo ocupa el lugar del padre
o Dos hijos → sustituimos el dato al nodo a borrar por su sucesor
▪ CASO: El sucesor es el menor valor de todos aquellos que son mayores
que el nodo a borrar → Coger menor dato del subárbol derecho.

• Árboles de decisión.
o Árbol con raíz, en el que cada vértice
interno corresponde a una decisión son un
subárbol en dichos vértices para cada
resultado de la decisión.
o Posibles soluciones → caminos desde la
raíz a las hojas
o Ordenación de tres elementos
o Ordenación basada en comparaciones binarias en cada paso. El resultado de
dicha comparación reduce e nº de órdenes posibles.
o Cada hoja representa una de las n! permutaciones de los n elementos.
 • Código instantáneo.
o Secuencia de bits:
▪ 27 letras → cada carácter codificado con 5 bits
▪ Nº total de bits para caracterizar un dato (palabra) = 5 veces el Nº de
caracteres
▪ Codificación que reduzca esta cantidad de bits→ codificar cada carácter
con cadenas de bits de longitudes diferentes. Caracteres más
frecuentes se codificarán con cadenas de bits más cortas
▪ Codificación con cadenas de longitud variable → Método para
determinar cuando comienza y termina la cadena
▪ Cada cadena de bits corresponde a solo una secuencia de caracteres →
Codificar cada carácter tal que su cadena de bits nunca aparezca al
comienzo (no sea prefijo) de la cadena de bits de otro carácter distinto:
Códigos Instantáneos (CI)
o Códigos instantáneos o prefijos pueden representarse por un árbol binario
donde los caracteres son las etiquetas de las hojas del árbol.
o Aristas → 0 hijo izqdo. Y 1 hijo drcho.
o Codificación de un carácter → cadena de bits de las aristas desde la raíz a la hoja

• Código de Huffman:
o Representa caracteres con cadenas de longitud variable en función de la
frecuencia del carácter (más frecuente, más corto).
o Toma como entrada las frecuencias de los caracteres y devuelve un CI que
codifica la cadena con el menor Nº de bits
o Se usa para compresión de datos
o Crear un árbol binario con raíz que tiene cada uno de los símbolos por hoja.
Comienza por un bosque de árboles degenerados y termina en un solo árbol.
Siguiendo desde la raíz hasta sus hojas s obtiene el código de Huffman.

¿Cómo se hace? Ejemplo:

0.10 0.25 0.05 0.15 0.3 0.07 0.08

A B C D E F G

Se suman los valores más pequeños:

- Iteración 1:

0.12

0.05 0.07
C F

- Iteración 2:

0.12 0.18

0.05 0.07 0.08 0.10

C F G A
- Iteración 3:

0.27 0.18

0.12 0.15 0.08 0.10

D G A
C F

- Iteración 4:

0.43 0.27

0.18 0.25 0.12 0.15

B D
G A C F

- Iteración 5:

0.57 0.43

0.27 0.3 0.18 0.25

E B
0.12 0.15 G A
D

C F

- Iteración 6:

0.57 0.43

0.27 E 0.18 B

0.12 D G A

C F

D. RECORRIDOS EN ÁRBOLES.
• Sistema de etiquetado universal o canónico.
o Objetivos: acceder a los datos almacenados en él o para evaluar expresiones
representadas por el árbol
o Estos procedimientos se basan en las ordenaciones definidas en los hijos.
▪ Se etiquetan todos los vértices, recursivamente. El raíz con el “0”,
sus k hijos (nivel 1) con: 1, 2, …, k
▪ Para cada vértice v del nivel n con etiqueta A, etiquetamos sus kv
hijos, de izqda. A derecha como: A.1, A.2,…A. kv
 • Algoritmos de recorridos de un árbol:
o Pre-orden → raíz en primer lugar, izquierda y derecha
o In-orden → izquierda-raíz-derecha
o Post-orden → izquierda-derecha-raíz

Pre-orden In-orden Post-orden

E. EXPRESIONES ALGEBRAICAS
• Vértices internos → operaciones, hojas → números
• Usar paréntesis
o Pre-orden: forma prefija o notación polaca.
▪ +x2–a1x3b
o In-orden: forma infija.
▪ 2 x (a – 1) + 3 x b
o Post-orden: forma postfija notación polaca inversa
▪ A1–2x3bx+

• Árbol de construcción de sólidos:

o Árbol binario para representar sólidos.
▪ Nodos hojas → primitivas
▪ Nodos internos → operaciones topológicas