Sem título

1. Conceptos fundamentales

Teoria de Grafos

Definicion 1.

Conjunto: es una colección de elementos de tal manera que es posible establecer si un elemento dado pertenece o no a un conjunto. Un conjunto se puede representar con un par de llaves { } escribiendo los elementos que contiene.

Ejemplo 1:

A = { x, y, z, w }

Igualdad de conjuntos. Dados dos conjuntos A y B, se dice que son iguales, (y lo denotamos por A=B) , si están formados por exactamente los mismos elementos. En símbolos: A = B ↔ ∀ x: x ∈ A → x ∈ B ∧ ∀ y: y ∈ B → y ∈ A

Se suele llamar también a la anterior definición, Principio de extensión.

Ejemplo 2: Dado el conjunto A={1, 2, 3}, defina otros tres iguales al mismo.

Solución:

B = {2, 3, 1, 1}

C = {x/ x ∈ N ∧ x < 4}

D = {x/ (x=1) ∨ (x=2) ∨ (x=3)}

Operaciones con conjuntos. Sean A y B dos subconjuntos de un conjunto universal U. Definimos las siguientes operaciones entre conjuntos:

Unión: A ∪ B = { x∈U : x∈ A ó x∈ B }

Intersección: A ∩ B = { x∈U : x∈ A y x∈ B }

Diferencia: A - B = { x∈U : x∈ A ^ x B }

Complementario: ó U \ A { x ∈ U : x A }

Definición 2.

Producto Cartesiano: En teoría de conjuntos, el producto cartesiano de dos conjuntos es una operación que resulta en otro conjunto cuyos elementos son todos los pares ordenados que pueden formarse tomando el primer elemento del par del primer conjunto, y el segundo elemento del segundo conjunto.

Por ejemplo, dados los conjuntos A = {1, 2, 3, 4} y B = {a, b}, su producto cartesiano es:

A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b), (4, a), (4, b)}

Par Ordenado: Un par ordenado es un conjunto de dos elementos donde se tiene prioridad en el orden de dichos elementos; cada uno de esos elementos ocupa una posición fija. El primer elemento se llama “primera componente” o “primera coordenada” y el segundo elemento se denomina “segunda componente” o “segunda coordenada”.

Definición 3.

Relación: Sean A y B conjuntos finitos. Si R es un subconjunto del producto cartesiano AxB tal que los elementos x de A cumplen la propiedad con respecto a los elementos y de B, se dice que R es una relación definida de A en B y se denota R:A→B al que xRy o (x,y) ∈ R. Por lo tanto, se dice x de A está relacionado con y de B. Al conjunto A se llama “conjunto de partida” y a B “conjunto de llegada”.

Ejemplo 3: Sea A={1,2,3,4}, B={2,3,4} y R:A→B la relación definida por R: ”ser menor que”. Calcule R.

R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

Quedará como ejercicio el cálculo de R: B→A

Relación Binaria: Dado cualquier par de elementos de un conjunto que cumplen o no una propiedad determinada se dice que establecen una relación binaria.

A menudo, la relación R es definida en A, esto es, y se dice que o simplemente R(A), que denominaremos “relación binaria definida en A”. Este tipo de relación es de gran importancia para aplicaciones de la computación (especialmente dentro de modelo emparentado para bases de datos) y en matemáticas aplicadas.

Relación Inversa: Sea R una relación de A a B, la inversa de R, representada por R-1 , es una relación de B a A que se define como sigue:

Representación Gráfica de una Relación: Las relaciones pueden representarse gráficamente de diversas maneras siendo las más comunes la representación cartesiana, la matricial y la sagitaria.

Mediante un gráfico cartesiano: En este caso se consideran como abscisas las primeras componentes y como ordenadas las segundas componentes. Mediante paralelas a los ejes trazados por los puntos de división se forma una cuadrícula cuyos elementos son los vértices de un producto cartesiano; de estos se señalan los que pertenecen a la relación R.

Dominio y Rango de una Relación: De una relación R se pueden definir conjuntos de gran importancia en el desarrollo de las matemáticas, de las ciencias y la tecnología: dominio e imágenes de R.

Conjuntos dominio de una relación: Sean A y B conjuntos cualesquiera y R una relación definida de A en B. El dominio de una relación R, denotado D(R) es el conjunto formado por todas la x o todos los primeros elementos o primeras componentes de la relación; así que,

Al dominio también se llama conjunto de “pre-imágenes” o de “partida”.

Conjunto imágenes de una relación: Sean A y B conjuntos cualesquiera y R una relación definida de A en B. Las Imágenes de una relación R, denotado Im(R) es el conjunto formado por todos los segundos elementos o segundas componentes de la relación; así que,

Propiedades de una relación: Las relaciones cumplen con ciertas propiedades que apoyan la gran importancia en aplicaciones computacionales y en el desarrollo de las matemáticas aplicadas. Las relaciones se pueden clasificar de acuerdo al tipo de asociación que hay en sus elementos como: uno-a-uno 1–1, uno-a-mucho 1-M, muchos-a-uno M-1 o muchos-a-muchos M-M. Sea A un conjunto finito cualquiera y R:A→A una relación, entonces se tienen las siguientes propiedades:

Relación reflexiva

Se dice que una relación R definida en A es “reflexiva” si todos los elementos de A están relacionados consigo mismo; es decir, si todos los elementos de A forman parejas ordenadas en R con componentes iguales. Simbólicamente,

.