Question

Considere o grafo em que os vértices correspondem às palavras ovo, trem, caso,

remo e sova e em que existe uma aresta conectando dois vértices quando as palavras

correspondentes possuem pelo menos uma letra em comum. Neste grafo, o número total de arestas é:

A) 4 B) 5 C) 6 D) 7 E) 8

Answer 1

O número total de arestas é 7 (Alternativa D).

$\dotfill$

Em matemática, um grafo é uma estrutura composta de vértices e arestas e serve para estudar a relação entre objetos de um determinado conjunto. No caso, os vértices são as palavras e as arestas ligam os vértices que possuem palavras compartilhando pelo menos uma letra em comum.

A fim de visualizar o grafo, vamos primeiramente fazer um esquema na forma de uma matriz de similaridades. Tal matriz tem 5 linhas e 5 colunas. Se há letra comum entre a palavra que está na posição na linha i e coluna j, marcamos um x nesta posição correspondente. Observe:

        ovo   trem  caso  remo  sova

ovo     -                  x          x        x    

trem             -                    x        

caso  x                  -          x        x

remo x        x        x          -        x

sova   x                  x          x        -

Observe que trata-se de uma matriz simétrica ( Se i está ligado a j, logo j está ligado a i).

Contando o número de x na diagonal superior (ou inferior) temos 7 arestas. Logo,  o número total de arestas é 7 (Alternativa D).

$\dotfill$

Até a próxima!!