Grafo malvagio

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Talete
Messaggi: 665
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Grafo malvagio

Messaggio da Talete » 21 mar 2017, 20:07

Sia $\Gamma$ un grafo con le seguenti proprietà:
(i) la media dei gradi dei vertici di $\Gamma$ è $2$;
(ii) ogni vertice di $\Gamma$ ha grado al massimo $3$.

Dimostrare che esiste un sottografo $\Gamma'\subseteq \Gamma$ in cui tutti i vertici hanno grado $2$.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Avatar utente
Sirio
Messaggi: 198
Iscritto il: 08 set 2016, 22:01

Re: Grafo malvagio

Messaggio da Sirio » 21 mar 2017, 21:38

Va detto che per deformazione da giochi logici stavo ipotizzando doppi ponti tra i vertici... :lol:
Testo nascosto:
Supponiamo che il grafo sia connesso. Leviamo dal grafo tutti i vertici di grado 1. Se lo spigolo che partiva da essi beccava un vertice di grado 1, il grafo non era connesso, quindi non vale. Se beccava un vertice di grado 2, questo mi diventa di grado 1. Se beccava un vertice di grado 3, questo mi diventa di grado 2. Ora, in ogni caso si ottiene un grafo che rispetta sia la (i) che la (ii) e su cui posso reiterare tutto l'ambaradam. Però non posso reiterare all'infinito perché prima o poi finisco i vertici, quindi se il grafo è sempre connesso finirò i vertici di grado 1, ma dalle ipotesi segue che il numero di vertici di grado 1 è uguale a quello di grado 3, quindi la tesi vale se il grafo è connesso.
Vabbè, vale anche se almeno una componente connessa rispetta la (i) e la (ii)...
Supponiamo che almeno una componente connessa del grafo che a sto giro consideriamo sconnesso non rispetti la (i) (è ovvio che la (ii) la rispetta per forza, no?). Anzi, che tutte non la rispettano. Bene, poniamo che in essa il numero di vertici di grado 3 sia maggiore di quello di grado 1. Tanto, visto che per tutto il grafo vale la (i), se è minore vuol dire che da qualche altra parte sia maggiore. Con la solita iterazione leviamo tutti gli 1 e così rimangono solo 2 e 3. Definiamo catena ogni insieme di spigoli e vertici di grado 2 che collega due vertici di grado 3 senza passare per altri vertici di quel gradi. Supponiamo pari il numero di vertici di grado 3. Per ogni coppia di vertici di quel grado leviamo dal grafo la catena che li unisce, se esiste (e se non esiste prendiamo le coppie in un altro modo), le leviamo e di quella componente connessa rimasero solo vertici di grado 2. Il numero di vertici di grado 3 non può essere dispari perché la somma dei gradi dei vertici deve essere pari. Basta, ho finito.
Non è formalissima, ma l'idea è questa
シリオ
$T=\sqrt{\dfrac l g 12\pi}$

Talete
Messaggi: 665
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Grafo malvagio

Messaggio da Talete » 22 mar 2017, 06:27

Sirio ha scritto:Va detto che per deformazione da giochi logici stavo ipotizzando doppi ponti tra i vertici... :lol:
A quanto ne so io si potrebbe fare comunque...

Btw, nel caso in cui è sconnesso: non hai considerato la potenziale presenza di vertici di grado 0, o sbaglio? Il seguente grafo:

Vertici: $\{v_1,v_2,v_3,v_4,v_5\}$
Archi: $\{(v_2,v_3),(v_2,v_4),(v_2,v_5),(v_3,v_4),(v_3,v_5)\}$

rispetta tutte le condizioni del problema, ma ha un vertice ($v_1$) di grado $0$. Come si gestisce?

Bonus question:
Testo nascosto:
Sia $p$ un numero primo.
Sostituire la (i) con "la media dei gradi dei vertici di $\Gamma$ è $2p-2$".
Sostituire la (ii) con "ogni vertice di $\Gamma$ ha grado al massimo $2p-1$".
Sostituire la tesi con "dimostrare che esiste un sottografo $\Gamma'\subseteq \Gamma$ in cui tutti i vertici hanno grado $p$".
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Avatar utente
Sirio
Messaggi: 198
Iscritto il: 08 set 2016, 22:01

Re: Grafo malvagio

