prouve que le graphe G = (V, E) a au moins | v | - | E | composants

Question

Prouver que le graphique G=(V,E) a au moins |v|-|E| composants

Je dois répondre à la question ci-dessus avec l'exemple et la description complète.

Answer 1

Un graphique avec | V | sommets et pas de bords a exactement | V | Composants. L'ajout d'une arête peut réduire le nombre de composants d'au plus un (si les sommets sur lesquels l'arête est incidente n'étaient pas précédemment connectés par un autre chemin, sinon le nombre de composants n'est pas réduit). Donc le moins possible de composants après avoir ajouté | E | les arêtes sont | V | - | E | et pas de graphique de | V | sommets et | E | les arêtes peuvent avoir moins de ce nombre de composants.

Answer 2

revendication: Chaque composant Ci avec des sommets Vi comporte au moins |Vi|-1 bords.
La preuve: Le sous-graphe contenant seulement Vi est connecté, et le graphe connexe minimal est un arbre, qui a |Vi|-1 bords. Si Ci avait moins de Vi-1 bords - il n'aurait pas été connecté, ce qui est en contradiction avec la façon dont nous avons défini Ci.

Indiquez Ei le nombre d'arêtes dans le composant Ci.
Notez que sum{|Ei| for each Ci} = E, car il n'y a aucun composant de connexion de bord Ci et composant Cj (sinon ils auraient été connectés eux-mêmes). Maintenant, résumons tous bords dans tous Ci, et nous vous répondrons

|E| =(1) sum { |Ei| } >=(2) sum{|Vi|-1} =(3) |V| - sum{1 | for each Ci} 
            =(4) |V| - #components 
-> 
|E| >= |V| - #components 
#components >= |V| - |E| 

QED

Explication pour les égalités dans la preuve ci-dessus:

(1) vient de sommer toutes les arêtes de chaque composant totalisent |E|, car il n'y a pas d'arêtes qui traversent les composants (expliqué ci-dessus)
(2) Provient de la revendication que nous avons prouvé
(3) Sommation | Vi | pour tous Ci résultats dans |V|
(4) la somme 1 pour chaque composante se traduit par le nombre de composants