Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

É possível organizar uma festa em que cada convidado tenha um número diferente de amigos presentes?

0 votos
25 visitas
perguntada Set 11 em Matemática por pedro zarur (1 ponto)  

Exercício 1.3 do capítulo 1 do livro "Complex Networks: Principles, Methods and Applications" de Vito Latora, Vincenzo Nicosia e Giovanni Russo:

a) Imagine que você organizou uma festa com 5 pessoas. Algumas delas já se conheciam previamente. Em particular, duas delas tem um amigo cada na festa, duas delas tem dois amigos cada e uma tem três amigos. Essa rede é possível? Por que? (Prove que, em qualquer grafo, o número de nós de grau ímpar deve ser par)

b) É possível organizar uma festa em que cada convidado tenha um número diferente de amigos presentes? Você pode sustentar sua resposta com uma demonstração matemática?

c) Considere um grafo bipartido com \(n\) nós do tipo 1 e \(v\) nós do tipo 2. Prove que \(k_N = \frac{v}{n} k_V\), sendo \(k_N\) o grau médio dos nós do tipo 1 e \(k_V\) o grau médio dos nós do tipo 2.

d) Prove que, se um grafo não tem ciclos de comprimento ímpar, então ele é bipartido.

Compartilhe

1 Resposta

0 votos
respondida Set 11 por pedro zarur (1 ponto)  
editado Set 13 por pedro zarur

a) Essa rede não é possível pois ela possui três nós de grau ímpar. Vamos provar que, em todo grafo, o número de nós de grau ímpar deve ser par:

Temos que o grau de um nó é igual ao número de arestas que incidem sobre esse nó. Como cada aresta pode ser encarada como um par (nesse caso, não ordenado) de nós, a soma de todos os graus de todos os nós é igual a duas vezes o número de arestas. Sendo \(T\) a soma dos graus de todos os nós, \(P\) a soma dos graus de nós de grau par e \(I\) a soma dos graus de nós de grau ímpar, temos que \(T = P + I\). Temos que \(P\) obviamente é par. Logo, como \(T\) também é par, \(I\) precisa ser par. Assim concluímos que o número de nós de grau ímpar é par.

b) Não é possível que essa festa aconteça. Consideremos uma festa em que nenhum participante tem o mesmo número de amigos. Se a festa tem \(x\) participantes, então a cada participante é associado um número diferente de amigos do conjunto \(\{0,1,...,x-1\}\). Logo, um dos participantes necessariamente tem \(x-1\) amigos. Mas se isso é verdade, então todos os demais convidados são amigos desse participante em questão, e ninguém tem \(0\) amigos. Logo, no mínimo dois participantes da festa terão o mesmo número de amigos presentes.

c) Como o grafo é bipartido, temos que cada aresta é um par composto por um elemento do tipo 1 e um elemento do tipo 2. Logo, a soma dos graus de elementos do tipo 1 (\(sg_1\)) é igual a soma dos graus dos elementos do tipo 2 (\(sg_2\)). Também temos que:

\(k_N = \frac{sg_1}{n}\) e \(k_V = \frac{sg_2}{v}\)

Logo, como \(sg_1 = sg_2\) concluímos que \(n k_N = v k_V\), isto é, \(k_N = \frac{v}{n} k_V\).

d) Um ciclo é uma sequência de nós e arestas entre dois nós (um caminho) em que o nó inicial e o nó final coincidem. O comprimento de um caminho é igual ao número de arestas do caminho em questão. A distância entre dois nós \(a\) e \(b\) é igual ao comprimento do menor caminho entre \(a\) e \(b\) em que nenhum nó é visitado mais de uma vez. Denotaremos o menor caminho como \(P(a,b)\) e o seu comprimento como \(| P(a,b) |\).

Suponhamos que um grafo \(G = (V, L)\) não tenha ciclos de comprimento ímpar. Sendo \(z\) um vértice qualquer, podemos construir os seguintes conjuntos:

\(V_p = \{x \in V : | P(z, x) |\ é \ par\} \) e \(V_i = \{x \in V : | P(z, x) |\ é \ ímpar\} \)

Vamos assumir que existe uma aresta \((a,b) \in L\) tal que \(a,b \in V_p\) ou \(a,b \in V_i\). Em qualquer um dos dois casos, \(P(z,a)\), \(P(z,b)\) e \((a,b)\) formam um ciclo de comprimento ímpar. Com essa contradição, concluímos que não existe uma aresta \((a,b) \in L\) tal que \(a,b \in V_p\) ou \(a,b \in V_i\). Logo \(G\) é bipartido.

...