Como se sabe, un grafo consiste de vértices y aristas, donde éstas se pueden ver como pares de vértices. El conjunto de vértices suele denotarse con y el de aristas con --y el grafo con G(V,E).
Una de las dificultades de aprendizaje que presenta la teoría de grafos es su extensa terminología. Para superar esa dificultad sugiero aprender los conceptos en bloques.
(El término valencia es posiblemente más adecuado, si uno recuerda su curso de química --la valencia es el "poder combinante de un elemento". Porque las aristas incidentes en el vértice "combinan" a éste con los vértices que son el otro extremo de esas aristas.) Esta definición nos permite presentar un teorema, elemental pero importante.
Teorema de la relación entre valencias y vértices
Demostración
Primero observemos que por cada vértice v hay g(v) aristas, y por cada arista hay dos vértices. Vamos a contar de dos formas (doble conteo) las parejas (vértice, arista incidente).
La primera forma consiste en recorrer los vértices y enumerar, para cada uno, sus aristas incidentes. Por ejemplo, al llegar al vértice , enumeramos las aristas incidentes, digamos, ak1,ak2,…,ag(vk). Al final del recorrido se tiene una lista de ∑v∈Vg(v) parejas, es decir, el lado izquierdo de la fórmula.
La segunda forma es recorrer las aristas y enumerar, para cada una, sus vértices extremos. Por ejemplo, al llegar a la arista aj enumeramos sus vértices extremos, digamos vaj1 y vaj2.
Al final del recorrido, se tiene una lista de parejas.
Comentarios
Publicar un comentario