Etica

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, um de 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 outra extremidade 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 alguns pontos.

[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ó como cabeç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 entrada