Modelos de Grafos

Definições Básicas

Grafo – Um grafo é um par (V, A) em que V representa o conjunto (não-vazio) dos vértices e A o conjunto das arestas, constituído por pares não ordenados de vértices.

Aresta – Uma aresta liga um vértice com outro vértice ou um vértice com ele próprio.

Lacete – É uma aresta que liga um vértice a ele próprio.

Vértice isolado – É um vértice que não tem ligação com nenhum outro vértice.

Arestas paralelas – São dois vértices ligados por mais do que uma aresta.

Grafo simples – É um grafo sem arestas paralelas nem lacetes.

  • Num grafo, dois vértices dizem-se adjacentes se tiverem uma aresta que os una.
  • Num grafo, duas arestas dizem-se adjacentes se tiverem um vértice em comum.

A Ordem de um grafo – Representa o número de vértices desse grafo.

A Dimensão de um grafo – Representa o número de arestas desse grafo.

O grau (ou valência) de um vértice – É igual ao número de arestas que começam (ou terminam) nesse vértice (o lacete conta duas vezes).

Grafo regular – É um grafo em que todos os vértices têm o mesmo grau.

  • Um grafo G é chamado de H se todo o vértice de G é vértice de H e se toda a aresta de G é aresta de H.

Grafo conexo – Um grafo é conexo se qualquer vértice estiver ligado por uma aresta ou uma sequência de arestas a qualquer um dos outros vértices.

Grafo completo – Chama-se grafo conexo a um grafo em que quaisquer dois dos seus vértices são adjacentes, isto é, há pelo menos uma aresta para cada par dos seus vértices.

Os grafos completos e simples são designados por Kn, onde n representa a ordem desse grafo.

Caminho – É uma sequência de arestas adjacentes que liga dois vértices.

Circuito – É um caminho que começa e acaba no mesmo vértice.

Comprimento de um caminho – É o número de arestas por que é constituído.

  • Um grafo diz-se pesado quando a cada aresta é atribuído um peso ou custo.

Num grafo o número de vértices de grau ímpar é par.

Em qualquer grafo, a soma dos graus de todos os vértices é igual ao dobro do número de arestas.

~ por goncasrato em 02/21/2010.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s

 
%d bloggers like this: