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$.
Grafo malvagio
Grafo malvagio
"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
"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
Re: Grafo malvagio
Va detto che per deformazione da giochi logici stavo ipotizzando doppi ponti tra i vertici...
Non è formalissima, ma l'idea è questa
Testo nascosto:
$T=\sqrt{\dfrac l g 12\pi}$
Re: Grafo malvagio
A quanto ne so io si potrebbe fare comunque...Sirio ha scritto:Va detto che per deformazione da giochi logici stavo ipotizzando doppi ponti tra i vertici...
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:
"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
"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
Re: Grafo malvagio
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:
$T=\sqrt{\dfrac l g 12\pi}$
Re: Grafo malvagio
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
"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
Re: Grafo malvagio
Soluzione $w4g-tamarra (però spero ne esista una decente):
Testo nascosto:
"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
"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