Conceptos básicos
En esta entrada empezaremos con una breve introducción a los grafos para describir aquellos conceptos que son necesarios para introducirse en el tema de los grafos.
Un grafo es una entidad matemática que relaciona unos objetos denominados vértices mediante aristas.
Matemáticamente un grafo G, consta de un conjunto de vértices V y un conjunto de pares A o aristas que conectan estos vértices.
Dado un grafo G y dos vértices u, v se dice que son adyacentes si los une una arista designada como uv. Dadas estas relaciones entre los vértices se puede definir la matriz de adyacencias como todas las relaciones directas entre vértices. En el grafo anterior el vértice 1 tiene relación con 2 y 4. Esta adyacencia se nota con un 1 en la matriz como representación de su unión.
Se define orden, n de un grafo como la cantidad de vértices que tiene.
Se define tamaño, m o medida de un grafo el número de aristas que posee y que relacionan los vértices entre ellos.
El número máximo de aristas que puede tener un grafo se calcula mediante la siguiente expresión:
n.(n-1)/2
Para el grafo representado anteriormente, al disponer de 5 vértices, el número máximo de arista que puede tener es de 5.4/2, es decir, 10, pero en este caso sólo dispone de 6 aristas.
El grado de un vértice v, g(v), se define como el número de aristas que inciden en él.
Os adjuntamos el enlace con el vídeo de esta introducción a los grafos y que tenéis disponible en youtube: https://youtu.be/Ybwys7rP1Xk
Puedes visitar nuestra web para nuevas entradas y/o solicitar clases de apoyo para esta u otras asignaturas.