1.2.2. Tipos de Grafos

Grafo Etiquetado: son grafos que contienen datos en sus aristas. Datos los cuales tienen un significado, los datos pueden tener un significado entre dos vértices.

Ejemplo:

G = (V, E);

V = {0,1,2,3,4,5}

E= {0,1,2,3,4,5}

Grafo dirigido o dígrafo: son grafos en los que sus aristas tienen dirección única, estas aristas al realizar un enlace entre dos vértices no puede tener un segundo enlace de retorno.

Explicado de mejor manera: se puede decir (a,b) pero es totalmente negable que exista en el mismo conjunto (b,a). Es decir (a,b) ≠ (b,a).

Ejemplo: 

G = (V, E);

V = {a,b,c,d}

E= {(a,b)(a,c)(b,c)(b,d)(c,d)}

Grafo Simple: Es la existencia de una unión de elementos del conjunto sin importar que solamente exista una,

                                                       

Grafo Completo: Es cuando todos los elementos de un conjuntos estas relacionados entre si y no debe de existir alguna excepción. toda vértice debe estar conectada a las demás del conjunto.

                                                         

Grafo Bipartito: Es un grafo compuesto por dos conjuntos de elementos que tienen relacion entre si. Existe relacion o vértices que se interceptan de diferentes conjuntos.

                                                

Read More

1.2. Teorıa de Grafos: Conceptos Fundamentales Definicion de un Grafo y Notacion

Grafo: Es un conjunto de objetos llamados vértices unidos mediante enlaces llamados aristas que permite realizar enlaces entre varios elementos de un conjunto. Es una manera muy descriptiva de solucionar un problema mediante posibles soluciones o decisiones a tomar.

Aristas: Elemento que enlaza dos vértices generalmente una linea que hace posible la relación dentro de un conjunto.
Vértice: Son los puntos fundamentales de un grafo, elementos de un conjunto que puede tener relaciones entre si.

Los grafos surgieron como una necesidad en la solución de problemas donde existían 

El primer articulo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se base en su articulo problemas de los puentes Königsberg. el problema se planteaba de la siguiente manera: Partiendo desde un punto de la ciudad es posible pasar atravez de todos los puentes solamente una vez llegando a todas las zonas de la ciudad y volver al punto de inicio.

Euler pudo concluir que era imposible la solución a dicho problema, aplicando modificaciones al problema podía tener solución.

Un Grafo cuenta con las siguientes propiedades: 

Adyacencia: Dos aristas son adyacentes si tienen un vertice en comun.

Incidencia: Una arista es indicente  a un vertice si esta lo uno a otro.

Ponderación: Corresponde a una funcion donde a cada arista se le asigna un varlo el cual esta implicado con el problema. el dato asignado puede ser moneda, distancia, peso, etc.

Etiquetado: Dato que se le asigna a las vertices o aristas, presentando de manera descriptiva las opciones y decisiones en le problema.

Ejemplo de Grafo:

                                  

Read More

1.1.2.4 Producto Cartesiano

Producto Cartesiano

Existe todavía otra operación para construir conjuntos a partir de unos dados; esta operación lleva implícita la noción de “par ordenado”. 

Por ejemplo, un punto en el plano cartesiano, lo podemos denotar como un par ordenado (x, y) y va corresponder de manera única a ese punto, de esta manera si se escribe un punto de la forma (3, 5) significa que con respecto a punto de referencia el punto esta ubicado a 3 unidades a la derecha y 5 unidades hacia arriba. 

La noción de pares ordenados se pueden generalizar a cualquier conjunto, sin necesidad de que sean conjuntos numéricos.

 Dados dos conjuntos A y B, se define su producto cartesiano A × B como el conjunto de todos los pares ordenados (a, b) para los cuales a es un elemento de A y b es un elemento de B. 

Formalmente A × B = {(a, b)|a ∈ A y b ∈ B}

Ejemplo: 1.1.2.4 

Sean los conjuntos A = {a, b, c, d} y B = {1, a, 2, b, 3, 4, 5} 

