Teoria grafurilor este folosit pentru a rezolva problemele de mai multe domenii: matematică, biologie, informatică
Îmi place proiectul ca 20 de participanți
1736, g.Konigsberg. Prin oraș curge râul pregelului. Orașul - șapte poduri, dispuse după cum se arată în figura de mai sus. Din cele mai vechi timpuri, locuitorii din Königsberg luptat cu un mister: dacă este posibil să treacă pe toate podurile, fiecare având doar o singură dată? Această problemă este rezolvată în teorie și pe suport de hârtie, cât și în practică, la plimbare - care trece chiar pe acest pod. Nimeni nu a fost în măsură să dovedească faptul că acest lucru nu este posibil, dar, de asemenea, pentru a face o astfel de „misterios“ nimeni nu putea să meargă peste poduri.
Pentru a rezolva problema a fost celebrul matematician Leonardu Eyleru. Și el a decis să nu numai la această problemă specială, dar a venit cu o metodă generală pentru rezolvarea unor astfel de probleme. În rezolvarea problemei Koenigsberg poduri Euler a intrat după cum urmează: acesta este „stors“ în punctele de teren și poduri, „întins“, în linie. O cifră care constă din puncte și linii de legătură aceste puncte, numite grafen.
Count - un set de set nevida de vârfuri și conexiunile dintre noduri. Cani sunt numite nodurile, liniile cu săgeți - arce, fără săgeți - margini.
Graficul 1.Orientirovanny (digraph scurt) - margini care sunt atribuite pe direcția.
2.Neorientirovanny grafic - un grafic. în care nu există linii de direcție.
3. grafic Ponderat - arce sau muchii au greutate (mai multe informații).
Solutia problemelor folosind grafice:
Soluție: lasa oamenii de știință vârfurile graficului și trage o linie de la fiecare nod la patru înălțimi diferite. Obținem 10 linii, care vor fi luate în considerare mâinile.
La școală motive cresc copaci 8: mar, plop, mesteacan, frasin de munte, stejar, artar, zada si pin. Rowan sus larice, mar sus arțar, stejar, mesteacan de mai jos, dar pin mai mare, frasin superior pin, mesteacan, plop de mai jos, si zada peste mere. Se pune copacii de la cel mai mic la cel mai mare.
Nodurile - un copac, un copac indicată de prima literă a numelui. În această sarcină două atitudini: „să fie mai jos“ și „să fie de mai sus“. Luați în considerare raportul „fiind mai mic decât“ și trage săgeți dintr-o mai mică la un nivel mai ridicat de copac. În cazul în care problema spune că cenușa de munte de mai sus laricele, săgeata pentru a pune pe cenușă de munte zada etc. Se obține un grafic, care arată că cea mai mică din lemn - paltin, urmat de măr, zada, frasin de munte, pin, stejar, mesteacan si plop.
Natasha are 2 plicuri: normal și aer, și 3 marca: dreptunghiulară, pătrată și triunghiulară. Cât de multe moduri pot alege plic Natasha și o ștampilă prin poștă o scrisoare?
Mai jos este o analiză sarcină.
