Pular para o conteúdo principal

O Teorema do Aperto de Mãos

No post anterior, vimos que o grau de um vértice v de um grafo G(V,E), o qual denotamos por gr(v), é o número de arestas incidentes a ele. Agora, vamos explorar dois teoremas importantes sobre esse assunto: o teorema do aperto de mão e outro, que diz respeito à paridade dos vértices.



O grau total de um grafo G(V,E) é a soma dos graus de todos os seus vértices. Matematicamente, denotamos-lhe por [latex]partial (G) = sum gr(v)[/latex], onde [latex]v in V[/latex]. Daí, surgem dois úteis teoremas os quais nos ajudarão a, por exemplo, decidir se uma sequência de graus pode representar um grafo.



O Teorema do Aperto de Mãos


Aperto demão


Este Teorema nos diz que, se G(V, E) é um grafo não orientado, o grau total de G é igual ao dobro do número de arestas. Simbolicamente, [latex]partial(G) = 2vert E vert[/latex]. Esse Teorema funciona mesmo que o grafo possua laços e arestas múltiplas.


Para provar sua veracidade, basta observarmos que uma aresta [latex]{u, v}in E[/latex] contribui com uma unidade para o grau de u e com uma unidade para o grau de v. Logo, cada aresta contribui com duas unidades para o grau total, portanto [latex]partial(G) = 2vert E vert[/latex].


Desse teorema, tiramos que o grau total de um grafo não orientado sempre é um número par. Desta consequência, vem nosso segundo Teorema, o qual nos diz que o número de vértices de grau ímpar é par.


A demonstração também é simples: sabendo-se que [latex]partial (G) = sum partial(v)[/latex], com [latex]v in V[/latex], podemos separar a soma dos graus dos vértices em duas parcelas [latex]partial (G) = sum_{partial(v) par} partial(v) + sum_{partial(v) impar} partial(v)[/latex].


Já sabemos, pelo teorema anterior, que [latex]partial(G)[/latex] é par e, obviamente, [latex]sum_{partial(v) par} partial(v)[/latex] também é par. Observe que temos uma soma de ímpares cujo resultado é um número par. Portanto, o número de parcelas precisa ser par. Assim, o número de vértices de grau ímpar é par.


Com isso, podemos provar a existência ou não de determinados grafos. Por exemplo: é impossível existir um grafo cujos graus dos vértices sejam 1, 1, 4 e 3 porque há um número ímpar de vértices com grau ímpar. No entanto, graças a estes teoremas, também podemos provar que, em um grafo simples, devem existir pelo menos dois vértices com o mesmo grau.


Tendo G n vértices, no mínimo o grau de um vértice v de G é zero - isto é, v é um vértice isolado - e, no máximo, o grau de v é n - 1 - pois G é um grafo simples e, portanto, não possui laços. Ora, se houver um vértice de grau 0, não pode existir um vértice de grau n-1 e vice-versa. Assim, temos n vértices e n-1 graus possíveis. Pelo Princípio da Casa dos Pombos, obviamente existem pelo menos dois vértices com o mesmo grau.

Comentários

Postar um comentário

Postagens mais visitadas deste blog

Como acessar configurações avançadas no Sagemcom F@st 2704N

NOVO TUTORIAL: GUIA DEFINITIVO DAS CONFIGURAÇÕES AVANÇADAS DO SAGEMCOM F@ST 2704N!
Atualização 23/01/2015: Alguns problemas apontados e descobertos nesse modem:
1. Alguns usuários relatam dificuldade em salvar alterações na configuração ADSL;
2. Não sei como acessar os logs do modem; mesmo habilitando, eles não aparecem;
3. Se você trocar o DNS do modem, ele voltará ao da Oi ao ser reiniciado;
4. Estou enfrentando alguns problemas sérios de lentidão. Não sei se isso é relacionado ao modem ou a algum dispositivo na minha rede interna.
-----
Os modens da marca Sagemcom estão se tornando muito populares no Brasil, não, quiçá, por sua qualidade, mas porque eles são os atuais queridinhos das operadoras: quando você assina um plano ADSL, geralmente a operadora envia um modem wireless para sua casa a fim de que você possa navegar sem precisar ter gastos extras com esse equipamento. É claro que os equipamentos fornecidos pelas operadoras são básicos, mas saciam as necessidades dos usuários comuns - …

O Guia Definitivo das configurações avançadas no Sagemcom F@st 2704N

Há alguns meses, eu contei minha experiência com o Sagemcom F@st 2704N e tenho recebido diversos comentários sobre suas configurações avançadas. Agora que minhas aulas na faculdade estão acabando, resolvi reservar um tempinho para explorar melhor esse modem que, diga-se de passagem, é muito bom.