La somme des degrés $\sum_{v\in V} id(v)$et hors-degrés $\sum_{v\in V} od(v)$sont toujours égaux ?

Dec 02 2020

Je travaille sur le problème #24 de la section 11.3 de Ralph P. Grimaldi's Discrete and Combinatorial Mathematics, an Applied Introduction, cinquième édition.

Question:

Laisser$G=(V,E)$être un graphe orienté, où$|V|=n$et$|E|=e$. Quelles sont les valeurs pour$\sum_{v\in V} id(v)$et$\sum_{v\in V} od(v)$?

$id(v)$et$od(v)$sont les degrés entrants et sortants.

Les degrés d'entrée et de sortie sont mentionnés en passant à la fin de la section 11.3, de sorte que chacun est laissé à lui-même pour répondre à cette question.

J'ai essayé de déduire les faits nécessaires sur$\sum_{v\in V} id(v)$et$\sum_{v\in V} od(v)$et j'aimerais savoir si ma logique est correcte:

Étant donné un nombre fini de sommets$n$pour chaque bord "dirigé" que vous ajoutez, vous ajoutez$1$pour$\sum_{v\in V} id(v)$et$\sum_{v\in V} od(v)$respectivement, et ils doivent toujours être égaux?

Si oui, alors$\sum_{v\in V} id(v)=\sum_{v\in V} od(v)=e?$

Réponses

1 user21820 Dec 06 2020 at 20:43

Pour rendre votre idée rigoureuse, vous devez utiliser l'induction. Laisser$Q(k)$être la déclaration que chaque graphe orienté avec exactement$k$bords satisfait la revendication souhaitée. Ensuite, utilisez l'induction sur$Q$. Ce faisant, veillez à ne rien faire comme "Si$Q(k)$est vrai, alors laissez$G$être n'importe quel graphe orienté avec$k$bords et ajouter un bord..." ! Lisez cette explication de l'induction pour vous assurer que vous faites correctement l'induction.