Estructura de Datos : Tipos De Grafos

Tipos De Grafos

Grafos dirigidos

Los grafos dirigidos son grafos en los que las aristas tienen una dirección definida; por ejemplo, se puede dar el caso de poder ir del nodo A al nodo B, pero no al revés. En la mayoría de los casos la dirección de las aristas indica algún tipo de relación de precedencia entre los nodos. Los grafos dirigidos pueden ser usados para:

• Modelar líneas de fabricación, en las que diferentes procesos dependen de otros

• Manejar dependencias en la compilación de archivos, como hace el make

Podemos ver claramente que por ejemplo, existe una arista de A a G, pero no de G a A. Sin embargo, está permitido que halla dos aristas de direcciones distintas entre los mismos nodos, como por ejemplo entre H e I, y entre L y M.

Búsqueda primero en profundidad

En el caso de grafos dirigidos, la búsqueda primero en profundidad es casi igual a la similar en el caso de grafos no dirigidos.

Grafos regulares

Los grafos son esquemas matemáticos, formados por una serie de puntos llamados vértices o nudos y unos segmentos que los unen llamados aristas.

En esta página haremos el estudio matemático de las posiciones de un rompecabezas, representaremos todas esas posiciones en forma de grafo, ello nos llevará a descubrir un concepto matemático nuevo, se trata de los grafos regulares, de cuyos vértices salen tres aristas.

Grafo Bipartido

Dícese de todo grafo simple sin lazos cuyo conjunto de vértices puede dividirse en dos subconjuntos disjuntos no vacíos de manera que los vértices que los componen solo tengan aristas o arcos con vértices del otro subconjunto, nunca con ningún vértice del mismo conjunto.

Definición.

Un grafo G=<V,A> se dice bipartido o bipartito si y solo si existe una partición de V=V1 U V2 tal que para toda arista (x,y) de A se cumple que x es un vertice de V1 e y está en V2 o simplemente que A será un subconjunto no nulo de V1xV2.

Cuando A=V1xV2 se dice que el grafo es bipartido completo.

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo 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 de 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 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 o cardinalidad, decimos que el grafo bipartito G es balanceado.