Teoría de grafos

Nombre:
María Fernanda Chuez

Curso/Jornada:
5to. “Alfa” Matutina

Profesor:
Daniel Pesantes



Materia:
Matemática

Año Lectivo:
2013- 2014

Índice:
1. Grafos
2. Vértices
3. Aristas
4. Circuito de Hamilton
5. Circuito de Euler



























Grafos
Concepto de grafos
Un grafo es una pareja de conjuntos G = (V,A), donde V esel conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que, tal que. Para simplificar, notaremos la arista (a,b) como ab.

»Multigrafo: Cuando hay 2 o más aristas paralelas, o cuando 2 vértices están relacionados más veces con sigo mismo.





»Dígrafo: Hay un punto de origen y uno de destino final, es decir: no pueden ser
a,b =b,a.




Estructura de los grafos
-Un grafo es un par ordenado , donde:
es un conjunto de vértices o nodos.
es un conjunto de aristas o arcos, que relacionan estos nodos.
-Normalmente suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.
-Se llama orden del grafo a su número de vértices, 
-El grado de un vértice o nodo es igual alnúmero de arcos que se encuentran en él.
-Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Tipos de grafos

Grafos simples: Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo queno es simple se denomina multigrafo.


Grafo completo: Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente K, siendo Kn  el grafo completo de n vértices. Un Kn, es decir, grafo completo de n vértices tieneexactamente n(n-1)/2  aristas.

La representación gráfica de los  como los vértices de un polígono regular da cuenta de su peculiar estructura.


Grafos bipartitos: Un grafo G es bipartito si puede expresarse como  G = {V1 U V2, A} (es decir, sus vértices son 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.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debeunirse un elemento de la columna A con un elemento de la columna B.


Grafos Planos: Un grafo G es plana si admite una representación en el plano de  tal forma que las aristas no se cortan, salvo en sus extremos. A dicha representación se le denomina grafo plano. Se dice que un grafo es plano si puede dibujarse en el plano de manera que ningún par de sus aristas se corte. A ese dibujo se lellama representación plana del grafo.



Grafo conexo: Un grafo se dice que es conexo si cada par de sus vértices están conectados. Es decir, G es conexo ⇐⇒ ∀u, v: ∃µ = [u, v]
En caso contrario, diremos que G es un grafo desconexo.





Grafos ponderados: Llamamos grafos ponderados a los grafos en los que se asigna un número a cada una de las aristas. Este número representa un peso para elrecorrido a través de la arista. Este peso podrá indicar, por ejemplo, la distancia, el costo monetario o el tiempo invertido, entre otros.

Definimos la longitud de un camino en un grafo ponderado como la suma de los pesos de las aristas de ese camino.


Propiedades de los grafos
Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una...