Determinar el producto cartesiano de A y B.

 Solución: A × B = {a, b, c, d} × {1, a, 2, b, 3, 4, 5} = {(a, 1),(a, a),(a, 2),(a, b),(a, 3),(a, 4),(a, 5),(b, 1),(b, a), ...,(d, 4),(d, 5)}

 Por lo tanto, tenemos que: A × B = {(a, 1),(a, a),(a, 2),(a, b),(a, 3),(a, 4),(a, 5),(b, 1),(b, a), ...,(d, 4),(d, 5)}. 

Observe que los pares ordenados se han escrito por extencion, usando puntos suspensivos dentro de las llaves, para omitir escribir todos los pares ordenados

Read More

1.1.2.3 Diferencia entre dos Conjuntos

Diferencia entre dos Conjuntos

Existe otra operación entre conjuntos que, en ocasiones resulta muy útil.

Se trata de la diferencia de dos conjuntos, que se denotara por A − B, y que se define como el conjunto formado por los elementos de A que no pertenecen a B.

Formalmente A − B = {x|x ∈ A y x /∈ B}

 En ocasiones tambien se le denomina complemento de B relativo a A.

Ejemplo: 1.1.2.3 Sean los conjuntos A = {a, b, c, d} y B = {1, a, 2, b, 3, 4, 5}

Determinar de A − B y B − A.

Solucion:
A − B = {a, b, c, d} − {1, a, 2, b, 3, 4, 5} = {c, d}
B − A = {1, a, 2, b, 3, 4, 5} − {a, b, c, d} = {1, 2, 3, 4, 5}

 Por lo tanto, tenemos que

A − B = {c, d}
 B − A = {1, 2, 3, 4, 5}.

Por lo cual, se puede concluir que A − B es diferente de B − A

Read More

1.1.2.2 Intersección de Conjuntos

Intersección de Conjuntos

Dados dos conjuntos A y B, otra forma de construir un nuevo conjunto es tomar los elementos en común de A y B. 

Este nuevo conjunto se llama intersección de A y B y se representa por A ∩ B. 

El resultado siempre es otro conjunto y que ese nuevo conjunto resultante, va contener a solamente los elementos comunes a A y B.

Formalmente, se define A ∩ B = {x|x ∈ A y x ∈ B} 

Ejemplo: 1.1.2.2 

Sean los conjuntos A = {a, b, c, d} y B = {1, a, 2, b, 3, 4, 5} 

Encontrar la intersección de A y B. 

Solución: A ∩ B = {a, b, c, d} ∩ {1, a, 2, b, 3, 4, 5} = {a, b, }

 Por lo tanto, tenemos que A ∩ B = {a, b}

Ahora bien, ¿que ocurre cuando los conjuntos no tienen elementos en común? 

¿A que seria igual A ∩ B?

El conjunto vació, tal y como lo indica su nombre, es el conjunto “que no tiene elementos”. 

Utilizando esta notación, expresaremos el hecho de que A y B no tengan elementos en común escribiendo A ∩ B = ∅.

También diremos en esta situación que los conjuntos A y B son disjuntos.

Read More

1.1.2.1 Union de Conjuntos

Unión de conjuntos

Dados dos conjuntos A y B, se puede construir un nuevo conjunto formado por los elementos de A junto con los elementos de B. Este conjunto se llama unión de A y B y se representa por A ∪ B.

Se formara un nuevo conjunto que contendrá a todos los elementos de ambos conjuntos A y B

 De manera formal, se define A ∪ B = {x/x ∈ A o x ∈ B} 

Ejemplo: 1.1.2.1 

Sean los conjuntos A = {a, b, c, d} y B = {1, a, 2, b, 3, 4, 5}

 Encontrar la unión de A y B. 

Solución: A ∪ B = {a, b, c, d} ∪ {1, a, 2, b, 3, 4, 5} = {1, 2, 3, 4, 5, a, b, c, d} 

Por lo tanto, tenemos que A ∪ B = {1, 2, 3, 4, 5, a, b, c, d}

 Observe que los elementos a y b están en ambos conjuntos, pero en la unión se escriben solamente una vez.

Read More

1.1.2 Operaciones entre Conjuntos

