Grafo simple. Grafo sin bucles en el que no hay dos aristas que unan el mismo par de vértices.
GD simple. Si no tiene bucles y no hay dos arcos uniendo el mismo par.
Si un grafo no es simple, es multigrafo.
GND completo. Si hay al menos una arista (arco) uniendo cada par de vértices distintos (no tiene bucle).
Llamamos Kn al grafo completo no dirigido y simple con n vértices.
Ejemplo:
Grafo dirigido completo no simple :::::::::::::::::: Grafo no dirigido completo simple (Kn)
Para Kn = (A) = n (n-1)/2
GND, G = (V,A) es bipartido si existe una partición de V formada por V1, V2:
– V1 u V2 = V
– V1 ^ V2 = 0
– Para toda arista {vi, vj} e A, vi e V1, vj e V2
¿Es bipartido? Si; V1 = {2, 5}; V2 = {0, 1, 3, 4, 6, 7}
Grafo Bipartido. Cuyos vértices se pueden separar en dos subconjuntos disjuntos V1(G) y V2(G) y las líneas siempre unen vértices de un subconjunto con vértices de otro subconjunto.
Un grafo dirigido es bipartido si lo es su grafo no dirigido asociado.