Etica

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1370 palavras )
  • Download(s) : 0
  • Publicado : 25 de setembro de 2012
Ler documento completo
Amostra do texto
Conteúdo da aula: Grafo – Conceitos
Livro Tenembaum pág.664. Livro Veloso pág. 156


Grafos

A organização de dados na memória de forma a refletir os relacionamentos entre esses dados são estruturas que denominamos de Grafos

1 Conceito

Grafos refletem estudos apontados até hoje por Mestre, dado a sua complexidade e profundidade.

Grafo é um objeto formado por dois conjuntos, umde vértices e um de arcos (usa-se o termo aresta somente no caso de grafos não orientados).
Cada arco num grafo é representado por um par de nós. Se os pares de nós que formam os arcos forem pares ordenados, este grafo é conhecido como grafo ordenado (ou dígrafo). A setas entre os nós representam os arcos, onde a ponta de cada seta representa o segundo elemento do par ordenado e a outraextremidade da seta representa o primeiro nó do par ordenado.

[pic]
Lembre-se que um grafo é a representação de um conjunto de vértices e arcos, portanto a representação do grafo acima é o seguinte conjunto: {, , , , , , }.
Observação importante: Um grafo não precisa ser uma árvore, mas uma árvore tem de ser um grafo.

Daremos alguns nomes para ilustrar as arestas do grafo acima para analisar algunspontos.

[pic]


Dado o grafo acima, destacaremos apenas o nó C.
O nó C incide nos arcos M, P e Q porque os pares ordenados dessas arestas constituem o nó C. Dizemos também que as arestas M, P e Q incidem no nó C.
O grau de um nó é o número de arcos incidentes neste nó. Em nosso caso o nó C tem grau igual a 3.
O grau de entrada de um nó é definido pelo número de arcos que tem o nó comocabeça. Em nosso caso o nó C tem grau de entrada igual a 2.
O grau de saída de um Nó é definido pelo número de arcos que tem o nó com terminação da seta. Em nosso caso o nó C tem grau de saída igual a 1.

Exemplo para fixação

[pic]
Para todos os grafos, o grau de um vértice é o número de arestas incidentes no vértice.
Para os grafos orientados, além do grau do vértice, temos o grau de entradae o grau de saída de cada Nó.
Responda:
Grau de entrada do vértice 2 é 1.
Grau de saída do vértice 2 é 2.
Grau do vértice 2 é 3.

Caminho de um grafo também faz parte de seus conceitos, ou seja, ao percorrer os nós de um grafo o caminho entre o vértice u e v de um grafo G é uma seqüência:
u, i1, i2, ... , ik, v tal que
• (u,i1), (i1,i2),..., (ik,v) são arestas em E(G), se G for nãoorientado.
• ,,..., são arestas em E(G), se G for orientado.

Mais adiante será discutido o percurso de um grafo.



2 Representações de Grafos


Matriz de Adjacências
Matriz de adjacência é definida como uma matriz quadrada de ordem n, onde n corresponde ao número de vértices de uma grafo. Em geral os valores da matriz de adjacência são lógicos (verdadeiro ou falso), ou seja, Vsinaliza a existência de uma aresta entre os vértices.

[pic]
Com o grafo acima temos a seguinte matriz de adjacência definida abaixo, onde zero representa o valor falso e 1 o valor verdadeiro.

|Nós |Colunas |
|Linhas ||
|Linhas | |
|Linhas | |
|Linhas| |
|Interseções entre ruas |Segmento de ruas |
|Bairros e Vilas |Estradas |
|Cidades...
tracking img