SEGUNDO PARCIAL
Unidad 5
Antes de que termine la unidad anterior vimos el producto cartesiano
que era el siguiente:
Que este genera el conjunto de todos los pares ordenados “Par
Ordenado”: (a, b), una relación binaria es solo un conjunto de esos
pares ordenados.
Relación:
Dados dos conjuntos no vacíos A y B, llamaremos relación binaria de
A en B, a todo subconjunto R del producto cartesiano A x B.
Dada una relación binaria R de A en B se pueden diferenciar cuatro
conjuntos:
● Alcance de la relación: o conjunto de partida, es el conjunto de
todas las posibles primeras componentes de los pares ordenados
de R.
● Rango de la relación: conjunto de llegada, es el conjunto de
todas las posibles segundas componentes de los pares ordenados
de R.
● Dominio de la relación: conjunto formado por todas las primeras
componentes de los pares ordenados que efectivamente
pertenecen R.
● Imagen de la relación: conjunto formado por todas las segundas
componentes de los pares ordenados que pertenecen
efectivamente R.
Esta es la
representación en un esquema de una relación binaria y el par
ordenado.
Representación de relaciones:
Como son conjuntos de pares ordenados las relaciones pueden ser
expresadas por extensión o comprensión.
Por extensión: enumerar todos los pares ordenados de la relación.
Por comprensión: las relaciones pueden representarse por
comprensión de diversas formas, siendo cada una útil según el tipo de
relación definida, los conjuntos sobre los cuales está definida y la
aplicación de que se trate.
a) Coloquialmente: expresar la relación en el lenguaje natural.
R: Los nombres de todos los contactos en el grupo de WhatsApp
sus respectivos números de teléfono
b) Por fórmulas: expresar la relación entre la primer y segunda
componente de los pares ordenados usando alguna fórmula.
c) Diagramas (casi) de Venn: la relación se representa por flechas que
conectan la primer componente en el conjunto de partida A con la
segunda componente en el conjunto de llegada B de cada par de la
relación (en realidad, por extensión).
d) Por Digrafo: cuanto la relación es definida en un conjunto R A x A
y el conjunto A es finito la relación puede expresarse mejor que con
un diagrama de Venn, por un grafo dirigido o digrafo (en realidad, por
extensión)
e) Tablas: expresar la relación entre la primer y segunda componente
de los pares ordenados en forma tabular (en realidad, extensión)
f) Matríz 0-1: en dígrafos, llamada matriz de incidencia. Ejemplo:
g) Gráfico cartesiano: en un diagrama de ejes coordenados, se coloca
el alcance de la relación en el eje de abscisas y el rango en el eje de
ordenadas. Así, la relación se representa por puntos del plano que
definen los ejes.
Relación Inversa
: Dada una relación binaria R A B, siempre existe la relación inversa
de R, denotada , definida en B A y obtenida intercambiando las
primeras y segundas componentes de los pares ordenados de R.
Operaciones con relaciones:
Las relaciones son conjuntos de pares ordenados, por lo que se
pueden complementar, unir e intersecar. Pero además, pueden
componerse:
Composición de relaciones:
Funciones
Concepto: ean A y B conjuntos no vacíos y f una relación de A en B.
Entonces f recibe el nombre de función de A en B, si y sólo si, el
alcance coincide con el dominio de la relación y además, dados dos
pares ordenados cualesquiera de f con sus primeras componentes
iguales, resultan iguales sus segundas componentes
Clasificación:
Recursividad
Definición directa: Una explicación de un nuevo concepto utilizando
palabras cuyo significado se conoce con anterioridad.
Definición recursiva: Una explicación de un nuevo concepto
utilizando palabras cuyo significado se conoce y el mismo concepto
que se define. Un tren es un tren con un vagón enganchado a él.
A) Caso base: ejemplos básicos y sencillos del concepto que se
está queriendo definir
B) Caso Recursivo: explicación del concepto haciendo uso de los
casos base y del mismo concepto que se quiere definir dentro de
la explicación.
Ejemplos:
A) Objetos Geométricos: Un objeto geométrico se dice que es
recursivo si forma parte de sí mismo o si está definido en base a
sí mismo.
En la década del 1970 Benoit Mandelbrot acuño el término fractal
para un objeto geométrico cuya estructura básica, fragmentada o
irregular, se repite a diferentes escalas en forma exacta o aproximada.
UNIDAD 7 GRAFOS Y ÁRBOLES
Definición: Un grafo G es un par de conjuntos (N, S), donde N es un
conjunto finito y no vacío de elementos llamados nodos (vértices o
puntos) y S es un conjunto de pares no ordenados y distintos de
elementos de N llamados segmentos (aristas o lados).
G = (N, S)
N = {n1 , n2 , …, nk }
S = {{ni , nj }, {nk , nl }, …, {nm, np }}
Si |N|=1 y |S|=0 el grafo se llama trivial. G = ({n}, {})
Representación de grafos
Vocabulario
Decimos que la arista {A,B} es incidente en los nodos A y B.
Dos nodos conectados por una arista se dice que son adyacentes
Un nodo sin conexión es un nodo aislado
La cantidad de aristas que inciden en un nodo A se denomina grado
del nodo A y se lo denota gr(A). Claramente gr(A)n
Un camino A-C entre dos nodos A y C, es una secuencia de nodos y
aristas tales que cada arista incide en el nodo anterior y posterior en la
secuencia. Hay infinitos!
Camino A-C: A, B, C = Camino A-C:
A, {A, B}, B, {B, C}, C
Si el nodo inicial y final de un camino son el mismo, el camino es un
camino cerrado: A, {A, E}, E, {E, F}, F, {F, A}, A
Teorema 1: En todo grafo G=(N,S) la suma de los grados de los nodos
es igual al doble de la cantidad de aristas:
Vocabulario
El largo o longitud del camino es la cantidad de aristas que lo
forman.
La distancia de(A,B) entre dos nodos A y B, es la longitud del menor
camino A-B.
Camino A-D2 : A, B, D - Largo(A-D2)
= 2 Distancia: d(A-D) = 2
Un sendero entre los nodos A y B es un camino A-B que no repite
aristas.
Camino A-D1 : A, B, C, D - SI es un sendero de A a D.
Camino A-D2 : A, B, C, B, D - NO es un sendero de A a D; repite {B,
C}.
Un circuito es un sendero cerrado.
Una trayectoria entre los nodos A y B es un camino A-B que no
repite nodos.
Un ciclo es una trayectoria cerrada.
Camino B-B: B, C, D, B - SI es un ciclo.
Un grafo se dice que es conexo, si existe un camino entre cualquier
par de nodos.
Un nodo es un punto de corte, si al quitarlo, el grafo resultante es no
conexo. Al quitar un nodo debo quitar todas las aristas incidentes en
él.
Ya no hay caminos desde F o E hasta
cualquiera de los otros nodos, entonces es no conexo.
Teorema 2: En todo grafo G=(N,S) existe una trayectoria A-B si y
sólo si existe un camino A-B.
Toda trayectoria (1, 2, 5) es un sendero, pero no todo sendero (1, 2, 3,
4, 2, 5) es una trayectoria. 1 4 5
TIPOS DE GRAFOS
Subgrafo: Un subgrafo G’ = (N’, S’) de un grafo dado G = (N, S) es
una parte de G, de tal forma que N’N y S’S y las aristas de S’ son
incidentes en los nodos de N’.
Multigrafo: Un multigrafo M = (N, S) es un grafo en el cual el
conjunto de aristas S es un multiconjunto, lo que permite que existan
aristas paralelas (que inciden en los mismos nodos) y lazos (arista de
un nodo a sí mismo).
Por oposición, se dice que un grafo G que no tiene aristas paralelas ni
lazos es un grafo simple o simplemente un grafo.
Digresión: circuito euleriano y teorema de Eüler
Definición: Dado un multigrafo M = (N, S), un circuito euleriano es
un camino cerrado en el que no se repiten aristas y se incluyen todas
las aristas.
Teorema de Eüler: En todo multigrafo conexo M = (N, S), existe un
circuito euleriano si y sólo sí, todos los nodos tienen grado par.
Corolario: En las condiciones del teorema, existirá un sendero
euleriano si y sólo sí, tiene sólo dos nodos de grado impar y el resto
son de grado par.
Definición: Un grafo G = (N, S) se dice que es grafo completo si en
S existe una arista entre cualquier par de nodos de N. En símbolos:
Definición: Un grafo G = (N, S) se dice que es un grafo plano si
puede dibujarse en el plano sin que se corten sus aristas.
Si existe alguna forma de
dibujar el grafo sin que las aristas se corten es plano.
El dibujo plano de un grafo plano, se denomina mapa y divide al
plano en áreas llamadas regiones, una no acotada -exterior- y otras
acotadas.
Teorema 3: En todo mapa de un grafo plano conexo G=(N,S) se
verifica que (fórmula de Eüler): |N| – |S| + |R| = 2
Definición: Un grafo rotulado G = (N, S, f), o etiquetado, es un grafo
en el que las aristas tienen asignada alguna información mediante una
función f:S→R, siendo R el conjunto de rótulos.
Si los rótulos son números reales no negativos, se dice que el grafo
está ponderado o pesado por la función de peso f.
Las aristas dirigidas se llaman también arcos
Al ser A una relación, el digrafo se puede representar por una matriz
de incidencia.
Si no hay aristas paralelas la matriz será 0-1, sino tendrá nN.
Vocabulario
Los arcos tienen un nodo inicial y un nodo final.
Un nodo v tiene un grado de salida gs(v) y un grado de entrada
ge(v) que es la cantidad de arcos que salen y llegan a v.
Se llama sumidero a un nodo con gs(v) = 0 y ge(v) 0.
Se llama fuente a un nodo con gs(v) 0 y ge(v) = 0.
Camino, sendero, trayectoria, circuito, ciclo, lazo, dirigidos.
Teorema 4: En todo digrafo D=(N, A) la suma de los grados de salida
de todos los nodos es igual al la suma de los grados de entrada de
todos los nodos:
ARBOLES
Definición: Un árbol A = (N, S) es un grafo conexo acíclico.
Al ser un árbol, un grafo que no tiene ciclos y que es conexo,
necesariamente existirá un único sendero entre cualquier par de nodos
del mismo.
Un árbol compuesto por un único nodo se denomina árbol trivial. Un
nodo u con gr(u)=1 se llama colgante u hoja. Si gr(u) > 1 se le llama
un nudo o nodo interno.
Un conjunto de árboles es denominado un bosque.
Definición: Dado un grafo G = (N, S), un subgrafo de G que sea un
árbol e incluya todos los nodos de N se denomina un árbol maximal
de G
Así, un árbol maximal de un grafo es un conexionado de todos los
nodos del grafo con una cantidad mínima de aristas.
Definición: Dado un grafo rotulado G = (N, S, p) con una función de
pesos p:S→R, árbol maximal que tenga las aristas de G que sumen el
menor peso posible, se denomina un árbol maximal minimal de G.
Así, un árbol maximal minimal de un grafo es un conexionado de
todos los nodos con un peso mínimo.
Para obtener el árbol maximal minimal de un grafo pesado G, voy
quitando las aristas de mayor peso que se pueda, cuidando que el
grafo resultante se mantenga conexo.
Un árbol maximal minimal de G
Definición: Un árbol con raíz es un grafo dirigido acíclico conexo (un
árbol dirigido) en el cual existe un único nodo R denominado raíz,
desde el cual existe un camino dirigido hacia cualquier otro nodo del
árbol.
Vocabulario
Nivel o profundidad de un nodo: es el largo del camino desde la raíz
al nodo.
Altura del árbol es el mayor nivel.
Hojas son los nodos con grado 1; otros internos
Rama es la trayectoria de un nodo a una hoja
Los nodos se dicen que preceden o siguen a otro.
Como pueden usarse para mostrar parentescos (genealógico) también
hay denominaciones como padre, hijo, hermano, antepasados,
descendientes, etcétera.
UNIDAD 6
Ya hablamos de George Boole (1815-1864), matemático británico que
inició la Lógica Simbólica con la publicación en 1854 de Una
investigación de las leyes del pensamiento sobre las cuales se
fundamentan las teorías matemáticas de la lógica y las probabilidades.
Claude Shannon (1916-2001), matemático e ingeniero
estadounidense, que con su Teoría Matemática de la Información
establece los principios de la Teoría de la Información, desarrolla su
tesis de maestría en 1937 donde muestra las aplicaciones del álgebra
booleana al análisis y síntesis de circuitos digitales.
Así, nace la posibilidad de utilizar símbolos en electrónica.
Álgebra Booleana Binaria
Entonces tendremos un conjunto B = {0, 1} con dos valores y sobre él
definiremos las operaciones de complemento (negación lógica),
adición (disyunción lógica) y multiplicación (conjunción lógica)
Propiedades
Variables booleanas: cuando se utilizan letras como a, b, …, x, y, z
para denotar un elemento cualquiera del conjunto B, se dice que las
mismas son variables booleanas y estas variables toman valores en B.
Expresiones booleanas: Una expresión booleana, es una
combinación bien formada de variables booleanas, 0, 1, y operaciones
+, . , –. Puede darse una definición recursiva de expresión booleana:
Función booleana: Una expresión booleana E(x1 , x2 , …, xn ) toma
distintos valores cuando las n variables x1 , x2 , …, xn que la
componen toman sus valores 0 y 1 del conjunto B. La relación entre
cada combinación de los valores de las variables booleanas y el de la
expresión booleana es una función booleana
Dos funciones booleanas son equivalentes si tienen igual tabla de
verdad
