CARACTERIZACIÓN DE LOS GRAFOS

Un problema interesante en la teoría de grafos, que no ha sido resuelto del todo, es el referente a la búsqueda de todos los grafos simples diferentes que existen con un número determinado de vértices (caracterización de los grafos). Así, para p = 1 hay un solo grafo.

Así, para p = 1 hay un solo grafo.

Para p = 2, existen dos grafos diferentes.

Para p = 3 ya llegan a ser cuatro grafos

.

Pero para p = 4 ya nos encontramos con once grafos distintos.

Si hacemos esto para todos los grafos simples diferentes que existen con un número "p" de vértices, vemos que a medida que "p" crece el número de grafos aumenta considerablemente.

Esto es un problema muy complejo, y para que se tenga una idea, cuando p = 9, existen 274668 grafos diferentes y conviene clasificar los grafos en ciertas familias de acuerdo a algunas propiedades específicas.

• Grafos Nulos (Np), son aquellos grafos que presentan solamente vértices aislados y por lo tanto, no existe una relación R entre sus vértices, es decir, /V(G)/= p y /E(G)/= 0.
• Grafos Completos (Kp), son grafos donde cada vértice está relacionado con todos los (p-1) vértices restantes.

Si tengo "p" vértices hay p (p-1) posibles líneas. pero como el grafo es simple, cada línea se cuenta dos veces. Luego hay un total de p(p-1)/2 líneas.

Esntonces /V(Kp)/= p y /E(Kp)/= p(p -1)/2

Algunos ejemplos de los cinco primeros Kp

Por ejemplo, la familia de los Grafos Nulos (Np), considera aquellos grafos que presentan solo vértices aislados y por lo tanto, no existe una relación R entre sus vértices, es decir, /V(G)/= p y /E(G)/= 0.

En contraposición, existe la familia de los Grafos Completos (Kp), donde cada vértice está relacionado con todos los (p-1) vértices restantes. Ahora, si tengo "p" vértices hay p(p-1) posibles líneas. Sin embargo, el grafo es simple y cada línea se cuenta dos veces, luego, hay un total de p(p -1)/2 líneas, o sea, /V(Kp)/= p y /E(Kp)/= p(p-1)/2 .

Otra familia de particular interés son los llamados Ciclos, que denotaremos Cp , donde "p" es el número de vértices. Son grafos regulares de valencia 2, donde el número de líneas q = p. También son conocidos (sobre todo en geometría) como los "p-ágonos". Algunos de los grafos que forman esta familia son los siguientes:

Triángulo ------>

Cuadrado ------>

Pentágono ---->