1. Os Turistas Jensen, Leuzingner, Dufour e Medeiros se encontram em um bar de Paris e começam a conversar. As línguas disponíveis são o inglês, o francês, o português e o alemão. Jensen fala todas. Leuzingner não fala apenas o português. Dufour fala francês e alemão. Medeiros fala inglês e português. Represente por meio de um digrafo todas as possibilidades de um deles dirigir a palavra a outro, sendo compreendido.

Passo 1

A questão pede um digrafo em que há um arco de um turista A para um turista B sempre que A fala pelo menos uma língua em que B se comunica. Vamos listar o conjunto de línguas que cada um fala: Jensen fala inglês, francês, português, a<=mãoêêêã, Leuzingner fala inglês, francês, a<=mãoêêã, Dufour fala francês, a<=mãoêã e Medeiros fala inglês, portuguêsêê.

Passo 2

O critério para ter arco de A para B é: Idiomas(A) cap Idiomas(B) neq varnothing. Se houver pelo menos uma língua comum, A pode dirigir a palavra a B e ser compreendido.

Passo 3

Agora vamos verificar cada par:
– Jensen para todos (todos partilham ao menos uma das quatro línguas).
– Leuzingner para Jensen, Dufour e Medeiros (há interseção em inglês, francês ou alemão).
– Dufour para Jensen e Leuzingner (compartilham francês e/ou alemão), mas não para Medeiros (sem língua em comum).
– Medeiros para Jensen e Leuzingner (compartilham inglês), mas não para Dufour.

Resposta

O digrafo resultante tem os arcos orientados:
Jensen→Leuzingner,
Jensen→Dufour,
Jensen→Medeiros,
Leuzingner→Jensen,
Leuzingner→Dufour,
Leuzingner→Medeiros,
Dufour→Jensen,
Dufour→Leuzingner,
Medeiros→Jensen,
Medeiros→Leuzingner.

Exercícios relacionados