Gabarito de prova de Análise Combinatória

Primeira Prova de An´lise Combinat´ria a o
Profo Danilo Artigas - PURO - UFF
Todas as respostas devem ser devidamente justificadas.
1) [2,0] Seja G = (V, E) um grafo euleriano e e uma aresta tal que e ∈ E. Prove que G + e n˜o ´ euleriano.
/
a e
Resp. Como G ´ euleriano todo v´rtice de G tem grau par. A adic˜o da aresta e aumenta em uma e e a unidade o grau dos extremos de e, tornando-os v´rtices de grau ´ e ımpar. Logo G + e n˜o ´ euleriano. a e
2) [2,0] Em 2013, o prˆmio Nobel de qu´ e ımica foi entregue a trˆs pesquisadores que desenvolveram modelos e computacionais para calcular o resultado de rea¸oes qu´ c˜ ımicas.
ˆ
Na natureza existem dois tipos distinos de ´ ıons: os C´tions e os Anions. Os c´tions nunca se relacionam a a entre si e os ˆnions tamb´m nunca se relacionam entre si. No entanto, um c´tion pode se ligar a um a e a a
ˆnion dependendo de suas composi¸oes. Uma mol´cula ´ composta liga¸oes entre ´ c˜ e e c˜ ıons. Observe que uma mol´cula pode conter muitos c´tions e ˆnions, desde que c´tions n˜o se liguem a c´tions nem e a a a a a a ˆnions a ˆnions. Um grupo S de ions ´ denominado fortemente ligado se todos os pares de ´ a e ıons de
S possuem liga¸ao entre si. Dado um conjunto de 5 c´tions e 5 ˆnions, quantos grupos distintos c˜ a a fortemente ligados com 4 ´ ıons ´ poss´ formar com os elementos deste conjunto? e ıvel
OBS1 : O primeiro par´grafo da quest˜o ´ verdadeiro. a a e
OBS2 : O segundo, possivelmente, n˜o faz nenhum sentido para a Qu´ a ımica.
Resp. Seja G um grafos obtido atrav´s da representa¸ao dos ´ e c˜ ıons por v´rtices e a possibilidade de e rela¸ao entre eles por arestas. O grafo G ´ bipartido com parti¸ao em c´tions e ˆnions. Um grupo de c˜ e c˜ a a 4 ions fortemente ligados ´ um K4 em G. K4 possui K3 como subgrafo o que ´ um absurdo pois K3 ´ e e e um ciclo ´ ımpar e G ´ bipartido. Portanto, temos ZERO grupos fortemente ligados com 4 ´ e ıons.
3) Seja G