OliForum Matematico

Non è troppo difficile, che i ciovini vi si cimentino :)

Dato un grafo con $n$ vertici, determinare il numero minimo di archi che "può" (cioè non "deve") avere in modo che presi qualsiasi tre vertici, almeno una coppia di essi siano collegati da un arco.

Qual è esattamente in questo caso la differenza tra "deve avere" e "può avere" ?

Considera $n$ fissato. Tra tutti i grafi che soddisfano la proprietà richiesta, ce ne sarà (almeno) uno con il minimo numero $m$ di archi e (almeno) uno con il massimo numero $M$. Allora i grafi devono avere almeno $m$ vertici, e possono averne fino a $M$.

Io continuo ad avere qualche problema di comprensione: intendi che, detto $ m $ questo numero, allora esiste una configurazione con $ n $ vertici e $ m $ archi che soddisfa ma non necessariamente tutte quelle con $ m $ archi soddisfano? Cioè che posso fare una configurazione con quel numero ma non tutte vanno bene?

mr96 ha scritto:Io continuo ad avere qualche problema di comprensione: intendi che, detto $ m $ questo numero, allora esiste una configurazione con $ n $ vertici e $ m $ archi che soddisfa ma non necessariamente tutte quelle con $ m $ archi soddisfano? Cioè che posso fare una configurazione con quel numero ma non tutte vanno bene?

Si, esattamente. Devi trovare la configurazione che ti minimizza il numero di archi da usare.

Il problema interpretato nell'altro modo sarebbe stato: dato un grafo con $n$ vertici, trovare $m$ tale che comunque si dispongano $m$ archi, ogni terna di punti avrà almeno un lato. In tal caso la risposta sarebbe stata: $\binom{n}{2}-2$.

fph ha scritto:Considera $n$ fissato. Tra tutti i grafi che soddisfano la proprietà richiesta, ce ne sarà (almeno) uno con il minimo numero $m$ di archi e (almeno) uno con il massimo numero $M$. Allora i grafi devono avere almeno $m$ vertici, e possono averne fino a $M$.

Scusami sbaglio o interpretandolo così allora $M=\binom n2$? Una cosa del genere avrebbe senso solo se la proprietà smettesse di valere da un certo punto in poi...
Da quello che ha appena detto Karlson mi pare di capire che il problema originale sia trovare l'$m$ di fph. E onestamente a me sembra lo stesso problema sia scrivendo "può" che "deve". Se uno chiedesse $M$ allora non dovrebbe dire torvare il minimo, ma il massimo. Mentre se uno chiedesse ciò che Karlson ha detto essere banale dovrebbe chiedere "trovare il minimo numero di archi $m$ per cui tutti i grafi con almeno $m$ archi soddisfano tale proprietà".

Penso che la risposta di fph fosse relativa soltanto all'interpretazione dei verbi, ovvero un esempio per far vedere la differenza tra "deve" e "può" in un contesto qualsiasi, non legato a questo problema.


Avrei risparmiato un sacco di fatica a tutti se avessi specificato meglio all'inizio cosa intendessi

Mah io lo intendevo riguardo a questo problema, più che altro perché non avevo pensato bene alla configurazione e il testo di karlosson aveva tratto in inganno anche me.
Visto quel "minimo" il testo ha un'unica interpretazione possibile, ma in ogni caso io li avrei usati nel modo che ho scritto lì sotto in un contesto matematico. L'importante è farsi capire, comunque.

Io ci provo... $ \binom{n-2}{2}+1 $? Se è giusto provo anche a dimostrarlo

In risposta alla missiva dello messer96

karlosson_sul_tetto ha scritto:Non è troppo difficile, che i ciovini vi si cimentino

Ubi solitudinem faciunt, solutionem appellant! Codesto esercitio est cogitato univocamente pelli juvenes pueri, secondo lo volere dello savio karlosson. Non est mea intentione sminuire lo vostro laboro, sed ego cogito quae melius est scorgere prima li tentativi delli utentes inexperti.

Vestra fideliter Renatus Cartesius.