Tre punti in un grafo hanno sempre un arco
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Tre punti in un grafo hanno sempre un arco
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.
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.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
Re: Tre punti in un grafo hanno sempre un arco
Qual è esattamente in questo caso la differenza tra "deve avere" e "può avere" ?
Re: Tre punti in un grafo hanno sempre un arco
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$.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Tre punti in un grafo hanno sempre un arco
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?
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: Tre punti in un grafo hanno sempre un arco
Si, esattamente. Devi trovare la configurazione che ti minimizza il numero di archi da usare.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?
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$.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
Re: Tre punti in un grafo hanno sempre un arco
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...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$.
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à".
Ultima modifica di Claudio. il 17 mag 2016, 10:24, modificato 2 volte in totale.
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: Tre punti in un grafo hanno sempre un arco
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
Avrei risparmiato un sacco di fatica a tutti se avessi specificato meglio all'inizio cosa intendessi
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
Re: Tre punti in un grafo hanno sempre un arco
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.
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.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Tre punti in un grafo hanno sempre un arco
Io ci provo... $ \binom{n-2}{2}+1 $? Se è giusto provo anche a dimostrarlo
- René Descartes
- Messaggi: 6
- Iscritto il: 18 set 2015, 18:02
- Località: France
Re: Tre punti in un grafo hanno sempre un arco
In risposta alla missiva dello messer96
Vestra fideliter Renatus Cartesius.
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.karlosson_sul_tetto ha scritto:Non è troppo difficile, che i ciovini vi si cimentino
Vestra fideliter Renatus Cartesius.
Computo ergo sum.