Foto de Jonas L.
Jonas há 1 ano
Enviada pelo
Site

Grafos

Seja G um grafo. Definimos o grau de  x ∈ V (G) por d(x) = |{xy; xy ∈ E(G)}|  Mostre que

2 respostas
Professor Isnard L.
Identidade verificada
  • CPF verificado
  • E-mail verificado
Respondeu há 1 ano
Contatar Isnard

Basta observar que cada aresta é incidente em exatamente dois vértices. Enquanto que o grau de um vértice é a quantidade de arestas que incide em um vértice. Digamos, por exemplo, que o nosso grafo seja ({x, y, z}, {x,y},{y,z}), isto é, uma árvore com 3 vértices e 2 arestas. Temos que


 

Ou seja, a aresta contribuiu uma unidade para o grau de x e uma unidade para grau de y. Assim como a aresta contribuiu uma unidade para o grau de z e uma unidade para o grau de y.

 

Logo, somando os valores dos graus, temos 1+2+1 = 4 = 2*2 = 2* número de arestas.

Um professor já respondeu

Envie você também uma dúvida grátis
Ver resposta
Envie uma dúvida grátis
Resposta na hora da Minerva IA e de professores particulares
Enviar dúvida
Professor Assis J.
Identidade verificada
  • CPF verificado
  • E-mail verificado
Respondeu há 1 ano
Contatar Assis

A afirmação dada é conhecida como o Teorema da Soma dos Graus ou o Teorema da Mão Dupla em Teoria dos Grafos. Ela declara que a soma dos graus de todos os vértices de um grafo é igual ao dobro do número de arestas. Vamos provar isso:

Para cada aresta em um grafo, há dois "fins" que são conectados a um vértice. Portanto, se contarmos todos os "fins" de todas as arestas, obteremos exatamente o dobro do número de arestas no grafo.

Por outro lado, se somarmos os graus de todos os vértices do grafo, também estamos contando todos os "fins" de todas as arestas, pois o grau de um vértice é o número de arestas conectadas a ele.

Portanto, a soma dos graus de todos os vértices é igual ao dobro do número de arestas, o que conclui a prova. Assim, temos:

? d(v) = 2|E(G)|

para todo v ? V(G), onde d(v) é o grau do vértice v, V(G) é o conjunto de vértices do grafo G, e E(G) é o conjunto de arestas do grafo G.

Um professor já respondeu

Envie você também uma dúvida grátis
Ver resposta
Minerva IA
do Profes
Respostas na hora
100% no WhatsApp
Envie suas dúvidas pelo App. Baixe agora
Precisa de outra solução? Conheça
Aulas particulares Encontre um professor para combinar e agendar aulas particulares Buscar professor