Login Registre-se

Home > Artigos > Algoritmos e Técnicas de Programação >

[GRAFOS] 02. Conceito de Grafos

Publicado por FilipeNevola em 16/08/2009 - 2.223 visualizações



comentários: 0

Definições Básicas
Um grafo é um tipo especial de digrafo, também conhecido como grafo não-dirigido e grafo não-orientado. Um grafo é um digrafo simétrico. Os arcos de um grafo andam aos pares: cada arco v-w é acompanhado do arco w-v.

Convém tratar esse par de arcos com distinção. Assim, diremos que um par de arcos anti-paralelos é uma aresta (= edge). As pontas dos dois arcos são as pontas da aresta. As duas pontas de uma aresta são indistinguíveis: não há ponta inicial nem ponta final.

Uma aresta com pontas v e w será denotada, indiferentemente, por v-w ou w-v.
Diremos que uma aresta v-w liga os vértices v e w. Diremos também que v-w incide em v e em w. O número de arestas de um grafo é a metade do seu número de arcos. Se E denota o número de arestas e A denota o número de arcos então A = 2•E.
0
Graus de vértices
O grau de um vértice em um grafo é o número de arestas que incidem no vértice. Esse número é igual ao grau de entrada do vértice e também ao grau de saída do vértice.

É fácil verificar que a soma dos graus de todos os vértices de um grafo vale 2E, sendo E o número de arestas. Portanto, o grau médio do grafo é o número 2E/V , sendo V o número de vértices.

Convém lembrar que um vértice é isolado se o seu grau é nulo.

Número Máximo de Arestas
Quantas arestas, no máximo, tem um grafo com V vértices? Não é difícil verificar que a resposta é V•(V-1)/2. Esse número é pouco menor que ½ V^2.

Um grafo é completo se todo par não-ordenado de vértices distintos é um aresta. Um grafo completo com V vértices tem exatamente V•(V-1)/2 arestas.

Referência: IME

Continue em nosso conteúdo sobre grafos

Introdução
01. Conceito de Digrafos
02. Conceito de Grafos <- você está aqui
03. Estruturas de dados
04. Usando Matriz de Adjacências
05. Usando Lista de Adjacências

Filipe Névola
ALLgoritmos.com




comentários: 0