Embedded Files
Pero, ¿solo hay un tipo de grafo? Como te estarás imaginando, no. Hay cantidades de tipos de grafos diferentes, y ahora vamos a intentar explicar los más importantes, conocidos y utilizados.
Grafo trivial
Grafo trivial
Es el grafo más simple que se puede considerar, ya que no tiene aristas; es un conjunto de vértices sin ninguna relación entre ellos. Se les llama grafos triviales precisamente por ser grafos muy simples que no tienen ninguna arista. No son más que puntos aislados.
Imagen de un grafo trivial
Grafo Camino
Grafo Camino
Este es otro grafo muy sencillo, que, como su nombre indica, representa un camino de aristas que une a los vértices. A los grafos camino los llamamos Pn, donde n es el número de aristas del camino.
P6 Grafo camino de orden 6
Grafo ciclo
Grafo ciclo
Es otro grafo también muy simple, en el cuál los vértices se unen formando un ciclo. Los llamamos Cn, donde n representa al número de vértices del mismo.
Ciclo C6
Grafo regular
Grafo regular
Los grafos regulares son aquellos en los que todos los vértices tienen la misma valencia, por ejemplo los ciclos, el grafo de Petersen o los grafos completos.
Grafo de Petersen
Grafo de Petersen
El grafo de Petersen no es un tipo de grafo como tal, pero se trata de un grafo regular de valencia 3 y fue construido en 1898 por el matemático danés Julius Petersen, quién le da nombre. Este grafo tiene propiedades muy interesantes. El matemático estadounidense Donald Knuth, célebre por sus libros en programación, dice de este grafo que es "una configuración notable que sirve como contraejemplo a muchas predicciones optimistas sobre qué podría ser cierto en un grafo en general". El grafo de Petersen es comúnmente dibujado como un pentágono con una estrella de 5 puntas dentro.
Grafo de Petersen
Grafo completo
Grafo completo
Los grafos completos son aquellos grafos regulares de n vértices en los que todos los vértices tienen valencia máxima, es decir, valencia n-1 (los grafos de n vértices en los que todos los vértices están unidos con todos los demás).
¿Por qué a los grafos completos los designamos con la letra K? Pues no está muy claro. Algunas fuentes aseguran que se adoptó esta letra por la palabra alemana komplett (ya que la C de complete, en inglés, ya se utiliza para los ciclos). Pero en alemán al grafo completo se le llama vollständiger graph, sin ninguna K. Otras fuentes aseguran que la K de los grafos completos es un homenaje a Kazimierz Kuratowski, matemático polaco que demostró uno de los teoremas (en Teoría de Grafos) más citados en la historia de las matemáticas. Y otros muchos piensan que es simplemente que al estar la C cogida para los ciclos, simplemente por fonética ya que la C suena fonéticamente igual (o muy parecida) a la K.
K7, grafo completo de 7 vértices.
Grafo bipartito
Grafo bipartito
En estos grafos los vértices están divididos en dos subconjuntos, de tal forma que los vértices de cada subconjunto no pueden estar unidos entre ellos.
Dentro de los grafos bipartitos también los tenemos completos. Un grafo bipartito de n vértices es uno de los subconjuntos y m vértices en el otro es un grafo bipartito en el que todos los vértices tienen valencia máxima (todos los vértices del primer subconjunto están unidos a todos los del segundo). Al grafo bipartito completo de n vértices en uno de los subconjuntos y m vértices en el otro lo llamamos Kn,m.
Estos grafos, los bipartitos, tienen infinidad de aplicaciones prácticas en problemas de asignación.
Un grafo bipartito completo con m = 5 y n = 3
Como es obvio hay muchísimos grafos más, pero estos son los que más nos interesan para este trabajo, ya que son los más conocidos y utilizados.
Page updated
Report abuse