Estatistica

Grafos Direcionados e Relações Binárias Suponha que G é um grafo direcionado com n vértices e sem arestas paralelas. Seja N o conjunto de vértices. Se (ni,nj) é um par ordenado de vértice, então existe ou não uma aresta entre os vértices ni e nj . Podemos usar esta propriedade para definir uma relação binária no conjunto N: ni ρ nj ↔ existe uma aresta G de ni para nj Esta é a relação de adjacência do grafo. Exemplo 1: Para o grafo direcionado abaixo, a relação de adjacência é { (1,2), (1,3), (3,3), (4,1), (4,2), (4,3)}.
1 2

3 4

Observação: Em um grafo direcionado, duas arestas do vértice a para o vértice b são paralelas, mas uma aresta do vértice a para o vértice b e outra do vértice b para o vértice a não são paralelas. Exemplo 2: Para o conjunto N = {1, 2, 3, 4} e relação binária {(1,4), (2,3), (2,4), (4, 1)} em N, obtemos o grafo direcionado abaixo.
1 4

2

3

Exercícios 1. Encontre a matriz de adjacência e a relação de adjacência para o grafo da figura dada.
a) 1 b) 1 3

2

3

2

4

2. Dada a relação de adjacência ρ = { (1, 4), (1, 5), (1, 6), (6, 2), (6, 3), (6, 5)} no conjunto N = {1, 2, 3, 4, 5, 6}, encontre o grafo direcionado e a matriz de adjacência associados. 3. Dada a relação de adjacência ρ = { (2, 1), (3, 2), (3, 3), (3, 4), (4, 5), (6,3), (6,6)} no conjunto N = {1, 2, 3, 4, 5, 6}, encontre o grafo direcionado e a matriz de adjacência associados.

1

a)

4. Encontre o grafo direcionado e a relação de adjacência equivalente à matriz a seguir: b) 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 A= 0 0 0 0 0 A= 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 5. Os dois grafos direcionados da figura dada têm relações de adjacência ρ e σ. Desenhe os grafos associados às relações ρ ∪ σ e ρ ∩ σ .
1

1

2

3

2

3

Alcançabilidade Definição: Vértice alcançável Em um grafo direcionado, o vértice nj é alcançável a partir do vértice ni se existir um caminho de nj ate ni No grafo do abaixo, o vértice 3 não é alcançável a