Se non ho cannato i ragionamenti...

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Se non ho cannato i ragionamenti...

Messaggio da Gerald Lambeau »

Sia $\mathcal{G}$ un grafo orientato con un numero finito di vertici (facciamo che sono almeno $2$) e tale che da ogni vertice parta esattamente un arco uscente (non c'è limite al numero di archi entranti invece). Sia $n$ il numero minimo insiemi in cui è possibile partizionare i vertici in maniera tale che due vertici collegati da un arco, qualunque sia il verso dell'arco, stanno in insiemi diversi.
Determinare tutti i possibili valori di $n$.
"If only I could be so grossly incandescent!"
Ilgatto
Messaggi: 38
Iscritto il: 24 ott 2017, 16:36

Re: Se non ho cannato i ragionamenti...

Messaggio da Ilgatto »

Sono possibili solo i casi $n=2$ e $n=3$.
Chiamiamo $k$ il numero di vertici del nostro grafo. Notiamo prima di tutto che ci sono esattamente $k$ archi che collegano i vertici tra loro.
Iniziamo dicendo che, essendo $k>0$, il caso $n=1$ non può verificarsi perchè due vertici collegati devono stare in insiemi diversi. $n=2$ è possibile per ogni $k$, basta pensare al caso in cui si collegano $k-1$ vertici a un unico vertice; si creano quindi $2$ insiemi di $k-1$ e $1$ elementi. Il caso $n=3$ è possibile se si collega il vertice $a$ al vertice $b$, $b$ a $c$ e $c$ ad $a$ e tutti gli altri si collegano casualmente a uno dei $3$; ora $a$, $b$ e $c$ sono per forza in 3 insiemi diversi e quindi $n=3$ è possibile. Notare che $n=3$ non è possibile se $k<3$ per ovvi motivi.
Ora, scrivere $n>3$ significa dire che ci sono almeno $4$ vertici collegati tutti tra loro, ma ciò non è possibile, visto che, considerando $k=4$, ci dovrebbero essere $3$ archi collegati a ogni vertice (1 per ogni altro vertice), ma considerando che gli archi sono al massimo $k$ e quindi $4$, non è possibile avere i $ \frac {3*4}{2}= 6 $ archi richiesti. Aumentando il numero di vertici, non si risolverebbe nulla, visto che comunque non aumenterebbe il numero di collegamenti diretti possibili tra i $4$ vertici già presenti.
Prendiamo di nuovo la configurazione con $k=4$, aggiungendo $1$ vertice si avrebbe aumentato di $1$ il numero di archi presenti e di $4$ il numero di archi richiesti (ognuno dei $4$ vertici già presenti deve essere collegato a quello nuovo). Non potendo avere $n=4$, non si può avere nemmeno $n>4$ in quanto, come appena detto, il numero di archi richiesti per un certo $n$ aumenta più velocemente del numero di archi disponibili.
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Se non ho cannato i ragionamenti...

Messaggio da Gerald Lambeau »

Ilgatto ha scritto: 25 ott 2017, 22:16 Ora, scrivere $n>3$ significa dire che ci sono almeno $4$ vertici collegati tutti tra loro
Questa frase non mi convince. Cioè, se non ricordo male il problema è vera, ma va dimostrata, perché magari c'è una configurazione di archi per i quali quattro vertici non tutti collegati tra loro da un arco sono comunque forzati a stare in quattro insiemi diversi: devi dimostrare che questa situazione non si verifica mai.
"If only I could be so grossly incandescent!"
Ilgatto
Messaggi: 38
Iscritto il: 24 ott 2017, 16:36

Re: Se non ho cannato i ragionamenti...

Messaggio da Ilgatto »

Pensavo non servisse una dimostrazione.
Comunque se si pensa che esista una funzione $f(x)$ che associa a ogni vertice $x$ il suo insieme di appartenenza, si nota che se $f(a)=f(b)$ allora $a$ e $b$ non possono essere collegati.
Nel caso assurdo in cui io abbia 4 vertici appartenenti a 4 insiemi diversi (non potendo diminuire ulteriormente il numero di insiemi per le condizioni del problema), allora avrei 4 diversi valori della funzione. Si può notare però che necessariamente $ f(a) \neq {f(b)} $ se $a$ e $b$ sono collegati, ma potrebbero comunque non esserlo (avevo dato per scontato che questo non fosse possibile). I nostri 4 punti sono necessariamente in insiemi diversi, altrimenti sarebbe possibile avere un numero minore di 4 di insiemi. Ciò significa che, essendo l'operazione "diverso" non transitiva (cioè $ a \neq {b} $ e $ b \neq {c} $ non implicano necessariamente $ a \neq {c} $) e considerando che ogni $f(i)$ è diversa dalle altre 3 $f$, ogni $i$ è collegato agli altri 3 vertici. Se così non fosse, ci sarebbe almeno un vertice collegato a solo altri 2 vertici, quindi sarebbe necessariamente in un insieme diverso da quei due punti, ma potrebbe essere tranquillamente in quello in cui si trova il terzo. Siamo giunti quindi ad avere 3 insiemi possibili, ma avevamo supposto che il numero di insiemi fosse 4, quindi per avere 4 insiemi i 4 punti devono essere tutti collegati tra loro, formando quindi 6 archi in totale.
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Se non ho cannato i ragionamenti...

Messaggio da Gerald Lambeau »

Ilgatto ha scritto:Se così non fosse, ci sarebbe almeno un vertice collegato a solo altri 2 vertici, quindi sarebbe necessariamente in un insieme diverso da quei due punti, ma potrebbe essere tranquillamente in quello in cui si trova il terzo.
E chi ti dice che non è collegato a un quinto vertice che sta nello stesso insieme di quel vertice a cui non è collegato?
"If only I could be so grossly incandescent!"
Ilgatto
Messaggi: 38
Iscritto il: 24 ott 2017, 16:36

Re: Se non ho cannato i ragionamenti...

Messaggio da Ilgatto »

Stiamo discutendo la situazione in cui abbiamo 4 vertici collegati in questo modo:
$a$ collegato a $b$, $c$ e $d$
$b$ collegato a $a$, $c$ e $d$
$c$ collegato a $a$ e $b$
$d$ collegato a $a$ e $b$
Per quanto detto prima, $n=3$ perchè i 3 insiemi sono {$a$}, {$b$} e {$c, d$}. Se aggiungo un quinto vertice($e$), collegato a $a$, $b$ e $d$, questo o sarà in un quarto insieme aggiuntivo, o dividerà l'insieme {$c, d$} creando i due insiemi {$c, e$} e {$d$}.
Tornando al problema originale, se consideriamo la situazione appena descritta, notiamo che ci sono 5 vertici, 8 archi e 4 insiemi, ma sappiamo che il numero di vertici è uguale al numero di archi, quindi la configurazione non è accettabile.
In generale si può notare che:
1. Se il vertice $a$ è collegato solo al vertice $b$, allora $ f(a) \neq {f(b)} $ e non ho altre condizioni su $f(a)$
2. Se i vertici $a$, $b$ e $c$ formano un triangolo, sono necessariamente tutti in insiemi diversi
3. Se un vertice $a$ è collegato a tutti e tre i vertici di un triangolo, si ha una situazione impossibile, avendo troppi archi. Diminuendo il numero di archi o aumentando il numero di vertici non si può arrivare a una configurazione tale che essi siano uguali e che ci siano 4 insiemi separati; difatti, per arrivare a una configurazione con 4 insiemi serve collegare un vertice a tutti i vertici di un triangolo (impossibile per il punto 2.), altrimenti esso potrebbe essere nello stesso insieme di uno dei vertici del triangolo stesso diminuendo a 3 il numero di insiemi.
4. Per il punto 3. non si può avere $n=4$, quindi non si può avere nemmeno $n>4$, perchè se fosse possibile avere una tale configurazione si potrebbero eliminare i vertici di uno dei 5 insiemi, lasciando 4 insiemi (situazione impossibile). L'operazione di eliminazione del solo quinto insieme è possibile perchè lascerebbe immutati i vertici degli altri insiemi e gli archi che li collegano tra loro; questo perchè gli archi che collegano un vertice del quinto insieme con quelli di altri insiemi non variano in alcun modo la disposizione di questi ultimi (non vale la proprietà transitiva), ma permettono solo l'esistenza del quinto insieme, i cui vertici devono essere collegati ad almeno uno di ciascuno degli altri insiemi.
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Se non ho cannato i ragionamenti...

Messaggio da Gerald Lambeau »

Ok, stavolta sei stato molto dettagliato, è giusta.
"If only I could be so grossly incandescent!"
Rispondi