Grafo connesso
Salve ragazzi,
ho questo esercizio
Io procederei in questo modo:
Sia $ G = (V, E, I ) $ G è connesso e la sua taglia è $ |V | − 1 $
in questo caso potremmo avere che $n=2$ per cui $m<=2-2$ quindi $m=0$
questo significa che $|V | − 1 = 0$ cioè che $|V | = − 1 $
e per questo posso dire che G non è connesso per $n=2$ ma potrebbe esserlo per $n>2$
secondo voi è giusta come soluzione? oppure ho detto una boiata?
grazie a tutti come sempre
ho questo esercizio
Sia G un grafo di ordine $n >= 2$ e supponiamo che abbia taglia $ m<= n-2 $. Può essere connesso? (motivare la risposta).
Io procederei in questo modo:
Sia $ G = (V, E, I ) $ G è connesso e la sua taglia è $ |V | − 1 $
in questo caso potremmo avere che $n=2$ per cui $m<=2-2$ quindi $m=0$
questo significa che $|V | − 1 = 0$ cioè che $|V | = − 1 $
e per questo posso dire che G non è connesso per $n=2$ ma potrebbe esserlo per $n>2$
secondo voi è giusta come soluzione? oppure ho detto una boiata?
grazie a tutti come sempre
Risposte
Un suggerimento per il futuro: se usi terminologia non universale è bene chiarirla (altrimenti ti giochi molti degli utenti che avrebbero voglia di risponderti). Per "taglia" intendi il numero di spigoli immagino.
L'idea che vedo è procedere per induzione su [tex]n[/tex]. Supponiamo che G sia connesso e abbia taglia [tex]m \leq n-2[/tex]. Allora dal fatto che la somma delle valenze dei vertici è uguale al doppio della taglia segue facilmente che c'è almeno un vertice di valenza 1. Ora eliminando tale vertice e il relativo spigolo otteniamo un grafo di ordine [tex]n-1[/tex] e taglia [tex]m-1 \leq (n-2)-1 = (n-1)-2[/tex], e ora si può usare l'induzione. L'idea è che per rendere un grafo sconnesso connesso non basta aggiungere un vertice a valenza 1 (guarda le componenti connesse).
L'idea che vedo è procedere per induzione su [tex]n[/tex]. Supponiamo che G sia connesso e abbia taglia [tex]m \leq n-2[/tex]. Allora dal fatto che la somma delle valenze dei vertici è uguale al doppio della taglia segue facilmente che c'è almeno un vertice di valenza 1. Ora eliminando tale vertice e il relativo spigolo otteniamo un grafo di ordine [tex]n-1[/tex] e taglia [tex]m-1 \leq (n-2)-1 = (n-1)-2[/tex], e ora si può usare l'induzione. L'idea è che per rendere un grafo sconnesso connesso non basta aggiungere un vertice a valenza 1 (guarda le componenti connesse).
"Martino":
Un suggerimento per il futuro: se usi terminologia non universale è bene chiarirla (altrimenti ti giochi molti degli utenti che avrebbero voglia di risponderti). Per "taglia" intendi il numero di spigoli immagino.
Per la verità non sapevo di usare una terminologia non universale, "taglia" è quello che c'è scritto negli appunti del prof
Ora provo a studiarmi questa soluzione che hai dato e spero di capirci qualcosa
in ogni caso grazie mille per la risposta
Dalle dispense del prof leggo che:
Sia $ G=(V,E,I) $
• Il numero $ |V| $ si dice l’ordine del grafo;
• il numero $ |E| $ si dice la taglia del grafo;
quindi sì Martino penso che tu abbia ragione si tratta del numero di spigoli
Continuo però a non capire come procedere
questo significa che per ogni vertice del grafo ci sono 2 archi? e se fossero 3? non mi è molto chiaro ma quando scrivi
forse capisco che la valenza dei vertici di cui parli è il suo ordine? giusto?
se su $m<= (n-1)-2$ uso l'induzione, il passo base mi porta ad avere $m<= -3$ ha senso? oppure non ho capito nulla della soluzione che hai proposto?
scusami se faccio tante domande ma vorrei capire e grazie cmq per il tuo tempo
Sia $ G=(V,E,I) $
• Il numero $ |V| $ si dice l’ordine del grafo;
• il numero $ |E| $ si dice la taglia del grafo;
quindi sì Martino penso che tu abbia ragione si tratta del numero di spigoli
Continuo però a non capire come procedere
Allora dal fatto che la somma delle valenze dei vertici è uguale al doppio della taglia segue facilmente che c'è almeno un vertice di valenza 1
questo significa che per ogni vertice del grafo ci sono 2 archi? e se fossero 3? non mi è molto chiaro ma quando scrivi
Ora eliminando tale vertice e il relativo spigolo otteniamo un grafo di ordine $n−1$
forse capisco che la valenza dei vertici di cui parli è il suo ordine? giusto?
se su $m<= (n-1)-2$ uso l'induzione, il passo base mi porta ad avere $m<= -3$ ha senso? oppure non ho capito nulla della soluzione che hai proposto?
scusami se faccio tante domande ma vorrei capire
e grazie cmq per il tuo tempo
Ciao!
[tex]d(v)[/tex] è il grado (o valenza) del vertice [tex]v[/tex], cioè il numero di spigoli che escono da quel vertice. Se c'è un vertice di grado zero allora è isolato e il grafo è sconnesso e abbiamo finito. Se tutti i vertici avessero grado almeno 2 allora si avrebbe
[tex]m = \frac{1}{2} \sum_{v \in V} d(v) \geq \frac{1}{2} 2|V| = n[/tex]
e questo contraddice l'ipotesi [tex]m \leq n-2[/tex]. Quindi c'è almeno un vertice di grado 1.
forse capisco che la valenza dei vertici di cui parli è il suo ordine? giusto?[/quote]Per "valenza" di un vertice intendo il suo grado, cioè il numero di spigoli che escono da quel vertice.
"duombo":No, ho solo usato questo risultato (sto leggendo qui):Allora dal fatto che la somma delle valenze dei vertici è uguale al doppio della taglia segue facilmente che c'è almeno un vertice di valenza 1
questo significa che per ogni vertice del grafo ci sono 2 archi? e se fossero 3?
[tex]d(v)[/tex] è il grado (o valenza) del vertice [tex]v[/tex], cioè il numero di spigoli che escono da quel vertice. Se c'è un vertice di grado zero allora è isolato e il grafo è sconnesso e abbiamo finito. Se tutti i vertici avessero grado almeno 2 allora si avrebbe
[tex]m = \frac{1}{2} \sum_{v \in V} d(v) \geq \frac{1}{2} 2|V| = n[/tex]
e questo contraddice l'ipotesi [tex]m \leq n-2[/tex]. Quindi c'è almeno un vertice di grado 1.
non mi è molto chiaro ma quando scrivi
[quote]Ora eliminando tale vertice e il relativo spigolo otteniamo un grafo di ordine $n−1$
forse capisco che la valenza dei vertici di cui parli è il suo ordine? giusto?[/quote]Per "valenza" di un vertice intendo il suo grado, cioè il numero di spigoli che escono da quel vertice.
se su $m<= (n-1)-2$ uso l'induzione, il passo base mi porta ad avere $m<= -3$ ha senso? oppure non ho capito nulla della soluzione che hai proposto?Il passo base è [tex]n=2[/tex], [tex]m=0[/tex], che si fa a mano (hai un grafo con due vertici isolati che quindi è sconnesso), io ho proceduto assumendo che sia [tex]n \geq 3[/tex].
Ciao Martino e grazie per le spiegazioni,
se vado di induzione usando $n=2$ come passo base, ottengo che il grafo è sconnesso, visto che la traccia mi parla di $n>=2$ in teoria mi potrei fermare qui, oppure è il caso di continuare?
se vado di induzione usando $n=2$ come passo base, ottengo che il grafo è sconnesso, visto che la traccia mi parla di $n>=2$ in teoria mi potrei fermare qui, oppure è il caso di continuare?
E' il caso di continuare.
rivedendo questo esercizio, ci ho ragionato nuovamente su (anche grazie ad un mio collega di università) ed è venuta fuori una soluzione di questo tipo
se $n=2$ allora $|V|=2$ ed $|E| =2-2=0$
questo significa che il grafo avrà $2$ vertici ma $0$ archi e quindi il grafo che ottengo non è connesso
mentre (visto che la traccia parla di $n>=2$) se $n=4$ allora $|V|=4$ ed $|E|=m<=2$ e anche in questo caso non è connesso perchè disegnando il grafo avrei un grafo di questo genere
[geogebra]
con un vertice isolato
e quindi posso dire che non è connesso
che ne pensate?
se $n=2$ allora $|V|=2$ ed $|E| =2-2=0$
questo significa che il grafo avrà $2$ vertici ma $0$ archi e quindi il grafo che ottengo non è connesso
mentre (visto che la traccia parla di $n>=2$) se $n=4$ allora $|V|=4$ ed $|E|=m<=2$ e anche in questo caso non è connesso perchè disegnando il grafo avrei un grafo di questo genere
[geogebra]
con un vertice isolato
e quindi posso dire che non è connesso
che ne pensate?
L'idea è quella per il caso n=4, ma non basta fare i casi n=2 e n=4, bisogna dimostrare il risultato per ogni possibile [tex]n[/tex]. Io sopra ho suggerito di procedere per induzione dando delle linee guida che vanno solo formalizzate e dettagliate un po' per arrivare alla soluzione.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo