Seja X o conjunto 1,2,3,4,5 e V o conjunto X^2 (conjunto de todos os subconjuntos de X que têm exatamente dois elementos). Digamos que dois elemento v e w de V são adjacentes se v cap w=emptyset. Essa relação de adjacência sobre V define o grafo de Petersen. Faça uma figura do grafo. Quantos vértices e quantas arestas tem o grafo?

Passo 1

Então, a gente tem um conjunto e quer formar todos os subconjuntos de que têm exatamente dois elementos. Esse conjunto de subconjuntos é chamado de e é conhecido como . A gente vai usar isso para definir um grafo, onde cada subconjunto de dois elementos é um vértice. Dois vértices são ligados por uma aresta se os subconjuntos correspondentes não tiverem nenhum elemento em comum. Esse grafo específico é chamado de Grafo de Petersen. A gente precisa desenhar esse grafo e descobrir quantos vértices e arestas ele tem.

Passo 2

Primeiro, vamos listar todos os subconjuntos de que têm exatamente dois elementos. Como tem 5 elementos, o número de subconjuntos de dois elementos é dado pela combinação .

Passo 3

Calculando C(5,2) = 5!2!(5-2)! = 5 times 42 times 1 = 10 :
Então, temos 10 subconjuntos de dois elementos. Essas serão as 10 vértices do Grafo de Petersen.

Passo 4

Agora, vamos entender como as arestas são formadas. Duas vértices estão conectadas se os seus subconjuntos não tiverem elementos em comum, ou seja, se a interseção deles for vazia ( ).

Passo 5

Vamos contar quantas pares de subconjuntos não compartilham nenhum elemento. Cada subconjunto de dois elementos precisa ser comparado com outros subconjuntos para verificar se não têm elementos em comum.

Passo 6

No Grafo de Petersen, cada vértice está conectado a exatamente 3 outros vértices que não compartilham elementos com ele. Como temos 10 vértices e cada um tem 3 arestas, o total de arestas seria:
10 times 32 = 15
Dividimos por 2 porque cada aresta é contada duas vezes nesse cálculo.

Resposta

O Grafo de Petersen tem 10 vértices e 15 arestas.

Exercícios relacionados