Piccolo rompicapo su scoredi grafo
Ciao ragazzi! Mercoledì ho l'esame di discreta e m'è passato tra le mani questo score che (a detta del docente) da cui dovrei ricavare un "disegno" di albero
d=(1,1,1,1,1,1,1,1,4,4,4)
beh.. le varie ostruzioni che mi vengono in mente perchè questo non sia score di grafo non mi dicono nulla. Anzi, con il teorema dello score si raggiunge poi la creazione del grafo.
Inoltre valutando se è un albero con eulero, ossia |E| = |V|-1 --> 10=11-1 ricavo che la condizione è vera (ammesso che sia connesso..) ed essendo condizione sufficiente e necessaria... perchè non riesco a disegnarlo maledizione?!
Se mi illuminate..
d=(1,1,1,1,1,1,1,1,4,4,4)
beh.. le varie ostruzioni che mi vengono in mente perchè questo non sia score di grafo non mi dicono nulla. Anzi, con il teorema dello score si raggiunge poi la creazione del grafo.
Inoltre valutando se è un albero con eulero, ossia |E| = |V|-1 --> 10=11-1 ricavo che la condizione è vera (ammesso che sia connesso..) ed essendo condizione sufficiente e necessaria... perchè non riesco a disegnarlo maledizione?!
Se mi illuminate..
Risposte
"bertuz":
Ciao ragazzi! Mercoledì ho l'esame di discreta e m'è passato tra le mani questo score che (a detta del docente) da cui dovrei ricavare un "disegno" di albero
d=(1,1,1,1,1,1,1,1,4,4,4)
beh.. le varie ostruzioni che mi vengono in mente perchè questo non sia score di grafo non mi dicono nulla. Anzi, con il teorema dello score si raggiunge poi la creazione del grafo.
Inoltre valutando se è un albero con eulero, ossia |E| = |V|-1 --> 10=11-1 ricavo che la condizione è vera (ammesso che sia connesso..) ed essendo condizione sufficiente e necessaria... perchè non riesco a disegnarlo maledizione?!
Se mi illuminate..
Sei sicuro di aver verificato le varie ostruzioni esattamente??...Per esempio:
1)Il numero di vertici di grado max (in questo caso 3) dovrebbe essere il grado minimo...ma qui il grado minimo è 1..
2) Il numero di vertici (11) dovrebbe essere <= del grado max e questo non è vero...
3)la somma di due vertici di grado max (4+4=8) dovrebbe essere il numero di vertici di grado >=2 escludendo quelli usati nella somma..
Conseguenza-->d non è lo score di un grafo..
secondo me..poi magari mi sbaglio..
"stefanosteve":
d=(1,1,1,1,1,1,1,1,4,4,4)
Sei sicuro di aver verificato le varie ostruzioni esattamente??...Per esempio:
1)Il numero di vertici di grado max (in questo caso 3) dovrebbe essere il grado minimo...ma qui il grado minimo è 1..
No! I vertici di grado max dovrebbero avere grado 11 per far valere ciò
"stefanosteve":
2) Il numero di vertici (11) dovrebbe essere <= del grado max e questo non è vero...
come no? è 4 il grado max
"stefanosteve":
3)la somma di due vertici di grado max (4+4=8) dovrebbe essere il numero di vertici di grado >=2 escludendo quelli usati nella somma..
non era nr vertici di grado >=2 deve essere almeno 4+4-11 ?
"stefanosteve":
Conseguenza-->d non è lo score di un grafo..
magari!! :/ Inoltre se fai il teorema dello score raggiungi senza problema la conclusione che questo un grafo lo è eccome! Il problema è relativo proprio all'albero
"bertuz":
[quote="stefanosteve"]
d=(1,1,1,1,1,1,1,1,4,4,4)
Sei sicuro di aver verificato le varie ostruzioni esattamente??...Per esempio:
1)Il numero di vertici di grado max (in questo caso 3) dovrebbe essere il grado minimo...ma qui il grado minimo è 1..
No! I vertici di grado max dovrebbero avere grado 11 per far valere ciò
[/quote]
Appunto,quindi visto che non vale questa ostruzione d non è score di un grafo..l'ostruzione dice che d può essere lo score di un grafo se e solo se il numero di vertici di grado massimo è il grado minimo..e questa non è verificata
"bertuz":
[quote="stefanosteve"]
2) Il numero di vertici (11) dovrebbe essere <= del grado max e questo non è vero...
come no? è 4 il grado max
[/quote]
Qui mi sono sbagliato, è il grado max (4) che deve essere <= 11-1 e questa è verificata..
"bertuz":
[quote="stefanosteve"]
3)la somma di due vertici di grado max (4+4=8) dovrebbe essere il numero di vertici di grado >=2 escludendo quelli usati nella somma..
non era nr vertici di grado >=2 deve essere almeno 4+4-11 ?
[/quote]
Hai ragione anche qua..è 4+4-11 e viene -3 e questi sono i vertici di grado >=2...anche se non so come interpretare quel -3
"bertuz":
[quote="stefanosteve"]
Conseguenza-->d non è lo score di un grafo..
magari!! :/ Inoltre se fai il teorema dello score raggiungi senza problema la conclusione che questo un grafo lo è eccome! Il problema è relativo proprio all'albero
[/quote] Secondo me non è ancora uno score di un grafo..perchè la prima ostruzione non è esatta
"stefanosteve":
No! I vertici di grado max dovrebbero avere grado 11 per far valere ciò
Appunto,quindi visto che non vale questa ostruzione d non è score di un grafo..l'ostruzione dice che d può essere lo score di un grafo se e solo se il numero di vertici di grado massimo è il grado minimo..e questa non è verificata
No. L'ostruzione è applicabile solo se il vertice di grado max è n-1. Altrimenti non vale. Ma comunque lo score E' un grafo (applica il teorema dello score e lo riuscirai a fare). Il problema è se è un ablero. Tutto lì!
"bertuz":
[quote="stefanosteve"]
No! I vertici di grado max dovrebbero avere grado 11 per far valere ciò
Appunto,quindi visto che non vale questa ostruzione d non è score di un grafo..l'ostruzione dice che d può essere lo score di un grafo se e solo se il numero di vertici di grado massimo è il grado minimo..e questa non è verificata
No. L'ostruzione è applicabile solo se il vertice di grado max è n-1. Altrimenti non vale. Ma comunque lo score E' un grafo (applica il teorema dello score e lo riuscirai a fare). Il problema è se è un ablero. Tutto lì![/quote]
Ma come mai dici che è lo score di un grafo anche se non verifica l'ostruzione?..ho provato a disegnarlo e viene però io mi sarei fermato prima visto che non verificava quell'ostruzione.cmq per quanto riguarda l'albero basta controllare se è connesso, e se lo è non può essere un albero..per verificare che è connesso basta verificare che gradomin <=|V|-gradomax-1 in questo caso 1<=11-4-1, questa è verificata quindi il grafo è connesso..
"stefanosteve":
Ma come mai dici che è lo score di un grafo anche se non verifica l'ostruzione?..ho provato a disegnarlo e viene però io mi sarei fermato prima visto che non verificava quell'ostruzione.cmq per quanto riguarda l'albero basta controllare se è connesso, e se lo è non può essere un albero..per verificare che è connesso basta verificare che gradomin <=|V|-gradomax-1 in questo caso 1<=11-4-1, questa è verificata quindi il grafo è connesso..
Bene, è un albero? Prova a disegnarlo...
"bertuz":
[quote="stefanosteve"]
Ma come mai dici che è lo score di un grafo anche se non verifica l'ostruzione?..ho provato a disegnarlo e viene però io mi sarei fermato prima visto che non verificava quell'ostruzione.cmq per quanto riguarda l'albero basta controllare se è connesso, e se lo è non può essere un albero..per verificare che è connesso basta verificare che gradomin <=|V|-gradomax-1 in questo caso 1<=11-4-1, questa è verificata quindi il grafo è connesso..
Bene, è un albero? Prova a disegnarlo...[/quote]
Ma no, ho scritto sopra che se è connesso non è un albero..e visto che quello è connesso non può essere un albero..
Ma spiegami perchè come fa ad essere lo score di un grafo anche se un'ostruzione non è verificata..
"stefanosteve":
[quote="bertuz"][quote="stefanosteve"]
Ma come mai dici che è lo score di un grafo anche se non verifica l'ostruzione?..ho provato a disegnarlo e viene però io mi sarei fermato prima visto che non verificava quell'ostruzione.cmq per quanto riguarda l'albero basta controllare se è connesso, e se lo è non può essere un albero..per verificare che è connesso basta verificare che gradomin <=|V|-gradomax-1 in questo caso 1<=11-4-1, questa è verificata quindi il grafo è connesso..
Bene, è un albero? Prova a disegnarlo...[/quote]
Ma no, ho scritto sopra che se è connesso non è un grafo..e visto che quello è connesso non può essere un albero..
Ma spiegami perchè come fa ad essere lo score di un grafo anche se un'ostruzione non è verificata..[/quote]
EEEEE? Se E' connesso non è un albero? Ma se un albero è CONNESSO e ACICLICO per definizione!!
L'ostruzione come la applichi tu è sbagliata, per applicarla il vertice/i di grado max dello score devono valere n-1. In questo caso nessun deg vale n-1, perciò una condizione necessaria per verificare tale ostruzione manca e non si può dir nulla.
La mia domanda originaria rimane ancora enza risposta. Se qualcuno ha qualche soluzione..
ok ci sono riuscito 
.Rimane da risolvere il fatto come non riesca a costruire l'albero procedendo a ritrovo con il teorema dello score.. stranissimo!!
[/img]
.Rimane da risolvere il fatto come non riesca a costruire l'albero procedendo a ritrovo con il teorema dello score.. stranissimo!![/img]
"bertuz":
EEEEE? Se E' connesso non è un albero? Ma se un albero è CONNESSO e ACICLICO per definizione!!
L'ostruzione come la applichi tu è sbagliata, per applicarla il vertice/i di grado max dello score devono valere n-1. In questo caso nessun deg vale n-1, perciò una condizione necessaria per verificare tale ostruzione manca e non si può dir nulla.
Si scusa, un albero per definizione è connesso e senza cicli..cmq ho provato a disegnarlo e a me viene fuori un albero..praticamente sono tre croci tutte collegate..cosi: +++..questo dovrebbe essere un albero..è connesso e non ha cicli..o sbaglio anche sta volta?
Cmq ho ancora una perplessità..ci sono 4 ostruzione per verificare se d è score di un grafo..se le verifico tutte sono sicuro che quello è uno score di un grafo..ma se una o più di una non sono verificate quello non dovrebbe essere più uno score di un grafo o sbaglio?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo