Unidad 4: Clasificacion de Grafos

Los grafos se pueden clasificar en dos grupos:

 Dirigidos y no Dirigidos.

En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que  representan dos arcos diferentes

En un grafo no dirigido el par de vértices que representa un arco no está ordenado

TIPOS DE GRAFOS 

Grafo regular: Aquel con el mismo grado en todos los vértices

Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Grafo completo: Aquel con una arista entre cada par de vértices

Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no

están conectados, esto es, que son vértices aislado

Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia

biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan

unidos por una arista en común

      

Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro

     

Grafo conexo

Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto

de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más

claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier

par de nodos existe al menos un camino que los une” 

DÍGRAFO (GRAFO DIRIGIDO).

A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas,

como en el siguiente caso