Post original (mi blog de m1) aquí.
Con cierto retraso, voy a pasar a la segunda parte de la asignatura M1: Los Grafos.
Un grafo G es un par formado por un conjunto de vértices (V) y un conjunto de aristas/arcos (A). Diremos que:
- G = (V,A) NO DIRIGIDO, donde V es un conjunto de vértices, y A una familia de pares no ordenados de vértices, llamados aristas.
- G = (V,A) DIRIGIDO, donde V es un conjunto de vértices, y A una familia de pares ordenados de vértices, llamados arcos.
Con estas definiciones, llamaremos grafo NO DIRIGIDO ASOCIADO a un grafo dirigido, a aquel con el mismo conjunto de vértices, y en el que se han ignorado las direcciones de los arcos.
Ahora, unas cuantas más definiciones:
- Grafo mixto: tiene tanto arcos como aristas.
- Los extremos de una arista/arco (vértices) son incidentes con la arista/arco.
- Dos vértices con una misma arista/arco son adyacentes.
- Un bucle es una arista/arco cuyos extremos son el mismo vértice.
Tipos particulares de grafos:
- Grafo simple es aquel que no hay dos aristas/arcos(con la misma dirección) uniendo el mismo par de vértices, y no tiene bucles.
- Multigrafo es el caso contrario al grafo simple.
- Grafo completo es aquel que tiene al menos una arista/arco uniendo cada par de vértices. Llamaremos Kn al grafo completo, no dirigido y simple.
- Grafo bipartido es aquel que tiene una bipartición {X,Y} del conjunto V de forma que toda arista tiene un extremo en X y otro en Y, y los vértices de una misma bipartición no tienen aristas que los una. Un grafo dirigido es bipartido si lo es su grafo no dirigido asociado.
Siendo G = (V,A), se tiene el teorema:
- ΣdG(v) = 2card(A). -> El sumatorio de los grados de los vértices de un grafo no dirigido es igual a dos veces el cardinal del conjunto de aristas A.
- Σde(v) = Σds(v) = card(A). -> El sumatorio de los grados de entrada de los vértices de un grafo dirigido es igual al sumatorio de los grados de salida de los mismos vértices, que es igual al cardinal del conjunto de aristas A.
Y para finalizar, un corolario:
El número de vértices de grado impar de un grafo es par.
En el próximo post se hablará de las cadenas de los grafos.