TIPOS DE GRAFOS

GRAFICA NO DIRIGIDA:

Son aquellos en los cuales los lados no están orientados (no son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (vi, vj) = (vj, vi)

La gráfica (o grafos no dirigidos) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e € pertenece se asocia con un par no ordenado de vértices. Si existe una arista única e asociada con los vértices v y w se escribe e = (v, w) o e = (w, v). En este contexto (v, w) en una gráfica no dirigida y no es un par ordenado.

GRAFICA DIRIGIDA:

Son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <vi, vj> = <vj, vi>. En grafos dirigidos, para cada lado <a, b>, a, el cual es el vértice origen, se conoce como la cola del lado y b, el cual es el vértice destino, se conoce como cabeza del lado.

Un gráfica dirigida (o dígráfica)  G consisten en un conjunto V vértices (o nodos) y u conjunto de vértices. Si hay una arista (o arcos) tales que cada arista e € está asociada con un par ordenado de vértices. Si hay una arista única e asociada con el par ordenado (v, w) de vértces, se escribe e = (v, w) que denota una arista v a w.

GRAFO SIMPLE:

Es un par G = (V; E) donde V es un conjunto _nito no vació de elementos llamados vértices y E es un conjunto de pares no ordenados de elementos distintos de V llamados aristas.

GRAFO COMPLETO DE n VÉRTICES (Kn):

Es el grafo en donde cada vértice está relacionado con todos los demás, sin lazos ni lados paralelos. Se indica como Kn, en donde n es el número de vértices del grafo.

GRAFO COMPLETO:

Un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo completo de n vértices tiene n(n-1) / 2 aristas, y se nota Kn. Es un grafo regular con todos sus vértices de grado n-1. Ningún grafo completo tiene lazos y está conectado totalmente, por ende, la única forma de hacer disconexo el grafo con una eliminación de vértices es aplicarla a todos.

GRAFOS BIPARTIDOS:

Es un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen un vértices de un conjunto con vértices de columnas (o filas) diferentes.

Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U azul y los vértices de V de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.

Un grafo bipartito suele con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| = |V|, esto es, si los dos subconjuntos tiene la misma cantidad de elementos, decimos que el grafo bipartito G es balanceado.

GRAFOS PLANOS:

Un grafo es plano si, y solo si, no contiene ningún subgrafo isomorfo a K5 ni a K3, 3, ni a subdivisiones de ellos.

Un grafo o es plano si no puede ser dibujado sobre un plano sin que sus aristas se intersequen. Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.

GRAFOS CONEXOS:

En matemáticas y ciencias de la computación es aquel grafo que entre cualquier par de sus vértices existe un Camino (Grafo) que los une.

GRAFOS PONDERADOS:

Un grafo ponderado con pesos es un grafo G(V, E), en el que a cada arista se le asigna un valor real no negativo o peso. Sobre el conjunto de aristas se introduce una función peso. El peso de un subgrafo de un grafo ponderado es la suma de los pesos de todas sus aristas.

REFERENCIAS:

Chirinos, N. (14 de Noviembre de 2010). Teoria de Grafos. Conceptos básicos. Obtenido de SlideShare.net: http://es.slideshare.net/naborchirinos/conceptos-teoria-de-grafos-5778778

Murillo, J. A. (s.f.). Matemáticas para la computación. México: Alfaomega Grupo Editor, S. A. de C. V., México.

Toledo, I. (11 de Octubre de 2012). Teoria de Grafos. Obtenido de SlideShare.net: http://es.slideshare.net/isaiastoledo7/teora-de-grafos-14694334