GRAFOS DIRIGIDOS Y NO DIRIGIDOS

No dirigidos:

Un grafo no dirigido  o grafo propiamente dicho es un grafo G = (V,E) donde:

• V  ≠ Ø
•  es un conjunto de pares no ordenados de elementos de V

Un par de ordenado es un conjunto de la forma (a,b) de manera que (a,b)=(b,a). para los grafos estos conjuntos pertenecen al conjunto potencia de V de cardinalidad 2 el cual se denota por P(V).

 

Dirigido:

Un grafo dirigido o digrafo es un grafo G=(V,E) donde:

• V≠Ø
•  es un conjuntode pares ordenados de elementos de V.

Dada una arista (a,b) a es un nodo inicial y b su nodo final.

Por definicion, los grafos dirigidos no contienen bucles .

Un grafo mixto es aquel que define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son caos particulares de este.

 

Grafos particulares

• Grafo nulo: Es aquel que no tiene vertices y aristas. Nótese que algunas personas exigen que el conjunto de vertices no sea vacío en la definición de grafo.

• Grafo vacío: Aquel que no tiene aristas.

 

• Grafo trival: Aquel que tiene una vertice y ninguna arista.

• Grafo simple: Aquel que no posee bucles o lazos.

• Grafo completo: Grafo simple en el que cada par de vertices estan unidos por una arista, es decir, contiene todas las posibles aristas.

 

• Grafo bipartito completo: Sea (W,X) una particion  del conjuntode vertices V, es aque donde cada vertice en W es adyacente sólo a cada vertice en X, y viceversa.

 

• Grafo bipartito: Sea (W,X) una particion del conjunto de vertices V, es aquel dende cada aristas tienen un vertice en W y otro en x.

• Grafo plano: Aquel que puede ser dibujado en el plano carteciano sin curce de aristas.

 

• Árbol: Grafo conexo sin ciclos.