Matemáticas discretas: 2013

RELACIONES DE EQUIVALENCIA,CLASES DE EQUIVALENCIA Y PATRICIONES.

En teoría de conjuntos, la noción de relación de equivalencia sobre un conjunto, permite establecer una relación entre los elementos del conjunto que comparten cierta característica o propiedad. Esto permite reagrupar dichos elementos en clases de equivalencia, es decir, «paquetes» de elementos similares. Esto posibilita la construcción de nuevos conjuntos «añadiendo» todos los elementos de una misma clase como un solo elemento que los representará y que define la noción de conjunto cociente.

OPERACIONES ENTRE RELACIONES.

COMPLEMENTO DE R.

El complemento de r de un número positivo N en base r con una parte entera de n dígitos, será definido como el complemento de r a n y se define como rn-N;

El complemento de 10 de un número decimal se puede formar dejando todos los ceros significativos sin cambios se resta el primer dígito del cero menos significativo de 10 y, entonces se restan todos los pocos dígitos menos significativos menores de 9.

INTERSECCION.

En teoría de conjuntos, la intersección de dos (o más) conjuntos es una operación que resulta en otro conjunto que contiene los elementos comunes a los conjuntos de partida. Por ejemplo, dado el conjunto de los números pares P y el conjunto de los cuadrados C de números naturales, su intersección es el conjunto de los cuadrados pares D :

P = {2, 4, 6, 8, 10,...}

C = {1, 4, 9, 16, 25, ...}

D = {4, 16, 36, 64, ...}

La intersección de conjuntos se denota por el símbolo ∩ por lo que D = P ∩ C

EMPLEO DE GRAFOS

Partes de un Grafo

Estos estan compuestos por vértices y aristas

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

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.

TIPOS DE GRAFO.

grafo simple
grafo completo
grafo bipartitos
grafo planos
grafo conexo
grafos ponderados
- Representación matricial:
  
  La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.
  
  Caminos
  
  Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso
- x e y se llaman los extremos del camino
- El número de aristas del camino se llama la longitud del camino.
- Si los vértices no se repiten el camino se dice propio o simple.
- Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
- Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
- Llamaremos ciclo a un circuito simple
- Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo.
  
  Grafos Isomorfos:
  
  Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.
  
  GRAFOS PLANOS.
  
  un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano).
  
  USO DE ARBOLES
  
  Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos)
  
  TIPOS DE AROBOLES
- Árboles Binarios
  - Árbol de búsqueda binario auto-balanceable
  - Árboles AVL
  - Árboles Rojo-Negro
  - Árbol AA
- Árboles Multicamino
- Árboles B (Árboles de búsqueda multicamino autobalanceados)
- BOSQUES DE ÁRBOLES.
  
  Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos
  
  PROPIEDADES DE LAS RELACIONES
  
  Propiedad Reflexiva
  
  Diremos que R es reflexiva si  "aÎA, a R a.
  
  Propiedad Simétrica
  
  Diremos que R es simétrica si  " a, b ÎA: a R b Þ b R a
  
  Propiedad Antisimétrica
  
  Diremos que R es antisimétrica si  " a, b ÎA: [a R b Ù b R a] Þ a = b.
  
  Propiedad Asimétrica
  
  Diremos que R es asimétrica si  " a, b ÎA: [a R b Ù b R a]
  
  Propiedad Transitiva
  
  Diremos que R es transitiva si  " a, b, c ÎA: [a R b Ù b R c] Þ a R c
  
  Propiedad de Equivalencia
  
  Para que esta propiedad se cumpla, R debe ser, Reflexiva, Simétrica y Transitiva
  
  APLICACIONES DE LAS RELACIONES
  
  Una lista enlazada es una relación
  
  Las listas enlazadas son tipos de datos dinámicos que se construyen con nodos.
  
  Un nodo es un registro con
  al menos, dos campos, uno de ellos contiene las componentes y se le denomina data (estructura de
  registro), el otro es un valor que señala al siguiente nodo y se le denomina enlace (next).
  
  Relaciones en las bases de datos
  
  EMPLEO DE FUNCIONES
  
  Dadas dos funciones reales de variable real, f y g, se llama composición de las
  
  funciones f y g, y se escribe g o f, a la función definida de R en R, por (g o f )(x) = g[f(x)].
  
  La función ( g o f )(x) se lee « f compuesto con g aplicado a x ».
  
  Primero actúa la función f y después actúa la función g, sobre f(x).
  
  TIPOS DE FUNCIONES
  
  Funciones Algebraicas
  
  En las funciones algebraicas las operaciones que hay que efectuar con la variable independiente son: la adición, sustracción, multiplicación, división, potenciación y radicación.
  
  Funciones explícitas
  
  Si se pueden obtener las imágenes de x por simple sustitución.
  
  $f(x) = 5x - 2$
  
  Funciones Implícitas
  
  Si no se pueden obtener las imágenes de x por simple sustitución, sino que es preciso efectuar operaciones.
  
  $5x - y - 2 = 0$
  
  Funciones Polinómicas
  
  Son las funciones que vienen definidas por un polinomio.
  
  $f(x) = a_0 + a_1 x + a_2 x^{2} + a_3 x^{3} + ... + a_n x^{n}$
  
  Funciones Constantes
  
  El criterio viene dado por un número real.
  
  $f(x)= k$
  
  Funciones Polinómica De Primer Grado
  
  $f(x) = mx + n$
  
  Función Cuadrática
  
  $f(x) = ax^{2} + bx + c$
  
  Son funciones polinómicas es de segundo grado, siendo su gráfica una parábola.
  
  Funciones Racionales
  
  El criterio viene dado por un cociente entre polinomio.
  
  FUNCIONES INVERTIBLES
  
  Una función puede tener inversa, es decir, otra función que al componerla con ella resulte en la identidad, del mismo modo que un número multiplicado por su inverso da 1.
  
  Dada una función f : A → B, se dice que g : B → A es lainversa o recíproca de f si se cumple:
  
  $\begin{align} &f\circ g = \text{id}_B\\ &g \circ f = \text{id}_A \end{align}$
  La inversa se denota por g = f⁻¹, y tanto f como f⁻¹ se dicen invertibles.
  
  No todas las funciones son invertibles, sino que solo aquellas que sean biyectivas poseen inversa:
  
  Toda función biyectiva f es invertible, y su inversa f⁻¹ es biyectiva a su vez. Recíprocamente, toda función invertible f es biyectiva.