Domanda

Se è collegato un grafico G (V, E), il numero di bordi è almeno il numero di vertici-1. È abbastanza evidente se ci pensi, ma come lo dimostrezzo formalmente?

È stato utile?

Soluzione

Immagina un processo in cui si inizia con il grafico vuoto e aggiungi i bordi uno per uno.Tieni traccia del numero di componenti collegati.All'inizio, ci sono $ | v | $ componenti collegati.Ogni bordo si aggiunge sia appartenente all'interno di un componente collegato o si unisce due componenti collegati e, in ogni caso, il numero di componenti collegati diminuisce al massimo 1. quindi dopo aver aggiunto $ | E |$ bordi, il numero di componenti collegati è almeno $ | V |- | e | $ .Se il grafico è collegato, $ | V |- | e |\ Leq 1 $ e così $ | e |\ Geq | V |- 1 $ .

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top