Tre punti in un grafo hanno sempre un arco

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Tre punti in un grafo hanno sempre un arco

Messaggio da karlosson_sul_tetto »

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.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Re: Tre punti in un grafo hanno sempre un arco

Messaggio da Claudio. »

Qual è esattamente in questo caso la differenza tra "deve avere" e "può avere" ?
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Tre punti in un grafo hanno sempre un arco

Messaggio da fph »

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]
mr96
Messaggi: 151
Iscritto il: 05 gen 2015, 01:07

Re: Tre punti in un grafo hanno sempre un arco

Messaggio da mr96 »

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?
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Tre punti in un grafo hanno sempre un arco

Messaggio da karlosson_sul_tetto »

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$.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Claudio.
Messaggi: 698
Iscritto il: 29 nov 2009, 21:34

Re: Tre punti in un grafo hanno sempre un arco

Messaggio da Claudio. »

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à".
Ultima modifica di Claudio. il 17 mag 2016, 10:24, modificato 2 volte in totale.
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Tre punti in un grafo hanno sempre un arco

Messaggio da karlosson_sul_tetto »

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 :oops:
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Tre punti in un grafo hanno sempre un arco

Messaggio da fph »

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. :)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
mr96
Messaggi: 151
Iscritto il: 05 gen 2015, 01:07

Re: Tre punti in un grafo hanno sempre un arco

Messaggio da mr96 »

Io ci provo... $ \binom{n-2}{2}+1 $? Se è giusto provo anche a dimostrarlo :lol:
Avatar utente
René Descartes
Messaggi: 6
Iscritto il: 18 set 2015, 18:02
Località: France

Re: Tre punti in un grafo hanno sempre un arco

Messaggio da René Descartes »

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. :wink:

Vestra fideliter Renatus Cartesius.
Computo ergo sum.
Rispondi