Grafos

Universidade Federal do Triângulo Mineiro Instituto de Ciências Tecnológicas e Exatas Departamento de Engenharia Mecânica

TEORIA DOS GRAFOS

Fagner Passarelli Lourenço Camila Fernanda A. Vieira

Novembro 2011

TEORIA DOS GRAFOS
Definição: Um grafo é uma estrutura de abstração que representa um conjunto de elementos denominados nós e suas relações de interdependência arestas. Representação Matemática: Denominando por V o conjunto de vértices da estrutura, e por A o conjunto das arestas ou ligações entre os vértices, um grafo pode ser representado por: G = (V,A). Um grafo nada mais é do que uma representação gráfica da interdependência entre elementos. Elementos estes, que são representados por nós, também chamados de vértices, como na figura abaixo:

Apesar de a figura acima já o ser, um grafo é mais comumente representado da seguinte forma:

Grafo ponderado: Um grafo G = (V,A) é ponderado se existem valores numéricos associados a suas arestas ou nós.

Grafos ponderados normalmente são utilizados para representar mapas, por exemplo. Nos mapas, as ponderações associadas às arestas podem ser as distancias entre um local e outro (um vértice desse grafo e outro).

Grafo rotulado: Definição: Um grafo valorado G = (V,A) tal que, para qualquer a número real c(a) associado. A, existe um

Essas atribuições são frequentemente referidas como o peso da ligação. Essa classificação é dada de acordo com a necessidade, ou não, da indicação do fluxo entre os vértices. Na prática este número pode representar: - custos, distâncias, capacidades, e/ou suprimentos e demandas; - tempo (trânsito, permanência, etc); - confiabilidade de transmissão; - probabilidade de ocorrer falhas; - capacidade de carga; - outros.

Multigrafo: Definição: Um grafo G = (V,A) é um multigrafo se existem mais de uma aresta ligando o mesmo par de vértices. Multigrafos podem ser usados, por exemplo, pra modelar as possíveis conexões de vôo oferecidas por uma linha aérea.

Grafo