¿Se pueden sumar dos conjuntos?

 Probablemente, la respuesta inmediata es si. Por lo cual es necesario hacer un análisis un poco mas profundo.

Supongamos que tenemos el conjunto A formado por todos los  arboles y el conjunto B formado por todos los peces. ¿A que seria igual A + B?

 ¿Parece un poco mas complicado no?

 Pues resulta, que estrictamente dentro de la lógica no tendría sentido sumar dos conjuntos. Y en esa misma lógica, tampoco tiene sentido multiplicar, restar o dividir conjuntos. Por lo cual, se hace estrictamente necesario definir otras operaciones que puedan ayudar al tratamiento de conjuntos y explotar sus propiedades. Las operaciones entre conjuntos que vamos estudiar son:

1. Unión de Conjuntos
2. Intersección de Conjuntos
3. Diferencia de Conjuntos
4. Producto Cartesiano 

  

Read More

1.1.1.2 Teoría de Conjuntos: Representación de Conjuntos

Representación de Conjuntos

¿Como se puede especificar el contenido de un conjunto? 

Si el conjunto tiene pocos elementos, basta con enumerarlos escribiendo “A es el conjunto que contiene los elementos a, b, c”. Esta situación la escribimos de manera simbólica como:  

A = {a, b, c} 

donde las llaves encierran la lista de los elementos del conjunto y cada elemento del conjunto lo separamos por comas.

De cualquier forma, la manera mas común para especificar los elementos de un conjunto, consiste en expresar alguna propiedad que dichos elementos verifiquen. Por ejemplo podemos tomar el conjunto B como el conjunto formado por todos los números enteros pares. Esta situación se expresa de manera simbólica como sigue:  

B = {x|x es un numero par} 

En resumidas cuentas, podemos especificar los elementos que forman un conjunto, o expresar el conjunto propiamente dicho, de tres maneras: 

1. Mediante Lenguaje Natural: Cuando expresamos el conjunto de manera común por ejemplo el conjunto de las plantas, el conjunto de los animales, etc.

2. Por Extensión: Cuando expresamos el conjunto nombrando cada uno de sus elementos entre llaves. Por ejemplo:   A = {1, 2, 3, 4, 5},   D = {m, n, o, p}. 

Debe tomar en cuenta, que cuando use esta notación, no debe repetir elementos dentro del conjunto, de ´esta manera el conjunto B = {d, a, d, o}, esta mal escrito, ya que se repite dos veces el elemento ”d”dentro del conjunto. Ademas debe separar cada uno de elementos por comas (,) para evitar confusiones, de esta manera, si tenemos el conjunto A = {Lima} y el conjunto B = {L, i, m, a} vamos a tener que: 

ya que el conjunto A esta formado por un solo elemento y el conjunto B indica que esta formado por 4 elementos. 

3. Por Comprensión: Cuando expresamos el conjunto mediante alguna propiedad de los elementos del conjunto. Por ejemplo A = {x|x es un triangulo},   B = {y|y es un numero mayor que 5}, etc.

Ejemplo:  Expresar el conjunto de los números naturales mediante extensión y comprensión: 

En primer lugar, recordemos que el símbolo que se ha adoptado de manera universal para representar a los naturales es N.  De esta manera tenemos: 

a) Por Extensión: Se puede expresar el conjunto como N = {1, 2, 3, 4, 5, 6, 7, ...} Observe que se usan puntos suspensivos para denotar que los elementos del conjunto se extienden de manera infinita (los números naturales son infinitos). 

b) Por Comprensión: En este caso, la propiedad que conocemos del conjunto es que justamente son números naturales de esta manera podemos expresar  N = {x|x es un numero natural}.

Read More

1.1.1. Teoría de Conjuntos: Nociones Fundamentales sobre Conjuntos

Nociones Fundamentales sobre Conjuntos.

Introducimos aquí las ideas básicas de la teoría de conjuntos y establecemos la terminología y la notación. También discutimos algunos puntos sobre la lógica, ya que es necesario evitar la producción de contradicciones.

