Grafi - Ciclo
Ciao a tutti,
tra i vari esercizi mi è capitato questo qui
La mia risposta è: sì è vero che contiene un ciclo perchè se ogni vertice ha grado >=2 significa che il minimo grafo che posso avere è un grafo con 3 vertici (perchè ognuno deve essere di grado 2) e quindi si crea un ciclo. Ovviamente se il numero dei vertici è maggiore, allora ci sarà sicuramente un ciclo contenuto nel grafo G.
Che ne dite? è giusta come risposta?
Grazie
tra i vari esercizi mi è capitato questo qui
Sia G un grafo in cui ogni vertice ha grado >= 2. E’ vero o no che G contiene un ciclo e perchè?
La mia risposta è: sì è vero che contiene un ciclo perchè se ogni vertice ha grado >=2 significa che il minimo grafo che posso avere è un grafo con 3 vertici (perchè ognuno deve essere di grado 2) e quindi si crea un ciclo. Ovviamente se il numero dei vertici è maggiore, allora ci sarà sicuramente un ciclo contenuto nel grafo G.
Che ne dite? è giusta come risposta?
Grazie
Risposte
Non mi sembra male, però io la affronterei così :
Parto da un vertice qualsiasi v0. Scelgo un arco tra gli almeno due possibili e vado avanti arrivando a v1. Il grado è maggiore o uguale a due, vuol dire che esiste un altro arco differente da quello già percorso. Così arrivo ad un v2 diverso dai precedenti. Procedendo così mi troverò per forza, prima o poi, a passare per un vertice già toccato, essendo il numero dei vertici finito.
Che ne dici ?
Parto da un vertice qualsiasi v0. Scelgo un arco tra gli almeno due possibili e vado avanti arrivando a v1. Il grado è maggiore o uguale a due, vuol dire che esiste un altro arco differente da quello già percorso. Così arrivo ad un v2 diverso dai precedenti. Procedendo così mi troverò per forza, prima o poi, a passare per un vertice già toccato, essendo il numero dei vertici finito.
Che ne dici ?
dico che mi piace di più la tua 
grazie mille Sigma1
grazie mille Sigma1
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo