9
Ci sono "n" vertici e 0 spigoli di un grafo non orientato. Quale può essere il numero massimo di spigoli che possiamo disegnare in modo tale che il grafico rimanga scollegato.Trova il numero massimo di spigoli nel grafico
Ho fatto la soluzione che possiamo escludere un vertice e trovare il numero massimo di bordi tra n-1 vertici del grafo non orientato, in modo che il grafico rimane disconnessa. che è n (n-1)/2 per n vertici e sarà (n-1) (n-2)/2 per n-1 vertici Può esserci una soluzione migliore?
Il motivo fornito da "" perché ogni nuovo spigolo aggiunto deve avere l'ennesimo vertice ad una estremità "' fornisce una spiegazione del perché è un * massimo locale * e non un * massimo globale *. Questa spiegazione non copre soluzioni con una struttura completamente diversa, che potrebbe avere più spigoli - senza una prova appropriata del perché non potevano. – amit
Il numero di bordi per una multigraph è ovviamente infinito. Ora se non può avere cicli autonomi, devi selezionare due vertici per aggiungere un bordo. Hai completamente collegato i primi (n-1) vertici. Per aggiungere un altro bordo entrambi i vertici non possono provenire dall'insieme iniziale di vertici n-1 perché hai reso ogni lato possibile dai vertici iniziali n-1. Quindi uno dei bordi deve essere l'ennesimo. Se sono consentiti cicli self, è possibile aggiungere n altri bordi perché i loop automatici non aggiungono alla connettività. – sukunrt
Ciò non copre affatto la possibilità di grafici costituiti da due sottografi completi di dimensioni diverse da 1, n-1. La soluzione è (accidentalmente) giusta, ma il ragionamento non lo è. – voidengine