Grafo

As sete pontes de Königsberg coas que se exemplificou o primeiro problema de grafos da historia.

En matemáticas e ciencias da computación, un grafo (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.

Características

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.

Véxase tamén

Bibliografía

• 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. 

Ligazóns externas

• Graph en MathWorld