Login Registre-se

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

[GRAFOS] 01. Conceito de Digrafos

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



comentários: 0

Definições Básicas

Um digrafo (= um grafo direcionado) consiste em dois conjuntos: um conjunto vértices e outro de arcos. Cada arco é um par ordenado de vértices. O primeiro vértice é o início e o segundo é o fim do arco.

Um arco com início em v e final em w será denotado por v-w (isto não é uma subtração). Existir um arco que liga o vértice v ao vértice w não significa que existe um arco que liga o vértice w ao vértice v.

Se v-w existe então dizemos que w é vizinho (ou adjacente) de v.

Digrafos simétricos

Um digrafo é simétrico se cada um de seus arcos é anti-paralelo* a algum outro arco.
*arcos anti-paralelos: Para um arco v-w temos também um arco w-v, estes dois arcos são anti-paralelos.

Grau de entrada e de saída

O grau de saída de um vértice v em um digrafo é o número de arcos que começam em v. O grau de entrada de um vértice v em um dígrafo é o número de arcos que terminam em v.

Uma fonte é um vértice que tem grau de entrada nulo (= 0) e um sorvedouro é um vértice que tem grau de saída nulo (= 0).

Um vértice é isolado se seu grau de entrada e seu grau de saída são ambos nulos.
0
Número de arcos

Qual máximo de arcos em um dígrafo de V vértices? Não é difícil verificar que a resposta a essa pergunta é o produto V•(V-1). Para valores grandes de V, esse número é apenas um pouco menor que V^2.
0
Um digrafo é completo se todo par ordenado de vértices distintos tem um arco entre eles (Sendo A número de arcos e V número de vértices, para um dígrafo completo: A = V•[V-1]).

Um digrafo é denso se o seu número de arcos é proporcional ao quadrado do número de vértices.

Um digrafo é esparso se for o complemento de um digrafo denso, ou seja, se o número de pares ordenados de vértices que não são arcos for proporcional ao quadrado do número de vértices.

Referência: IME

Continue em nosso conteúdo sobre grafos

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

Filipe Névola
ALLgoritmos.com


Download:  digrafo02.jpg
Size:  8 KB

Download:  digrafo01.jpg
Size:  3 KB



comentários: 0