Uma estrela é um grafo bipartido tal que uma das partes, digamos X, é um conjunto unitário e o vértice que pertence a ela está ligado a todos os vértices da outra parte, Y. Com base nessa definição, determine os graus dos vértices de uma estrela.

Passo 1

Beleza, vamos lá! O exercício fala sobre uma estrela, que é um tipo de grafo bipartido. Um grafo bipartido é dividido em duas partes, X e Y, sem conexões dentro da mesma parte. No caso da estrela, a parte X tem só um vértice, e ele está conectado a todos os vértices da parte Y. A gente precisa descobrir qual é o grau de cada vértice nessa estrela. Para resolver isso, vamos precisar entender o que é grau de um vértice e como funciona um grafo bipartido, especialmente uma estrela.

Passo 2

Primeiro, vamos lembrar o que é o grau de um vértice. O grau de um vértice é o número de arestas que estão conectadas a ele. Então, para cada vértice na estrela, vamos contar quantas conexões (arestas) ele tem.

Passo 3

Na estrela, temos duas partes: X e Y. A parte X tem somente um vértice. Como a estrela é um grafo bipartido, esse único vértice de X está conectado a todos os vértices de Y. Vamos chamar esse vértice de vX e os vértices de Y de vY1, vY2, dots, vYn, onde n é o número de vértices em Y.

Passo 4

Agora, vamos determinar o grau de vX. Já que vX está conectado a todos os n vértices de Y, o grau de vX é n. Ou seja:
Grau de vX = n

Passo 5

Em seguida, vamos ver o grau de cada vértice em Y. Cada vértice de Y está conectado apenas a vX e não a nenhum outro vértice de Y (já que grafo bipartido não tem conexões dentro da mesma parte). Então, cada vértice vYi tem apenas uma conexão, que é com vX. Portanto:
Grau de vYi = 1 para todo i = 1, 2, dots, n

Resposta

Os graus dos vértices de uma estrela são: o vértice central possui grau n, onde n é o número de vértices na parte Y, e cada vértice da parte Y possui grau 1.

Exercícios relacionados