Grafos

Grafos simples
Un grafo es simple si sólo 1 arista une 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 noes simple se denomina Multigráfica o Gráfo múltiple.
Grafo completo
En en el campo de la teoría de grafos, un grafo completo es aquél donde todas sus aristas conectan cada par de vértices. El grafocompleto de n vértices tiene n vértices y 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.
El teorema de Kuratowski dice que un grafo planar no puede contener K5 (ó el grafobipartito completo K3,3) y todo Kn incluye a Kn − 1, entonces ningún grafo completo Kn con es planar
Los grafos completos de n vértices, para n entre 1 y 8 son estos:
K1 | K2 | K3 | K4 |
K5 | K6 | K7 ||

Grafo complemento

Un grafo de Petersen (a la izquierda) y su grafo complemento (a la derecha).
En teoría de grafos, el complemento o inverso de un grafo G:=(V,E) es un grafo G':=(V,E'), conel mismo conjunto de vértices y tal que dos vértices de G' son adyacentes si y sólo si no son adyacentes en G. Para obtener el complemento de un grafo, se deben completar todas las aristas faltantespara hacerlo completo, y quitar todas las aristas del grafo G original. Este concepto no debe confundirse con el del complemento de un conjunto, pues sólo se complementan las aristas.
Se llama grafoautocomplementario a aquél que es isomorfo a su propio complemento.
Grafo bipartito

Ejemplo de grafo bipartito.
Un Grafo bipartito se denomina en Teoría de grafos a un grafo no dirigido cuyosvértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen vértices de un conjunto con vértices de otro:
*
*
* no existe ninguna arista e = x1,x2 ni e = y1,y2...