Grafi

[Stardust*11]

Salve, non riesco a risolvere questo esercizio, potete aiutarmi??

1 - Esiste un grafo connesso con (esattamente) 100 vertici e 93 lati? Si, No, perchè?

Io dico no, perchè essendo i vertici in numero maggiore rispetto ai lati, ci saranno dei vertici isolati, quindi il grafo non può essere connesso. E' giusto il ragionamento??

2 - Esiste un grafo connesso con (esattamente) 93 vertivi e 100 lati?? Si, Ni, perchè?

Io dico di si, ma non so giustificarlo

[vict85]

Non sono molto pratico di grafi comunque...

Del primo, direi di no perché il minimo numero di lati necessari per connettere un grafo sono N-1 dove N è il numero di vertici. Si dimostra facilmente per induzione.

Del secondo si, basta prendere un grafo con 93 vertici e 92 lati e poi aggiungerci a caso i restanti lati.

[Stardust*11]

ciao, grazie per avermi risposto. Sul secondo sono in dubbio perchè sugli appunti ho scritto "almeno" N-1 lati, mentre sul libro c'è scritto che i lati devono essere N-1, non vorrei che dovessero essere esattamente 92..anche io ho fattoi il tuo ragionamento di mettere diciamo a "casaccio" gli altri lati restanti

[adaBTTLS1]

con N-1 lati riesci a costruire un albero (grafo connesso aciclico), con altri lati in più puoi sempre costruire un grafo connesso ciclico, senza superare il numero di lati pari a $(N(N-1))/2$.
dunque con 93 vertici i lati possono variare da 92 a 4278.
ciao.