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