Desenhe as versões não orientadas e orientadas do grafo G(V, E), onde V=1,2,3,4,5,6 e E=(2,5),(6,1),(5,3),(2,3).

Passo 1

O enunciado define um grafo G com o conjunto de vértices V=1,2,3,4,5,6 e o conjunto de arestas/arcos E=(2,5),(6,1),(5,3),(2,3). O conteúdo é representação gráfica de grafos simples não orientados e orientados, e vamos precisar usar a definição de aresta sem direção e arco com direção para desenhar as duas versões.

Passo 2

Para obter o grafo não orientado, cada par (u,v)in E vira uma aresta sem sentido ligando u e v. Note que o vértice 4 não aparece em nenhuma aresta, portanto fica isolado.

Passo 3

Para obter o grafo orientado, cada par (u,v)in E vira um arco direcionado de u para v. Novamente, o vértice 4 fica sem arcos incidentes.

Resposta

Versão não orientada (arestas sem direção):
1: {6}
2: {3,5}
3: {2,5}
4: {}
5: {2,3}
6: {1}
Versão orientada (arcos direcionados):
1: {}
2: {5,3}
3: {}
4: {}
5: {3}
6: {1}

Exercícios relacionados