Professor Ezequias

| Problemas Resolvidos

(UFRJ) A figura a seguir representa um grafo, isto é, um conjunto de pontos (nós) ligados por segmentos (arestas). Se X e Y são dois nós do grafo, designamos por d( X , Y ) o menor número de arestas necessárias para ir de X a Y , percorrendo exclusivamente um caminho sobre as arestas do grafo (assim, por exemplo, d( N , R ) = 3 ).

Teoria dos grafos

a) Determine d( A , B ).
b) Identifique os nós X e Y para os quais d( X , Y ) é máximo. Nesse caso, quanto é d( X , Y )?


Solução: Este problema é uma breve introdução à Teoria dos Grafos. Vamos resolver as duas questões observando a figura e o enunciado.

Item a) Como o menor número de arestas necessárias para ir do ponto A até o ponto B corresponde ao caminho AMOJB, temos que a resposta procurada é d( A , B ) = 4.

Item b) Os pontos X e Y para os quais d( X , Y ) é máximo são A e C, cujo caminho, que tem o menor número de aresta, é AMOJEFC e d( A , C ) = 6.



Um restaurante prepara 4 pratos quentes (frango, peixe, carne assada e salsichão) 2 saladas (verde e russa) e 3 sobremesas (sorvete, romeu e julieta, frutas). De quantas maneiras distintas um freguês pode se servir consumindo um prato quente, uma salada e uma sobremesa?
Solução: Podemos resolver esse problema utilizando um diagrama de árvore (um tipo especial de grafo).
grafo conexo sem ciclos
Observando o diagrama temos que o resultado é 24 maneiras. De fato, temos três níveis de decisão (3 etapas), escolher um prato quente, escolher uma salada e escolher uma sobremesa. Como temos 4 possibilidades na primeira, 2 possibilidades na segunda e 3 possibilidades na terceira, o Princípio Fundamental da Contagem (PFC) afirma que o número de maneiras de tomarmos as três decisões é 4󫎿=24.
Em um torneio de futebol, participarão seis times. Cada time deve jogar exatamente uma vez com cada um dos outros participantes (hexagonal). Quantos jogos haverá no torneio?
Solução: Podemos resolver o problema com o grafo abaixo, onde cada ponto (vértice) é um time e cada segmento (aresta) é um jogo.
grafo k6 - torneio
Assim, o número de jogos é 15.
De fato, em um conjunto de 6 times de Futebol, cada jogo é um subconjunto (combinação) de 2 times (a ordem não faz a diferen鏰).
Assim, o número de jogos é o número de combinações de 2 times escolhidos entre 6 equipes, ou seja, C6,2 = 6×5/2! = 30/2 = 15.
(MACK) Os polígonos de K lados ( k múltiplos de 3), que podemos obter com vértices nos 9 pontos da figura, são em número de:
torneio
(A) 83
(B) 84
(C) 85
(D) 168
(E) 169


Solução: Como K é múltiplo de 3, o valor de K é 3 (triângulo), 6 (hexágono) ou 9 (eneágono).

Para construir um triângulo precisamos escolher 3 pontos (vértices) dentre os 9 pontos disponíveis, e mais, a ordem com que estas escolhas são feitas NÃO FAZ diferença. Logo, o número de triângulos é o número de combinações de 3 vértices escolhidos entre 9 pontos, ou seja, C 9,3 = 9×8×7/3! = 504/6 = 84 triângulos.

De modo análogo:

O número de hexágonos é C 9,6 =  9×8×7×6×5×4/6! = 60480/720 = 84.

O número de eneágonos é C 9,9 =  9!/9! = 1

Então, o número de polígonos é C9,3 + C9,6 + C9,9 = 84 + 84 + 1 = 169 (op玢o E)





| Privacidade
| Vídeos