CARACTERIZACIÓN DE GRAFOS

Grafos Simples Un grafo es simple si a lo más sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es el único que une dos vértices específicos. Un grafo que no es simple se denomina complejo. 

Grafos Conexos Un grafo es conexo (más formalmente fuertemente conexo) si todos sus vértices están conectados por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. Es posible determinar si un grafo es fuertemente conexo coleccionando la información de los grados de sus vértices al tiempo que se acumulan las diferentes rutas que salen de un vértice o llegan a él. En términos matemáticos la propiedad de un grafo de ser fuertemente conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes fuertemente conexos", es decir, porciones del grafo, que son fuertemente conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos. 

Grafos Completos Un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.

Grafos Bipartitos Un grafo G es bipartito si puede expresarse como G = {V1 + V2, A} (es decir, la unión de dos grupos de vértices), bajo las siguientes condiciones: 

• V1 y V2 son distintos y tienen más de un elemento cada uno. 

• Una arista en A une un vértice de V1 con uno de V2. 

• No existen aristas uniendo dos elementos de V1; análogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B. 

Cibergrafia :

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0701_Tc1003_TODO_Grafos.pdf