Teoría de la gráfica

Una gráfica es un conjunto de objetos llamados vértices (o nodos) conectados por líneas llamados bordes .

Una gráfica sencilla finita es una pareja ordenada G = [ V , E ] , donde V es un conjunto finito de vértices o nodos y cada elemento de E es un subconjunto de 2 elementos de V. Típicamente, una gráfica se define como un conjunto de puntos (los vértices) conectados por líneas (los bordes).

El orden de una gráfica es | V | (el número de vértices). El tamaño de una gráfica es | E | , el número de bordes. El grado de un vértice es el número de bordes que se conectan entre si.

En la gráfica anterior, el conjunto de vértices son y el conjunto de bordes son .

El orden de la gráfica es . El tamaño de la gráfica es .

El número de bordes que conectan con el vértice u son 2 y por lo tanto el grado del vértice u es 2.