Conforme a Wikipedia Grafos são conjuntos de objetos de um mesmo tipo que apresentação ligação entre eles. A teoria dos grafos é o campo que os estuda, sendo de grande valia à matemática e à ciência da computação. Dois conceitos fundamentais são o nodos e arestas. Nodos são os objetos representados e a aresta a ligação entre eles.
Os grafos podem ser usados para modelar diversos objetos que se relacionam entre si.
Um exemplo de grafo é um diagrama da UML onde há símbolos que representam determinado conceito e linhas, as quais ligam dois objetos e descrevem a relação dos objetos a que estão ligadas.
Outro exemplo é o diagrama de uma competição mata a mata, aonde os nodos são as equipes e as linhas determinam as partidas a serem realizadas para a eliminação.
Um desenho básico de grafo pode ser visto abaixo
Fonte: http://en.wikipedia.org/wiki/Graph_theory
Definição matemática
A definição matemática de um grafo é bem simples:
G = {V, E}
Gé a estrutura do grafo em si
V é o conjunto de vértices, isto é objetos/nodos de um grafo.
E é o conjunto de arestas do grafo, sendo que cada aresta representa uma relação entre dois vértices, isto é Ex = Vi -> Vj
Algoritmos sobre grafos
Caminho Euleriano
Dijkstra
Prim
Kruskal
