Grafos

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

File:6n-graf.svg
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

Links

http://en.wikipedia.org/wiki/Graph_theory

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.