Grafo

En matemáticas e ciencias da computación, un grafo^[1] (do grego grafos: debuxo, imaxe) ou gráfica é o principal obxecto de estudo da teoría de grafos. Informalmente, un grafo é un conxunto de obxectos chamados vértices ou nós unidos por enlaces chamados arestas ou arcos, que permiten representar relacións binarias entre elementos dun conxunto.

Tipicamente, un grafo represéntase graficamente como un conxunto de puntos (vértices ou nodos) unidos por liñas (arestas).

Dende un punto de vista práctico, os grafos permiten estudar as interrelacións entre unidades que interactúan as unhas coas outras. Por exemplo, unha rede de computadoras pódese representar e estudar mediante un grafo, no que os vértices representan terminais e as arestas representan conexións (que á súa vez, poden ser cables ou conexións inalámbricas).

Practicamente calquera problema pode ser representado mediante un grafo, e o seu estudo transcende a diversas áreas das ciencias exactas e das ciencias sociais.

• Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). Nova York: Dover Publications. ISBN 978-0-486-67870-2. Consultado o 8-8-2012. 

• Graph en MathWorld