Conceptos matemáticos preliminares

Teoria de Conjuntos:
El concepto de conjunto es intuitivo y podríamos definirlo simplemente como una colección de objetos, Usualmente los conjuntos se representan con una letra mayúscula: A, B, K,...

Llamaremos elemento, a cada uno de los objetos que forman parte de un conjunto, estos elementos tienen carácter individual, tienen cualidades que nos permiten diferenciarlos, y cada uno de ellos es único, no habiendo elementos duplicados o repetidos. Los representaremos con una letra minúscula: a, b, k,...

De esta manera, si ~A es un conjunto, y ~a, b, c, d, e todos sus elementos, es común escribir:

~A= \{a, b, c, d, e\}
Conjuntos definidos:

El universo de discurso, conjunto universal o referencial, que normalmente se denota por las letras U, V o E, es un conjunto cuyo objeto de estudio son los subconjuntos del mismo.

Existe además, un único conjunto que no tiene elementos al que se le llama conjunto vacío y que se denota por \emptyset. Es decir

\emptyset = \{\}

La característica importante de este conjunto es que satisface todos los elementos posibles no están contenidos en él, es decir

\forall x \quad x\notin\emptyset.
Operaciones con Conjuntos:

Unión:
Diagrama de Venn que ilustra

Diagrama de Venn que ilustra A\cup B

Para cada par de conjuntos A y B existe un conjunto que se denota como A\cup B el cual contiene todos los elementos de A y de B. De manera más general, para cada conjunto S existe otro conjunto denotado como \bigcup S de manera que sus elementos son todos los x\in X tales que X\in S. De esta manera A\cup B es el caso especial donde S=\{A,B~\}.

Intersección

Diagrama de Venn que ilustra

Diagrama de Venn que ilustra A\cap B

Los elementos comunes a ~A y ~B forman un conjunto denominado intersección de ~A y ~B, representado por A\cap B . Es decir, A\cap B es el conjunto que contiene a todos los elementos de A que al mismo tiempo están en B:

A\cap B = \{x\in A:x\in B\}.

Si dos conjuntos ~A y ~B son tales que A\cap B =\emptyset, entonces ~A y ~B se dice que son conjuntos disjuntos.


Diagrama de Venn que muestra y

Digrama de Venn que muestra A - B~~~ y B - A~

Los elementos de un conjunto ~A que no se encuentran en otro conjunto ~B, forman otro conjunto llamado diferencia de ~A y ~B, representado por ~A\setminus B. Es decir:

A\setminus B= \{x\in A:x\notin B\}.

o dicho de otra manera:

x\in(A\setminus B)\iff (x\in A) \wedge (x\notin B)

Algunas personas prefieren denotar la diferencia de A~ y B~ como A-B~.


Complemento

El complemento de un conjunto A, es el conjunto de los elementos que pertenecen a algún conjunto U pero no pertenecen a A, que lo representaremos por A^\complement . Es decir

A^\complement=U\setminus A

El conjunto complemento siempre lo es respecto al conjunto universal que estamos tratando, esto es, si hablamos de números enteros, y definimos el conjunto de los números pares, el conjunto complemento de los números pares, es el formado por los números no pares. Si estamos hablando de personas, y definimos el conjunto de las personas rubias, el conjunto complementario es el de las personas no rubias.

En vista de que A\subseteq U y B\subseteq U, entonces

x\in \left (A\setminus B\right) \iff x\in \left(A\cap B^\complement\right),

de manera que

A\setminus B=A\cap B^\complement

Grafo
Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de subconjuntos de la forma (u,v) tal que (u,v) \in V, tal que u \neq v. Para simplificar, notaremos la arista {a,b} como ab.

Un vértice es la unidad fundamental de la que están formados los grafos. Los vértices son tratados como un objeto indivisible y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan conceptos o clases de objetos.

tipos de Grafos:

Grafos Ciclicos

Un grafo ciclico consiste en un sólo ciclo. un grafo ciclico se denota por Cn, donde n es el número de vértices.












Grafos Bipartitos

Un grafo G es bipartito si puede expresarse como G = \{V_1 \cup V_2, A\} (es decir, la unión de



dos grupos de vértices), bajo las siguientes condiciones:

  • V1 y V2 son disjuntos y no vacíos.
  • Cada arista de A une un vértice de V1 con uno de V2.
  • No existen aristas uniendo dos elementos de V1; análogamente para V2.



Grafos Completos

Un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices.
El conjunto de los grafos completos es denominado usualmente \mathbb{K}, siendo \mathbb{K}_n el grafo completo de n vértices.

Un Kn, es decir, grafo completo de n vértices tiene exactamente \frac{n(n-1)}{2} aristas.










Árbol

Un árbol es un grafo dirigido aciclico en el que cada nodo está conectado con un camino simple, partiendo desde el nodo distinguido llamado "raiz". un nodo y es "hijo" de x, y x el "padre" de y, si y es es adyacente y x esta más cercano a la raiz o es la raiz.