Esercizio sui grafi
Dimostrare che dato un grafo G=(V,L) se il grado minimo fra i suoi vertici è (n-1)/2 , allora G è connesso.
Come si fa a dimostrare?
A me risulta fals aquesta espressione, in un grafo connesso L>=V-1
Se il grado minimo fra i gradi dei suoi vertici è (n-1)/2, siccome il grafo ha n vertici, la sommatoria fra tutti i gradi di tutti i vertici del grafo da un risultato maggiore o uguale di (n-1)n / 2 , perchè ha n vertici e ogni vertice ha almeno (n-1)/2 come grado.
Per cui siccome 2 L = sommatoria fra tutti i gradi di tutti i vertici, ricavo che (n^2 - n)/4 è il minimo numero di lati del grafo.
Per essere connesso il grafo soddisfare la disuguaglianza L>=V-1
Cioè n^2 -2 >= 4n -4
Ma questa disuguaglianza non è verificata per tutti gli n, ad esempio non è verificata per n=3.
Ho sbagliato qualcosa nei conti? In teoria la condizione dovrebbe risultare vera...
Come si fa a dimostrare?
A me risulta fals aquesta espressione, in un grafo connesso L>=V-1
Se il grado minimo fra i gradi dei suoi vertici è (n-1)/2, siccome il grafo ha n vertici, la sommatoria fra tutti i gradi di tutti i vertici del grafo da un risultato maggiore o uguale di (n-1)n / 2 , perchè ha n vertici e ogni vertice ha almeno (n-1)/2 come grado.
Per cui siccome 2 L = sommatoria fra tutti i gradi di tutti i vertici, ricavo che (n^2 - n)/4 è il minimo numero di lati del grafo.
Per essere connesso il grafo soddisfare la disuguaglianza L>=V-1
Cioè n^2 -2 >= 4n -4
Ma questa disuguaglianza non è verificata per tutti gli n, ad esempio non è verificata per n=3.
Ho sbagliato qualcosa nei conti? In teoria la condizione dovrebbe risultare vera...
Risposte
Tu non hai dimostrato che la proposizione è falsa, semplicemente non hai dimostrato che è vera.
Ma la proposizione è infatti vera: supponiamo per assurdo che G sia disconnesso. Di conseguenza esiste una componente connessa con un numero di vertici minore o uguale a $n/2$. Ne consegue che il grado massimo dei vertici di tale componente è al più $n/2 - 1$, violando l'ipotesi iniziale che il grado di un qualsiasi vertice sia almeno $(n-1)/2$ poiché ovviamente $n/2 - 1 < (n-1)/2$.
EDIT: hai sbagliato sezione comunque.
Ma la proposizione è infatti vera: supponiamo per assurdo che G sia disconnesso. Di conseguenza esiste una componente connessa con un numero di vertici minore o uguale a $n/2$. Ne consegue che il grado massimo dei vertici di tale componente è al più $n/2 - 1$, violando l'ipotesi iniziale che il grado di un qualsiasi vertice sia almeno $(n-1)/2$ poiché ovviamente $n/2 - 1 < (n-1)/2$.
EDIT: hai sbagliato sezione comunque.
Non ho capito bene questa dimostrazione.
Perchè se G è disconnesso allora deve esistere una parte connessa con almeno n/2 vertici?
E non ho capito la conclusione,puoi essere più chiaro?
Perchè se G è disconnesso allora deve esistere una parte connessa con almeno n/2 vertici?
E non ho capito la conclusione,puoi essere più chiaro?
[mod="Martino"]Sposto in "Algebra, logica, teoria dei numeri e matematica discreta".[/mod]
Mi è venuta in mente una cosa, mi sono detto "e se lo dimostrassi per induzione?".
Ho provato a dimostrarlo, vorrei sapere se il mio ragionamento è corretto.
Il minimo grado di tutti i vertici è (n-1)/2
Il che significa che se faccio la sommatoria tra tutti i gradi di tutti i vertici ottengo come minimo (n^2 -n)/2
Ora sappiamo che in un grafo 2|L|=sommatoria di tutti i gradi di tutti i vertici
Quindi sappiamo che il minimo numero di lati è uguale a (n^2 -n)/4
Ora dimostro che ciò è valdio per n=2.
Infatti se n=2, il grafo sarà connesso se possiede almeno 1 lato.
(2^2 -1)/4=3/4, ciò significa che il numero di lati è maggiore o uguale a 3/4, ma essendo il grado un elemento che appartiene a N, può essere solo un intero per cui sicuramente |L|>=1, per cui ho dimostrato che ciò è valido per n=2.
Ora secondo l' ipotesi di induzione, se |L| >= (n^2 -n)/4 , allora il grafo è connesso.
Ora vedo cosa succede per n+1:
[(n+1)^2-(n+1)]/4 = (n^2 +n)/4 = (n^2-n)/4 + 2n/4 = |L|
Ciò significa che se ho n+1 vertici,|L| = |L-1| +2n/4, dove |L-1| indica il numero i lati che ha tale grafo con n-1 vertici.
Ma 2n/4 è sicuramente maggiore di 1 perchè n>2, allora ne concludo che, partendo da un grafo connesso, se aumento di 1 il numero di vertici, allora il numero di lati aumenta di almeno 1, il che porterebbe ancora a un grafo connesso.
Se io ho un grafo connesso, gli aumento di 1 il numeri di vertici e di 1 il numerod i lati, ottengo ancora un graof connesso, giusto?
Ho provato a dimostrarlo, vorrei sapere se il mio ragionamento è corretto.
Il minimo grado di tutti i vertici è (n-1)/2
Il che significa che se faccio la sommatoria tra tutti i gradi di tutti i vertici ottengo come minimo (n^2 -n)/2
Ora sappiamo che in un grafo 2|L|=sommatoria di tutti i gradi di tutti i vertici
Quindi sappiamo che il minimo numero di lati è uguale a (n^2 -n)/4
Ora dimostro che ciò è valdio per n=2.
Infatti se n=2, il grafo sarà connesso se possiede almeno 1 lato.
(2^2 -1)/4=3/4, ciò significa che il numero di lati è maggiore o uguale a 3/4, ma essendo il grado un elemento che appartiene a N, può essere solo un intero per cui sicuramente |L|>=1, per cui ho dimostrato che ciò è valido per n=2.
Ora secondo l' ipotesi di induzione, se |L| >= (n^2 -n)/4 , allora il grafo è connesso.
Ora vedo cosa succede per n+1:
[(n+1)^2-(n+1)]/4 = (n^2 +n)/4 = (n^2-n)/4 + 2n/4 = |L|
Ciò significa che se ho n+1 vertici,|L| = |L-1| +2n/4, dove |L-1| indica il numero i lati che ha tale grafo con n-1 vertici.
Ma 2n/4 è sicuramente maggiore di 1 perchè n>2, allora ne concludo che, partendo da un grafo connesso, se aumento di 1 il numero di vertici, allora il numero di lati aumenta di almeno 1, il che porterebbe ancora a un grafo connesso.
Se io ho un grafo connesso, gli aumento di 1 il numeri di vertici e di 1 il numerod i lati, ottengo ancora un graof connesso, giusto?
"ramy1989":
Dimostrare che dato un grafo G=(V,L) se il grado minimo fra i suoi vertici è (n-1)/2 , allora G è connesso.
Cosa è $n$, il numero dei vertici? A me sembra falso.
"ramy1989":
Perchè se G è disconnesso allora deve esistere una parte connessa con almeno n/2 vertici?
E dove mai l'ho scritto? Ho scritto che se G è disconnesso esiste una componente connessa con al più $n/2$ vertici. Il perché è banale: se una componente ha più di $n/2$ vertici le altre componenti devono avere per forza meno di $n/2$ vertici.
E non ho capito la conclusione,puoi essere più chiaro?
Che cosa esattamente non ti è chiaro? Ho dimostrato che se il grafo è disconnesso il grado minimo è inferiore a $(n-1)/2$, ma ciò contraddice l'ipotesi iniziale che ogni nodo abbia grado almeno uguale a $(n-1)/2$.
Se io ho un grafo connesso, gli aumento di 1 il numeri di vertici e di 1 il numerod i lati, ottengo ancora un graof connesso, giusto?
Non è detto: puoi lasciare il nuovo vertice completamente disconnesso e inserire un lato tra due nodi del grafo originale
@Rggb: perché falso? Hai trovato qualche controesempio? A me pare di averla dimostrata correttamente.
EDIT: ho controllato su un libro e la proposizione è corretta. Credo anche la mia dimostrazione.
@Deckard
Anzitutto, cosa prendere come valore di grado minimo se $n$ è pari? [Ma forse non ci interessa]
Per il resto, credo mi sia lasciato sviare da un problema di terminologia, perché quello che voi qui chiamate grafo per me è un grafo semplice, tutto qui.
Anzitutto, cosa prendere come valore di grado minimo se $n$ è pari? [Ma forse non ci interessa]
Per il resto, credo mi sia lasciato sviare da un problema di terminologia, perché quello che voi qui chiamate grafo per me è un grafo semplice, tutto qui.
"Rggb":
@Deckard
Anzitutto, cosa prendere come valore di grado minimo se $n$ è pari? [Ma forse non ci interessa]
No infatti non ci interessa poiché è solo una limitazione inferiore, ovviamente se n è pari il grado minimo $delta(G)$ sarà maggiore o uguale a $n/2$.
Sì, la proposizione corretta dovrebbe essere "Dimostrare che dato un grafo G=(V,L) se il grado minimo fra i suoi vertici è maggiore o uguale a (n-1)/2 , allora G è connesso." L'avevo dato per scontato, ma in effetti altrimenti per $n$ pari non ha senso.
Per il resto, credo mi sia lasciato sviare da un problema di terminologia, perché quello che voi qui chiamate grafo per me è un grafo semplice, tutto qui.
Ah, ok.
Comunque non l' hai dimostrato, nella dimostrazione per assurdo violi la condizione che il grado minimo sia (n-1)/2.
Hai detto che se un grafo per assurdo è disconnesso, allora il grado minimo è minore uguale di n/2, ma la condizione è che era maggiore o uguale di (n+1)/2.
Nella dimostrazione per assurdo dovevi considerare questa condizione, non la condizione opposta, sennò non è più una dimostrazione per assurdo.
E' come se dico se a
Non so come spiegarmi, hai capito?
Hai detto che se un grafo per assurdo è disconnesso, allora il grado minimo è minore uguale di n/2, ma la condizione è che era maggiore o uguale di (n+1)/2.
Nella dimostrazione per assurdo dovevi considerare questa condizione, non la condizione opposta, sennò non è più una dimostrazione per assurdo.
E' come se dico se a
Non so come spiegarmi, hai capito?
Io per assurdo affermo che, soddisfatte le ipotesi sul grado, esistono almeno due componenti connesse; ciò risulta in una negazione dell'ipotesi sul grado minimo. Ergo non possono esistere due componenti connesse indipendenti soddisfando l'ipotesi sul grado minimo.
In pratica ho semplicemente dimostrato che negando la tesi si ha la negazione di una delle ipotesi. È lo schema di ogni dimostrazione per assurdo.
In pratica ho semplicemente dimostrato che negando la tesi si ha la negazione di una delle ipotesi. È lo schema di ogni dimostrazione per assurdo.
Chiedo scusa ma proprio non capisco come fai a concludere che se G è disconnesso, allora di conseguenza esiste una componente connessa con un numero di vertici minore o uguale a n/2 
E poi un' alktra cosa: riguarda alla mia dimostrazione per induzione hai detto:
"Non è detto: puoi lasciare il nuovo vertice completamente disconnesso e inserire un lato tra due nodi del grafo originale "
Però la condizione che il grado minimo sia (n-1)/2 smentisce il fatto che il nuovo vertice possa essere disconnesso.
Grazie per la pazienza.
"Non è detto: puoi lasciare il nuovo vertice completamente disconnesso e inserire un lato tra due nodi del grafo originale "
Però la condizione che il grado minimo sia (n-1)/2 smentisce il fatto che il nuovo vertice possa essere disconnesso.
Grazie per la pazienza.
"ramy1989":
Chiedo scusa ma proprio non capisco come fai a concludere che se G è disconnesso, allora di conseguenza esiste una componente connessa con un numero di vertici minore o uguale a n/2
Poniamoci nel caso di solo due componenti, se ce ne sono di più ancora meglio, l'argomento si fa più forte.
Se ci sono due componenti connesse vuol dire che devo dividere l'insieme dei vertici fra due componenti, una avrà $a$ vertici, l'altra $n - a$. Ma allora se $a<=n/2$ vuol dire che è la prima componente ad avere al più $n/2$ vertici. Se invece $a > n/2$ allora la seconda avrà $n-a<=n-n/2=n/2$ vertici.
In sostanza se dividi i vertici in più componenti, ce ne sarà sempre una con al più la metà dei vertici perché se una ha più di metà dei vertici ti rimangono meno della metà dei vertici da dividere fra le altre componenti.
Spero di essere stato abbastanza chiaro ora.
"ramy1989":
E poi un' alktra cosa: riguarda alla mia dimostrazione per induzione hai detto:
"Non è detto: puoi lasciare il nuovo vertice completamente disconnesso e inserire un lato tra due nodi del grafo originale "
Però la condizione che il grado minimo sia (n-1)/2 smentisce il fatto che il nuovo vertice possa essere disconnesso.
Grazie per la pazienza.
Rispondevo alla tua domanda "Se io ho un grafo connesso, gli aumento di 1 il numeri di vertici e di 1 il numerod i lati, ottengo ancora un graof connesso, giusto?". La risposta a questa domanda è no.
La tua dimostrazione non mi torna perchè $|L|>=(n^2-n)/2$ non implica necessariamente che il grafo sia connesso. E inoltre durante la dimostrazione usi $|L-1| = (n^2-n)/4$ dove, a parte l'errore formale (L-1 scritto così non ha senso, ma immagino intendessi il numero di lati del grafo con n vertici), l'ipotesi corretta è che $|L-1| >= (n^2-n)/4$ e questo smonta il tuo ultimo punto.
Ora ho capito, supponi che il grafo essendo disconnesso, abbia due o più parti connesse.
Se le parti connesse sono due, allora ogni vertice ha al massimo (n/2)-1 come grado, ciò viola la condizione che il grado minimo sia (n-1)/2.Grazie per la pazienza.
Se le parti connesse sono due, allora ogni vertice ha al massimo (n/2)-1 come grado, ciò viola la condizione che il grado minimo sia (n-1)/2.Grazie per la pazienza.
Solo un' ultima domanda: se un grafo G=(V,L) è denso, vale la relazione |L|<|V|^2 o |V|<|L|^2 ?
Il concetto di grafo denso (e sparso) non ha una vera e propria definizione o meglio, varia da contesto a contesto.
Di certo la prima delle due non può andar bene perchè per grafi semplici è sempre verificata, infatti vale $|L| <= ( ( |V| ),( 2 ) ) < |V|^2$.
Di solito per grafo denso s'intende un grafo t.c. $|L|=Ɵ(|V|^2)$ ovvero che il numero di lati è dell'ordine di grandezza del quadrato del numero dei vertici. Però appunto, dipende dal contesto, non esiste una definizione univoca.
Di certo la prima delle due non può andar bene perchè per grafi semplici è sempre verificata, infatti vale $|L| <= ( ( |V| ),( 2 ) ) < |V|^2$.
Di solito per grafo denso s'intende un grafo t.c. $|L|=Ɵ(|V|^2)$ ovvero che il numero di lati è dell'ordine di grandezza del quadrato del numero dei vertici. Però appunto, dipende dal contesto, non esiste una definizione univoca.
E' possibile una definizione che sia |V|=O(|L|^2)? Io ho questa sugli appunti ma mi sorge il ubbio che sia sbagliata.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo