Se poate o rezolvare cu explicatie pentru fiecare fel de raspuns?
Răspunsuri la întrebare
Salut :)
Pt. 1: Din afirmatia "lista de adiacenta a fiecarui nod este formata din cel putin 1 element" ne dam seama ca fiecare nod este conectat cu cel putin un altul → graful este conex (daca un nod ar fi izolat,graful nu ar mai fi conex) → ADEVARAT (1)
Pt. 2: Din afirmatia "graf eulerian" si din faptul ca am dem. ca este conex → toate varfurile au grad par.Daca nu am aveam macar un vf cu grad 2 → am avea 10 vf fiecare cu grad 4/6/8...,ceea ce trece cu mult peste 16 muchii,deci va trebui sa avem cel putin un nod de grad 2. →ADEVARAT
Pt. 3: Prin definitie,un graf este hamiltonian daca contine un ciclu hamiltonian(ciclu care contine toate varfurile/nodurile grafului).Definitia mai spune si ca daca gradul fiecărui vârf este mai mare sau egal cu jumătate din numărul de vârfuri,atunci acel graf este hamiltonian.
avem 10 varfuri si 16 muchii,iar fiecare varf va avea cel putin gradul 5.
Daca luam vf 1 cu gradul 5,care sa fie legat de 2,3,4,5,6,asta inseamna ca vf 2 va trebui sa fie legat de inca 4 noduri,de ex 3,4,5,6,7,ceea ce ar inseamna ca 3 ar trebui sa fie legat de inca 3 noduri,de ex 4,5,6,deci 4 ar trebui ;egat de inca 2 noduri...5 de inca unul....etc...deci trecem peste 1+2+3+4+5=15 noduri,avand in vedere ca pe 7,8,9,10 nici nu le-am legat.Deci e clar ca muchiile trec peste 16. → FALS
Pt. 4: Am gasit un exemplu de graf cu 16 muchii care sa nu aibă ciclu elementar de lungime 3,deci logic ar fi ca afirmatia sa fie adevarata(poza 2) :) → ADEVARAT (2)
rezulta 2 afirmatii adevarate
