Mutasd meg, hogy egy n csúcsú összefüggő gráf csúcsai megszámozhatók úgy, hogy az 1, . , k csúcsok által feszített részgráf összefüggő legyen minden k<n és k=n esetén?

Ez nem indirekt lesz, hanem konkrét.

Áliitás: minden öf gráfnak van olyan csúca, akit ha elhagysz, akkor a maradék még öf.

(( Bizonyítás: veszel egy feszítõfát, és, nézed egy levelét, az ilyen. ))

Ezt alapján az algoritmus:

* veszed a G_n (n csúcsú) gráfodnak egy ilyen csúcsát, õ kapja az "n" sorszámot. Elhagyod.

* A kapott G_(n-1) gráffal megismétled ugyanezt, egészen addig, amíg el nem fogynak a csúcsaid.

Ekkor G_k az a gráf, amit az elsõ k csúcs kifeszít, és összefüggõ, hiszen úgy csináltuk G_(k+1)-bõl, hogy legyen összefüggõ.

(Fára ugyanez: sorra letépkeded leveleit, és fordított sorrendben feljegyzed õket. Ha tanultál gráf bejáró algoritmusokat, akkor pl a mélységi bejárás elhagyási számai egy ilyen listát adnak meg)

Hát az attól függhet, hogy kinek.

De alapjában véve igen, elég, azt hiszem ennél több nem kell.