5.11 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 que no 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 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 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 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 el plano de manera que ningún par de sus aristas se corte. A ese dibujo se le llama 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 el recorrido 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 delos pesos de las aristas de ese camino.

http://itpn.mx/recursosisc/1semestre/matematicasdiscretas/Unidad%20VI.pdf