Componente de un Grafo

PARTES DE UN GRAFO

Un grafo (G) es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L).

Considérese el siguiente grafo:

A partir de esta figura se definen los siguientes elementos:

Vértices (nodos)
Se indican por medio de un pequeño círculo y se les asigna un número o letra. En el grafo anterior los vértices son V= {a,b,c,d}.

Lados (ramas o aristas)
Son las líneas que unen un vértice con otro y se les asigna una letra, un numero o una combinación de ambos. En el grafo anterior los lados son: L= {1, 2, 3, 4, 5, 6}.

Lados paralelos
Son aquellas aristas que tienen relación con un mismo par de vértices. En el grafo anterior los lados paralelos son: P={2,3}.

Lazo
Es aquella arista que sale de un vértice y regresa al mismo vértice. En el grafo anterior se tiene el lazo: A= {6}

Valencia de un vértice
Es el numero de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:

Valencia (a)=2
Valencia (b)=4
Valencia (c)=2
Valencia (d)=3

Hay que observar como en el caso del vértice del lazo solo se considera una vez, entrada o salida pero no ambos.