unidad 6 teorema de grafos matematicas discretas

 Unidad 6 Teoría de grafos
6.1 Elementos y Características de los Grafos
 
Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices. Los grafos representan conjuntos deobjetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. La notación
G = A (V, A)
Se utiliza comúnmente para identificar un grafo. Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismografo.


























6.1.1.- componentes de un grafo (vértices, aristas, lazos, valencia)

Aristas.- son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.
Aristas adyacentes: se dice que dos aristas son adyacentes si coinciden en el mismo vértice.
Aristas paralelas: se dice que dos aristas son paralelas sivértice inicial y el final son el mismo
Aristas cíclicas: arista que parte de un vértice para entrar en el mismo.

Vértices.- Son los puntos o nodos con los que está conformado un grafo.

Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

Vértices Adyacentes: si tenemos un par de vértices de un grafo (U,V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
Vértice Aislado: Es un vértice de grado cero.
Vértice Terminal: Es un vértice de grado 1
Lazo: es una arista cuyos extremos inciden sobre el mismo vértice
Valencia de un vértice.- Es el numero de lados que salen o entran a un vértice. En el grafoanterior las valencias de los vértices son:

Valencia (a)=2
Valencia (b)=4
Valencia (c)=2
Valencia (d)=3

Hay que observar como en el caso del vértice del lazo solo se considera una vez, entrada o salida pero no ambos.











6.1.2.- tipos de grafos (simples, completos, bipartidos, planos, conexos, ponderados)
Grafos simples.- Un grafo es simple si a lo más existe una aristauniendo 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 que no es simple se denomina multígrafo.

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 esdenominado usualmente K, siendo Kn  el grafo completo de n vértices. Un Kn, es decir, grafo completo de n vértices tiene exactamente 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 bipartidos.- Un grafo G es bipartido si puede expresarse como G = {V1 U V2, A} (es decir, susvé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 elementosdiferentes, como aquellos resultantes de los ejercicios y puzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.


Grafos Planos.- Un grafo G es planar 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...