{"id":8819,"date":"2019-09-17T16:45:17","date_gmt":"2019-09-17T13:45:17","guid":{"rendered":"https:\/\/iteach.ro\/experientedidactice\/?p=8819"},"modified":"2019-09-21T11:31:47","modified_gmt":"2019-09-21T08:31:47","slug":"domenii-de-aplicabilitate-ale-teoriei-grafurilor-elemente-pentru-abordari-interdisciplinare","status":"publish","type":"post","link":"https:\/\/iteach.ro\/experientedidactice\/domenii-de-aplicabilitate-ale-teoriei-grafurilor-elemente-pentru-abordari-interdisciplinare","title":{"rendered":"Domenii de aplicabilitate ale teoriei grafurilor. Elemente pentru abord\u0103ri interdisciplinare"},"content":{"rendered":"<p>Grafurile au multiple aplica\u0163ii practice, fiind str\u00e2ns legate de multe ramuri ale matematicii (cercet\u0103ri opera\u0163ionale, teoria grupurilor, teoria numerelor), dar sunt folosite \u015fi ca modele matematice \u00een rezolvarea unor probleme tehnice, economice, etc. Ast\u0103zi, teoria grafurilor este folosit\u0103 \u00een domenii variate: fizic\u0103, chimie, biologie, sociologie, tehnologia comunica\u021biilor, re\u021belele de calculatoare, sisteme de transport, etc. Pentru problemele \u00een care se impune o ierarhizare a informa\u021biilor, astfel \u00eenc\u00e2t anumite elemente s\u0103 fie subordonate altora, este util\u0103 introducerea unei noi structuri de date, \u0219i anume arborele cu r\u0103d\u0103cin\u0103. <!--more--><\/p>\n<p>Arborii cu r\u0103d\u0103cin\u0103 sunt o prezen\u021b\u0103 cotidian\u0103. Cu ajutorul lor se poate construi un arbore genealogic \u0219i, \u00een plus, cea mai mare parte a termenilor folosi\u021bi \u00een limbaj informatic deriv\u0103 de aici.<\/p>\n<p>Teoria grafurilor, la \u00eenceputurile ei, s-a dezvoltat paralel cu algebra. Grafurile au multiple aplica\u0163ii practice, fiind str\u00e2ns legate de multe ramuri ale matematicii (cercet\u0103ri opera\u0163ionale, teoria grupurilor, teoria numerelor), dar sunt folosite \u015fi ca modele matematice \u00een rezolvarea unor probleme tehnice, economice etc.<\/p>\n<p>Prima carte de teoria grafurilor a fost publicat\u0103 de D. K\u00f6nig \u00een 1936, <em>Theorie der endlichen und unendlichen Grphen<\/em>, urmat\u0103 de cartea lui C. Berge din 1957, <em>Th\u00e9orie des graphes et ses applications<\/em>. Marele matematician Grigore Moisil afirma c\u0103: <em>\u201eAzi teoria grafurilor a devenit o disciplin\u0103 major\u0103, de\u0219i nu-\u0219i g\u0103se\u0219te locul \u00eentr-o clasificare dogmatic\u0103 a capitolelor matematicii. Folosirea teoriei grafurilor \u00een domenii variate, de la chimie la economie, de la studiul re\u021belelor electrice la critica textelor \u0219i la politic\u0103, \u00eei dau azi un prestigiu de care cel ce clasific\u0103 \u0219tiin\u021bele trebuie s\u0103 \u021bin\u0103 seama.\u201d<\/em><\/p>\n<p>Numeroase situa\u021bii din via\u021ba cotidian\u0103 pot fi modelate cu ajutorul teoriei grafurilor. Pentru problemele \u00een care se impune o ierarhizare a informa\u021biilor, astfel \u00eenc\u00e2t anumite elemente s\u0103 fie subordonate altora, este util\u0103 introducerea unei noi structuri de date, \u0219i anume<em> arborele cu r\u0103d\u0103cin\u0103<\/em>. Arborii cu r\u0103d\u0103cin\u0103 sunt o prezen\u021b\u0103 cotidian\u0103. Cu ajutorul lor se poate construi un arbore genealogic \u0219i, \u00een plus, cea mai mare parte a termenilor folosi\u021bi \u00een limbaj informatic deriv\u0103 de aici.<\/p>\n<p><strong>Aplica\u021bii \u00een fizic\u0103, chimie, biologie<\/strong><\/p>\n<p>Arborii au fost studia\u021bi intensiv de numero\u0219i matematicieni \u0219i fizicieni, precum matematicianul britanic A.Cayley, pe care l-au interesat aplica\u021biile lor \u00een chimia organic\u0103, de exemplu <em>grafurile chimice<\/em>. \u00cen prezent teoria grafurilor \u0219i arborilor reprezint\u0103 un instrument \u00een modelarea moleculelor \u015fi reac\u0163iilor chimice, domeniu foarte interesant, aflat la grani\u0163a dintre chimie, biologie\u00a0 \u015fi matematic\u0103. <em>Institutul Na\u021bional de Cercetare-Dezvoltare pentru Tehnologii Izotopice \u0219i Moleculare <\/em>din <em>Rom\u00e2nia <\/em>se num\u0103r\u0103 printre fondatorii <em>Teoriei Grafurilor Chimice<\/em>, ca \u015ftiin\u0163\u0103 modern\u0103, interdisciplinar\u0103 (parte a Chimiei Matematice, al\u0103turi de Chemometrie \u015fi Chimie Computa\u0163ional\u0103), cu implica\u0163ii \u00een farmaceutic\u0103, \u015ftiin\u0163a materialelor, coloran\u0163i, aromatizan\u0163i, cosmetice ori electronic\u0103.<\/p>\n<p>Teoria grafurilor chimice reprezint\u0103 un domeniu interdisciplinar de v\u00e2rf \u00een cercetare, viz\u00e2nd \u00een special urm\u0103toarele: matrici topologice; indici topologici; simetrie si similaritate; modelarea propriet\u0103\u021bilor fizico-chimice \u015fi biologice, modelarea molecular\u0103 la nivel molecular-mecanic \u015fi cuantic, modelarea activit\u0103\u0163ii biologice, modelarea cineticii reac\u0163iilor chimice\u00a0 complexe \u015fi ale metaboliz\u0103rii medicamentelor etc.<\/p>\n<p>Fizicianul german G.R.Kirchhoff, a studiat arborii pornind de la studiul re\u021belelor \u0219i circuitelor electrice. Astfel, Kirchoff a studiat la mijlocul secolului al XIX-lea re\u021belele electrice cu metode care apar\u021bin ast\u0103zi teoriei grafurilor.<\/p>\n<p>Exemple de aplica\u021bii practice care pot fi abordate:<\/p>\n<ul>\n<li>Fizic\u0103 &#8211; <em>Graful unui circuit electri<\/em>c (asocierea unui graf orientat unui circuit electric, aplicarea ecua\u021biilor lui Kirchhoff);<\/li>\n<li>Chimie &#8211; <em>Grafuri moleculare<\/em> (reprezentarea grafului molecular specific unei formule structurale specificate, calculul gradelor-valen\u021belor v\u00e2rfurilor unui compus chimic);<\/li>\n<li>Biologie &#8211; <em>Grupele sangvine din sistemul AB0<\/em> (asocierea unui graf orientat cu patru noduri corespunz\u0103tor grupelor sangvine, stabilirea posibililor donatori \u0219i grupele sangvine la care pot dona).<\/li>\n<\/ul>\n<p><strong>Aplica\u021bii \u00een \u0219tiin\u021be sociale<\/strong><\/p>\n<p>Cele mai importante structuri neliniare ce intervin \u00een algoritmii de prelucrare cu calculatorul sunt <em>structurile arborescente<\/em>. Acestea pot fi utilizate \u00een modelarea diverselor fenomene ale lumii reale (de exemplu: arborii genealogici, structuri de organizare \u015fi conducere din \u00eentreprinderi, institu\u0163ii etc.). Structurile arborescente sunt utilizate \u00een mod deosebit \u00een informatic\u0103 pentru reprezentarea structurilor de date ierarhice, sau pentru reprezentarea modular\u2013structurat\u0103 a programelor, a structurii directoarelor etc.<\/p>\n<p>Analiza re\u0163elelor sociale combin\u0103 aspecte ale sociologiei cu reprezent\u0103ri matematice, utiliz\u00e2nd modele structurale pentru a reprezenta interac\u0163iunile umane. De exemplu, problema determin\u0103rii persoanei cu cel mai mare grad de influen\u021b\u0103, cunosc\u00e2nd diferite rela\u021bii, are asociat un graf orientat ce poart\u0103 numele de <em>graf de influen\u021b\u0103<\/em> care are aplica\u021bii \u00een teoria re\u021belelor sociale.<\/p>\n<p>Multe exemple de utilizare a teoriei grafurilor \u00een sociologie implic\u0103 implementarea unui <em>arbore genealogic:<\/em>\u00a0pentru o persoan\u0103 oarecare, determinarea numelor bunicilor, dac\u0103 ace\u0219tia figureaz\u0103 \u00een arborele genealogic sau determinarea \u00een ordinea rela\u021biilor de rudenie a tuturor descenden\u021bilor familiei unei persoane care figureaz\u0103 \u00een arborele genealogic.<\/p>\n<p><strong>Aplica\u021bii de tip labirint<\/strong><\/p>\n<p>Problema real\u0103 a omului prins \u00eentr-un labirint ca fiind o construc\u021bie p\u0103tratic\u0103 format\u0103 din camere (celule), este abordat\u0103 prin teoria grafurilor astfel: consider\u0103m drept noduri camerele, iar drept muchii u\u0219ile dintre camere. Labirintul este &#8222;dat&#8221; \u00een \u00eentregime la \u00eenceput, dar omul prins \u00een labirint nu dispune de \u00eentreaga sa hart\u0103. \u00cen camera de pornire nu cunoa\u0219te la \u00eenceput dec\u00e2t existen\u021ba a cel mult patru u\u0219i de leg\u0103tur\u0103 cu vecinii direc\u021bi (nord, est, sud \u0219i vest). Nu va cunoa\u0219te existen\u021ba unei u\u0219i \u00eentre camere dec\u00e2t \u00een cazul \u00een care ajunge \u00eentr-un nod al grafului. De aici rezult\u0103 c\u0103 la aplicarea oric\u0103rui algoritm de ie\u0219ire din labirint trebuie impus\u0103 condi\u021bia ca aceast\u0103 parcurgere s\u0103 fie efectuat\u0103 &#8222;din camer\u0103 \u00een camer\u0103&#8221;. Astfel, consider\u0103m urm\u0103toarea defini\u021bie a unui labirint &#8211;<em>\u201dNumim labirint un graf neorientat G = (V, M) \u00eempreun\u0103 cu o submul\u021bime Vp de v\u00e2rfuri distincte numite noduri de plecare\u201d.<\/em><\/p>\n<p><em>Algoritmul FILL<\/em> realizeaz\u0103 umplerea (colorarea) unei suprafe\u021be \u00eenchise. Exist\u0103 o serie de probleme care pot fi privite drept aplica\u021bii \u0219i adapt\u0103ri ale mecanismului algoritmului FILL. De exemplu, fiind dat\u0103 o celul\u0103 oarecare din labirint, ale c\u0103rei coordonate se cunosc, s\u0103 se determine un drum de la aceasta \u0219i p\u00e2n\u0103 la singura ie\u0219ire din labirint; nu este neap\u0103rat necesar ca drumul s\u0103 aib\u0103 lungimea minim\u0103.<\/p>\n<p><em>Algoritmul LEE<\/em>\u00a0determin\u0103 lungimea drumului minim\u00a0 pe care \u00eel are de parcurs un \u015foarece p\u00e2n\u0103 la \u021bint\u0103, c\u00e2t \u0219i coordonatele drumului g\u0103sit prin labirint.<\/p>\n<p><strong>Aplica\u021bii din tehnologia comunica\u021biilor, re\u021belele de calculatoare \u0219i sistemele de transport<\/strong><\/p>\n<p>Suportul tehnologic al societ\u0103\u0163ii informa\u0163ionale este asigurat prin convergen\u0163a a trei sectoare: tehnologia informa\u0163iei, tehnologia comunica\u0163iilor \u015fi produc\u0163ia de con\u0163inut electronic. Sistemele de comunica\u0163ii actuale integreaz\u0103 tehnologii multiple, capabile s\u0103 asigure suport pentru servicii de band\u0103 larg\u0103 \u015fi servicii orientate spre aplica\u0163ii particulare ale utilizatorilor. Aceste servicii necesit\u0103 interconectarea mai multor re\u0163ele de comunica\u0163ii, cu arhitecturi \u015fi topologii diferite. Complexitatea analizei \u015fi evalu\u0103rii securit\u0103\u0163ii sistemelor de comunica\u0163ii actuale este determinat\u0103 de multitudinea tehnologiilor, de natura resurselor sistemelor, dar \u015fi de diversificarea tipurilor de amenin\u0163\u0103ri. C\u00e2teva exemple de aplica\u021bii:<\/p>\n<ul>\n<li>determinarea num\u0103rului minim de re\u021bele(\u0219i a structurii acestora) \u00een cadrul c\u0103rora este posibil\u0103 comunica\u021bia direct\u0103 sau indirect\u0103 \u00eentre oricare doi sateli\u021bi trimi\u0219i \u00een spa\u021biu;<\/li>\n<li>determinarea probabilit\u0103\u021bii ca o re\u021bea de calculatoare s\u0103 nu mai func\u021bioneze corect, \u00een cazul \u00eentreruperii unei leg\u0103turi dintre dou\u0103 calculatoare.<\/li>\n<li>determinarea de c\u0103tre departamentul de transporturi a unui scenariu de gravitate maxim\u0103 raportat la c\u0103ile de acces distruse dintr-o zon\u0103, \u00een cazul unui incendiu de propor\u021bii. (S\u0103 ne imagin\u0103m un ora\u0219 ca o re\u021bea de str\u0103zi, sau harta rutier\u0103 a \u021b\u0103rii ca o re\u021bea de autostr\u0103zi, drumuri na\u021bionale \u0219i jude\u021bene, sau\u00a0 re\u021beaua de c\u0103i ferate.)<\/li>\n<\/ul>\n<p><strong>Aplica\u021bii de tip dic\u021bionar<\/strong><\/p>\n<p>Aplica\u0163iile de tip dic\u021bionar electronic sunt elegante \u015fi practice. \u00cen ele se pot stoca baze de date complete \u015fi complexe ale cuvintelor, \u00een func\u021bie de dorin\u021b\u0103: dic\u021bionarul explicativ al limbii rom\u00e2ne, dic\u021bionar de acronime, de abrevieri, de neologisme, etc. Dintre facilit\u0103\u021bi amintim: suport complet at\u00e2t pentru c\u0103utare rapid\u0103 c\u00e2t \u0219i pentru listare, inserarea\/\u0219tergerea unui cuv\u00e2nt din dic\u021bionar.<\/p>\n<ul>\n<li>crearea unui dic\u021bionarul electronic de acronime, afi\u0219area acronimelor \u00een ordine lexicografic\u0103, c\u0103utarea unui cuv\u00e2nt \u0219i a expresiei lexicale asociate, \u0219tergerea unui cuv\u00e2nt din dic\u021bionar.<\/li>\n<\/ul>\n<p><em><strong>Observa\u021bie:<\/strong><\/em> Pe l\u00e2ng\u0103 ariile de aplicabilitate prezentate mai sus, grafurile \u0219i arborii apar \u0219i \u00een alte domenii de o mare importan\u021b\u0103 \u00een modelarea \u0219i procesarea informa\u021biilor, ca de exemplu:<\/p>\n<ul>\n<li>analiza \u0219i implementarea algoritmilor (schema logic\u0103 a unui program se poate reprezenta printr-un <em>graf orientat<\/em>);<\/li>\n<li>studiul bazelor de date cu structuri ierarhice (de tip arbore) \u0219i cu structuri de tip re\u021bea (reprezentate cu ajutorul grafurilor orientate);<\/li>\n<li>modelarea unor algoritmi eficien\u021bi utiliza\u021bi \u00een aplica\u021bii<em> Internet<\/em>, dar \u0219i \u00een reprezentarea grafic\u0103 a unor frac\u021biuni din spa\u021biului <em>WWW<\/em>:<\/li>\n<li>grafurile orientate sunt folosite \u00een algoritmul de analiz\u0103 a ratei de accesare a unei pagini web (prin folosirea <em>hyperlink-urilor<\/em>) pentru determinarea celor mai importante pagini vizitate &#8211; <em>Google\u2019s PageRank<\/em>;<\/li>\n<li>ramuri ale inteligen\u021bei artificiale:<\/li>\n<li>teoria jocurilor (arborii de c\u0103utare pentru determinarea strategiilor de c\u00e2\u0219tig maxim \u00een algoritmul <em>MiniMax<\/em> sau \u00een algoritmul <em>Alfa-Beta<\/em>);<\/li>\n<li>studiul sistemelor expert unde arborii de decizie constituie un model grafic de reprezentare a cuno\u0219tin\u021belor fiind utiliza\u021bi \u00een diferi\u021bi algoritmi de ra\u021bionament;<\/li>\n<li>re\u021bele neuronale artificiale f<em>eed-forward <\/em>\u0219i de tip <em>recurent <\/em>(modelate cu ajutorul grafurilor orientate ponderate).<\/li>\n<\/ul>\n<p>Alegerea \u015fi includerea acestor aplica\u021bii \u00een cadrul orelor de informatic\u0103 nu are doar scopul de a demonstra larga aplicabilitate a teoriei grafurilor, ci \u0219i de a oferi probleme c\u00e2t mai intuitive pentru captarea aten\u0163iei elevilor.<\/p>\n<p><em><strong>Bibliografie<\/strong><\/em><br \/>\n1. ATANASIU A. Bazele informaticii, Editura Universit\u0103\u0163ii din Bucure\u015fti, Bucure\u0219ti, 1989.<br \/>\n2. CADAR C. Introducere \u00een teoria grafurilor, Gazeta de Informatic\u0103 (GINFO), Vol.16\/2 (2006).<br \/>\n3. CERCHEZ E., \u0218ERBAN M. Programarea \u00een limbajul C\/C++ pentru liceu, volumul 3, Editura Polirom, Ia\u0219i, 2006.<br \/>\n4. GHEORGHE M., T\u0102T\u0102R\u00c2M M., ACHINCA C., N\u0102STASE C. Informatic\u0103. Manual pentru clasa a XI-a, Editura Corint, Bucure\u0219ti, 2006.<br \/>\n5. HU\u021aANU V., TUDOR S. Manual de informatic\u0103 intensiv, clasa a XI-a, Editura L&amp;S Soft, Bucure\u0219ti, 2006.<br \/>\n6. LIVOVSCHI L., GEORGESCU H. Sinteza \u015fi analiza algoritmilor, Editura \u015etiin\u0163ific\u0103 \u015fi Enciclopedic\u0103, Bucure\u015fti, 1986.<br \/>\n7. MILO\u0218ESCU M., Manual de informatic\u0103 intensiv, clasa a XI-a, Editura Didactic\u0103 \u0219i pedagogic\u0103, Bucure\u0219ti, 2016.<br \/>\n8. PETRE C., POPA D., CR\u0102CIUNOIU \u015e., ILIESCU C.\u00a0 Metodica pred\u0103rii informaticii \u015fi tehnologiei informa\u0163iei, Editura Arves, Craiova, 2002.<br \/>\n9. T\u0102T\u0102R\u00c2M M. Metodica pred\u0103rii informaticii (I) &#8211; (VIII), Gazeta de Informatic\u0103 (GINFO), vol.III (1993), nr.3 &#8211; vol.IV (1994), nr.3<br \/>\n10. TOMESCU I. Probleme de combinatoric\u0103 \u015fi teoria grafurilor, Editura Didactic\u0103 \u015fi Pedagogic\u0103, Bucure\u015fti, 1981.<br \/>\n11. <a href=\"http:\/\/www.ginfo.ro\/\" target=\"_blank\" rel=\"noopener noreferrer\">www.ginfo.ro<\/a><\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Grafurile au multiple aplica\u0163ii practice, fiind str\u00e2ns legate de multe ramuri ale matematicii (cercet\u0103ri opera\u0163ionale, teoria grupurilor, teoria numerelor), dar sunt folosite \u015fi ca modele matematice \u00een rezolvarea unor probleme tehnice, economice, etc. Ast\u0103zi, teoria grafurilor este folosit\u0103 \u00een domenii &hellip; <a href=\"https:\/\/iteach.ro\/experientedidactice\/domenii-de-aplicabilitate-ale-teoriei-grafurilor-elemente-pentru-abordari-interdisciplinare\">Cite\u0219te continuarea <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[890,1014],"tags":[164],"class_list":["post-8819","post","type-post","status-publish","format-standard","hentry","category-curriculum","category-didactica-informaticii","tag-gabriela-tanasescu"],"_links":{"self":[{"href":"https:\/\/iteach.ro\/experientedidactice\/wp-json\/wp\/v2\/posts\/8819","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/iteach.ro\/experientedidactice\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/iteach.ro\/experientedidactice\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/iteach.ro\/experientedidactice\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/iteach.ro\/experientedidactice\/wp-json\/wp\/v2\/comments?post=8819"}],"version-history":[{"count":2,"href":"https:\/\/iteach.ro\/experientedidactice\/wp-json\/wp\/v2\/posts\/8819\/revisions"}],"predecessor-version":[{"id":8895,"href":"https:\/\/iteach.ro\/experientedidactice\/wp-json\/wp\/v2\/posts\/8819\/revisions\/8895"}],"wp:attachment":[{"href":"https:\/\/iteach.ro\/experientedidactice\/wp-json\/wp\/v2\/media?parent=8819"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/iteach.ro\/experientedidactice\/wp-json\/wp\/v2\/categories?post=8819"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/iteach.ro\/experientedidactice\/wp-json\/wp\/v2\/tags?post=8819"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}