Bine aţi venit pe Scientia QA!
Pentru a putea publica întrebări şi răspunsuri, trebuie să vă înregistraţi.
Atenţie! Este posibil ca e-mailul de confirmare a înregistrării să intre în Spam.
Pune o întrebare

Newsletter


3.5k intrebari

6.7k raspunsuri

15.2k comentarii

2.2k utilizatori

0 plusuri 0 minusuri
601 vizualizari

Mă refer exclusiv la una dintre problemele pe care personajul interpretat de Matt Damon le rezolvă pe parcursul filmului, cea din imaginea de mai jos.

Aveți idee despre ce problemă este vorba și ce grad de dificultate are?

Senior (7k puncte) in categoria Matematica

1 Raspuns

1 plus 0 minusuri
Problema din film este una de teoria grafurilor. In teoria grafurilor se considera o multime de noduri si muchii intre nodurile respective. O configuratie de acest gen se numeste graf. Un graf fara cicluri se numeste arbore, iar ciclul e un drum pe muchiile din graf pe care se revine intr-un nod.

Gradul unui nod reprezinta numarul de muchii incidente in acel nod.

Problema cere sa se reprezinte arbori distincti fara noduri de grad 2 pentru n=10 noduri. Arborele de acest gen e un gen de arbore decizional; mai exact, daca te deplasezi pe muchiile din arbore si ajungi intr-un nod ai cel putin 2 optiuni de alegere a continuarii drumului. De aceea se exclud cei de grad 2.

Termenul ”homeomorfic” se refera la faptul ca, structural, arborii nu pot fi obtinuti din izometrii, adica rotatii, simetrie sau translatie.

Dificultatea nu e asa mare, mai greu fiind sa arati ca acele figuri sunt toate configuratiile posibile, dar si asta se face relativ usor daca se tine seama de gradele nodurilor.
Experimentat (2.3k puncte)
editat de
0 0
Din videoclipul de mai jos rezultă că există 10 asemenea configurații. Dar nu se oferă o demonstrație. Cred că ar fi interesant dacă am putea cumva defini acest gen de arbori de care vorbiți prin intermediul unei structuri de date, ale cărei posibile valori să le aflăm cu un program de computer. O să arunc o privire pe internet să văd dacă găsesc ceva în acest sens.

0 0
Am găsit o rezolvare care poate fi înțeleasă de oricine:

http://sierra.nmsu.edu/morandi/oldwebpages/math210Fall2014/Lectures/Good%20Will%20Hunting-web.pdf

Dacă cineva are o idee pentru modelarea matematică a problemei și rezolvarea cu ajutorul computerului, ar fi nemaipomenit.
...