Notación Básica Habitualmente usaremos las letras A, B, C, ... para representar conjuntos y letras minúsculas, como a, b, c, ... para representar los elementos u objetos que pertenecen o forman parte de esos conjuntos. Si un objeto a pertenece a un conjunto A, expresaremos ´este hecho con la notación: 

El símbolo de igualdad “=” para nosotros va significar identidad lógica. De modo que cuando escribimos a  =  b estamos queriendo decir que a y b son símbolos para el mismo objeto. Es la misma situación, por ejemplo, que en aritmética cuando se escribe 2/4 = 1/2 . Análogamente, la ecuación A = B establece que “A” y “B” son símbolos distintos que representan el mismo conjunto. De aquí, podemos concluir que dos conjuntos son iguales si están formados precisamente por los mismos elementos.

Si a y b son elementos distintos, escribiremos:

si A y B son conjuntos diferentes, escribiremos:

Por ejemplo, si consideramos que A es el conjunto de los n´umeros naturales y B es el conjunto de los enteros,

 ya que tienen diferentes elementos.

Diremos que A es subconjunto de B, si cada elemento de A es tambi´en un elemento de B y expresamos este hecho escribiendo:

A ⊂ B

Observe que nada en esta definición impide que A sea diferente de B, de hecho, si A = B, es cierto que A ⊂ B y que B ⊂ A. Si A es subconjunto de B y ademas son conjuntos diferentes, diremos que A es un subconjunto propio de B y escribiremos:

Las relaciones:

Se denominan inclusión e inclusión propia respectivamente. Si A ⊂ B, también podemos escribir 

B ⊃ A y se lee “B contiene a A”.

Read More

1.1. Teoría de Conjuntos: Introduccion

Introducción 

La idea de agrupar objetos de la misma naturaleza para clasificarlos en “colecciones” o “conjuntos” es parte de la vida diaria de los seres humanos. Por ejemplo, el conjunto de libros de una biblioteca, el conjunto de arboles en un terreno, el conjunto de zapatos en un negocio de venta al publico, el conjunto de utensilios en una cocina, etcétera. En todos estos ejemplos, se utiliza la palabra conjunto como una colección de objetos. Vamos adoptar, un punto de vista sencillo en lo relacionado a la teoría de conjuntos. Supondremos que lo que se entiende por conjunto es algo intuitivamente claro, y procederemos sobre esa base. Diremos de manera inmediata, que un conjunto es una colección de objetos. En este sentido un conjunto es una agrupación, asociación, colección, reunión, unión de integrantes homogéneos y heterogéneos, los cuales pueden ser de naturaleza real o imaginaria. En conclusión pueden estar integrados por letras, números, meses de un a˜no, astros, países, mares, ¿vacas voladoras?, etc., a los integrantes en general se les llama elementos del conjunto. El origen de este concepto se debe al matemático alemán George Cantor (1845- 1918). Su objetivo era el de formalizar las matemáticas como ya se había hecho con el calculo cien años antes. El concepto de conjunto es uno de los mas fundamentales en matemáticas, incluso mas que la operación de contar. De esta manera, comprender la teoría de conjuntos se vuelve fundamental para el estudio de cualquier ciencia.

Read More

1.0. Teoria de Conjuntos: Un poco de historia

Un poco de Historia 

El concepto de conjunto es uno de los mas fundamentales en matemáticas, incluso mas que la operación de contar. De ´esta manera, comprender la teoría de conjuntos se vuelve fundamental para el estudio de cualquier ciencia. 

George Cantor (1845-1918)

El origen de la teoría de conjuntos se debe a este matemático alemán. Su objetivo era el de formalizar las matemáticas como ya se había hecho con el calculo cien anos antes. Es decir, su idea era dotar las matemáticas de una estructura. 

El concepto de conjunto es uno de los mas fundamentales en matemáticas, incluso mas que la operación de contar. De esta manera, comprender la teoría de conjuntos se vuelve fundamental para el estudio de cualquier ciencia 

El origen de la teoría de conjuntos se debe a este matemático alemán. Su objetivo era el de formalizar las matemáticas como ya se había hecho con el calculo cien años antes. Es decir, su idea era dotar las matemáticas de una estructura. 

Read More