Come al solito è facile, come al solito date la soluzione solo se non sapete risolverlo.
Abbiamo un grafo su n vertici, e ogni vertice ha grado minore o uguale a k. Dimostrare che si possono prendere almeno $ \lceil\frac{n}{k+1}\rceil $ vertici che formino un'anticricca (che siano dunque a due a due non collegati).
Anticricche
Anticricche
Sono il cuoco della nazionale!
Re: Anticricche
Suvvia, era uno scherzo!Anér ha scritto:Come al solito date la soluzione solo se non sapete risolverlo.
Sono il cuoco della nazionale!
Re: Anticricche
Ma sbaglio o è semplicissimo? Penso vada bene costruire l' anticricca facendo vertice per vertice. Prendo un vertice a caso, e questo sarà il primo appartenente all'anticricca; poi, per scegliere il secondo, ho una scelta di almeno $n-k-1$ altri vertici, visto che uno è il vertice stesso e al massimo altri k sono quelli a lui collegati, che nel peggiore dei casi non sono collegati a quello da scegliere. Poi procedo con il terzo, e dovrò sceglierlo almeno tra $n-2k-2=n-2(k-1)$, per gli stessi motivi. Ora posso dimostrare che l'm-esimo termine dell'anticricca lo posso scegliere tra almeno $n-(m-1)(k+1)$ vertici; infatti, se prima ne ho già scelti $m-1$, dovrò escluderne $(m-1)k$ e i vertici stessi.
Quindi adesso, per vedere quanti vertici può contenere al minimo l'anticricca, basterebbe che $n-(\lceil\frac{n}{k+1}\rceil-1)(k+1)$ sia maggiore di 0 (e non quello successivo). Questo è vero perché $\lceil\frac{n}{k+1}\rceil-1< \frac{n}{k+1}$ e sotituendo $\frac{n}{k+1}$ ottengo l'uguaglianza a 0 (mentre con l'intero subito dopo si ottiene un numero nullo o negativo) $\square$
Quindi adesso, per vedere quanti vertici può contenere al minimo l'anticricca, basterebbe che $n-(\lceil\frac{n}{k+1}\rceil-1)(k+1)$ sia maggiore di 0 (e non quello successivo). Questo è vero perché $\lceil\frac{n}{k+1}\rceil-1< \frac{n}{k+1}$ e sotituendo $\frac{n}{k+1}$ ottengo l'uguaglianza a 0 (mentre con l'intero subito dopo si ottiene un numero nullo o negativo) $\square$
Re: Anticricche
No, non sbagli, era davvero semplice.Euler ha scritto:Ma sbaglio o è semplicissimo?
Sono il cuoco della nazionale!