Messaggio da Sirio » 22 mar 2017, 06:54

Se ci sono vertici di grado 0 ci deve essere per forza una componente connessa con più gradi 3 che gradi 1 e quindi mi riallaccio alla mia dimostrazione
Testo nascosto:
The Game
シリオ
$T=\sqrt{\dfrac l g 12\pi}$

Talete
Messaggi: 665
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Grafo malvagio

Messaggio da Talete » 22 mar 2017, 19:07

Alright! E della bonus question che dici?
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Avatar utente
Sirio
Messaggi: 198
Iscritto il: 08 set 2016, 22:01

Re: Grafo malvagio

Messaggio da Sirio » 22 mar 2017, 21:48

Dico che la faccia qualcun altro!
シリオ
$T=\sqrt{\dfrac l g 12\pi}$

Talete
Messaggi: 665
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Grafo malvagio

Messaggio da Talete » 23 mar 2017, 19:46

Soluzione $w4g-tamarra (però spero ne esista una decente):
Testo nascosto:
Siano $v_1,\ldots,v_n$ i vertici e siano $e_1,\ldots,e_m$ gli archi. Ricordiamo che $2m$ è uguale alla somma dei gradi dei vertici del grafo, dunque:
\[m=\frac12\cdot\sum_{i=1}^n \deg(v_i)=\frac12\cdot n\cdot (2p-2)=n\cdot(p-1).\] Considero la funzione $f: \mathcal{V}\times \mathcal{E} \rightarrow \{0,1\}$ per cui $f(v_i,e_j)=1$ se l'arco $e_j$ ha come estremità il vertice $v_i$, $f(v_i,e_j)=0$ altrimenti. Adesso, prendiamo $m$ variabili $x_1,\ldots,x_m$ (ciascuna ovviamente associata ad un arco). Consideriamo il seguente polinomio in $m$ variabili:
\[P(x_1,\ldots,x_m):=\prod_{j=1}^m (1-x_j)-\prod_{i=1}^n \left[1-\left(\sum_{j=1}^m f(v_i,e_j)\cdot x_j\right)^{p-1}\right].\]
Perché sto facendo questa roba? Allora, questo è un polinomio di grado $m$ (infatti la prima produttoria ha grado $m$, mentre la seconda ha grado $n\cdot(p-1)$, che fa proprio $m$). Il coefficiente di $x_1\cdot\ldots\cdot x_m$ è $(-1)^m$, e proviene tutto dalla prima produttoria (se quello proveniente dalla seconda produttoria fosse non nullo, vorrebbe dire che ogni vertice appartiene ad ogni arco, impossibile se i vertici sono più di $2$).

E adesso.... KOMBINATORIALNULLSTELLENSATZ!

Dunque, esiste una $m$-upla $(x_1',\ldots,x_m')$ per cui $P(x_1',\ldots,x_m')\neq0$. Notiamo inoltre che $P(0,\ldots,0)=0$, quindi la $m$-upla $(x_1',\ldots,x_m')$ non è tutta nulla. Dunque il prodotto
\[\prod_{j=1}^m (1-x_j)\]
è nullo, e quindi sappiamo che
\[\prod_{i=1}^n \left[1-\left(\sum_{j=1}^m f(v_i,e_j)\cdot x_j\right)^{p-1}\right]\neq0.\hspace{1cm}(\star)\]
Modulo $p$, il valore di
\[\left(\sum_{j=1}^m f(v_i,e_j)\cdot x_j\right)^{p-1}\]
può essere $0$ oppure $1$, da $(\star)$ sappiamo dunque che fa $0$ per ogni vertice.

Consideriamo il sottografo formato da tutti gli archi $e_j$ per cui $x_j=1$. Per quanto detto sopra si deve avere che
\[\sum_{j=1}^m f(v_i,e_j)\equiv0 \pmod{p}.\]
Ma la somma a sinistra è uguale al grado di $v_i$, che quindi, essendo minore o uguale a $2p-1$, può valere o $0$ oppure $p$. Se vale $0$, elimino dal grafo il vertice $v_i$. Dopo aver eliminato tutti gli archi per cui $x_j=0$, e tutti i vertici che dopo questo trattamento hanno grado $0$, rimane un sottografo in cui tutti i vertici hanno grado $p$.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti