Os Sistemas de Informação

Universidade do Sul de Santa Catarina - UNISUL – Campus: Grande Florianópolis
Curso: Sistemas de Informação – Unidade Dib Mussi

Disciplina: Programação Linear e Grafos

Prof. Fernanda – Folha 1 – 2015-B (Conceitos, tipos de grafos e representação de grafos)

1. Dado o grafo da figura: a. Identificar os vértices adjacentes; b. Calcular o grau de cada vértice; c. Identificar vértices isolados e pendentes; d. Desenhe um laço que incida no vértice V2; e. Identifique arestas incidentes no vértice V1; f. Identifica as arestas paralelas; g. Represente o grafo da figura através dos conjuntos de vértices e arestas;

[pic 1]

2. Desenhe os seguintes grafos:

a. Grafo regular e simples de ordem 5;

b. Grafo completo de ordem 5;

c. O sub-grafo do grafo do exercício 1, excluindo o vértice V5;

d. O grafo parcial do grafo do exercício 1, excluindo a aresta (V2,V3) e (V1,V5);

e. Grafo bipartido com 4 vértices no conjunto de vértices V1, 3 vértices

    no conjunto V2 e 7 arestas;

 

3. Dada a matriz de adjacência de um grafo responder: O grafo representado é orientado? O grafo possui laços? Qual é o grau de cada vértice? Desenhar o grafo.

V1 V2 V3 V4 V5 V1 0 1 1 0 1 V2 1 0 1 0 1 V3 1 1 0 1 0 V4 0 0 1 1 0 V5 1 1 0 0 0

4. Dada a matriz de incidência de um grafo responder: O grafo representado é orientado? O grafo possui laços? Qual é o grau de cada vértice? Desenhar o grafo.

E1 E2 E3 E4 E5 E6 V1 1 0 0 0 0 1 V2 0 1 1 0 0 0 V3 1 1 0 1 0 0 V4 0 0 1 1 0 0 V5 0 0 0 0 1 1

5. Dado um grafo representado por sua matriz de adjacência, responder sem desenhar o grafo: Qual é o número de arestas do grafo; Qual é o grau dos vértices do grafo; Construir a matriz de incidência; Representar o grafo com a notação da teoria dos conjuntos; Desenhar o grafo.

V1 V2 V3 V4 V5 V1 0 1 1 0 1 V2 0 0 0 1 0 V3 0 1 0 0 1 V4 1 0 1 0 0 V5 1 0 0 1 0

...