Teoria grafurilor, dezvoltându-se paralel cu algebra modernã, ºi-a fãurit un limbaj al sãu ºi însãºi noþiunea de graf a cãpãtat mai multe accepþii. Teoria grafurilor este prezentatã în sensul lui Koning ºi Berge
Yüklə 175,66 Kb.
|
|
Din µ § ºi µ § µ § µ § ºi deci µ §, iar din dubla incluziune µ §. Problema 3 Reuniunea unui poligon convex cu interiorul sãu este o mulþime convexã. Demonstraþie: Din problema 2 avem µ §, adicã intersecþia celor n semiplane închise limitate de suporturile laturilor µ §. Dar semiplanele închise sunt mulþimi convexe ºi deci întersecþia acestora este tot o mulþime convexã. Observaþie: µ § se numeºte suprafaþã poligonalã limitatã de poligonul convex P. Problema 4. Fie µ § o linie poligonalã. Dacã µ § ºi µ § sunt de o parte ºi de alta a unei drepte d, atunci aceastã dreaptã intersecteazã linia poligonalã. Demonstraþie: Din µ § ºi µ §. Fie k cel mai mic indice pentru care µ § atunci µ § deoarece µ § ºi deci µ § ºi deci µ §.
Dacã o dreaptã d nu este suportul unei laturi a unui poligon convex, atunci d are cel mult douã puncte comune cu poligonul dat. Demonstraþie: Presupunem prin absurd cã d are în comun cu poligonul dat punctele distincte A, B ºi C. Unul dintre aceste puncte este situat între celelalte douã, de exemplu µ § deci µ §, cum µ § se aflã pe o laturã a poligonului, deci existã k aºa încât µ § prin ipotezã µ § ºi deci µ §, dar µ § ºi µ § aºadarµ §. Deci A ºi B sunt de o parte ºi de alta a lui µ § ceea ce nu este posibil într-un poligon convex. Aceasta deoarece din µ § rezultã cã existã µ § aºa încât µ § ºi deci Pi sau Pi+1 aparþin semiplanului µ §. La fel existã µ § aºa încât µ § de unde µ § sau µ §, deci ar exista vârfuri ale poligonului de o parte ºi de alta a dreptei µ §.
Dacã µ § este un poligon convex unde µ § atunci µ § este tot un poligon convex. Demonstraþie: Notãm µ § ºi µ §. Din problema 5 rezultã cã d nu poate avea mai mult de douã puncte comune cu poligonul convex P. De aici avem µ § cãci altfel d ar avea trei puncte comune cu poligonul P. Deci µ §, adicã µ §. La fel gãsim µ § care indicã cã µ §. Procedând analog pânã la segmentul µ § gãsim cã µ § se gãsesc de aceeaºi parte a suportului laturii µ §. Pentru celelalte laturi µ § ale poligonului µ § vârfurile diferite de extremitãþile laturilor respective se gãsesc de aceeaºi parte a suportului sãu, deoarece ele sunt laturi ºi în poligonul convex µ §, deci µ § este ºi el poligon convex.
Fie µ § poligonul convex, µ § numerele naturale astfel ca µ § unde µ §. Sã se arate cã µ §este un poligon convex. Demonstraþie: Folosind problema 6, din µ § poligon convex, µ § este poligon convex ºi aºa mai departe µ § este poligon convex. Putem renunþa la un numãr de vârfuri consecutive ºi obþinem un poligon format din vârfurile rãmase care este tot convex. Folosind aceeaºi procedurã ca mai sus, din poligonul µ § renunþând la vârfurile µ §, obþinem poligonul µ §, care este tot convex cu µ §. Putem continua acest procedeu ºi obþinem astfel poligonul µ § care va fi tot convex. Problema 8. Fie µ § un poligon convex, µ § ºi µ §. Sã se arate cã µ §. Câte puncte are aceastã mulþime? Demonstraþie: Se ºtie cã µ § este intersecþia tuturor semiplanelor deschise limitate de suporturile laturilor µ § ale poligonului ºi care conþine vârfurile pe laturile respective. Din µ § sau µ §. Dacã µ §. Dacã µ § ºi µ § existã k astfel încât B sã nu aparþinã semiplanului mãrginit de dreapta µ § ºi care conþine celelalte vârfuri. Punctul A aparþine acestui semiplan, deci A ºi B se gãsesc de o parte ºi de alta a dreptei µ §. Am demonstrat cã existã mai multe drepte µ § astfel încât A ºi B sã se gãseascã de o parte ºi de alta a lor, rezultã µ §. Fie µ § cel mai mic dintre segmentele µ §. Presupunem cã µ § ºi µ § ºi µ §, dar µ § ºi deci A ºi µ § sunt de o parte ºi de alta a cel puþin unei drepte µ §. Deci existã µ § aºadarµ §. Din µ §. Din µ § ceea ce este în contradicþie cu alegerea punctului µ §. Deci presupunerea cã µ § este falsã µ §. Deoarece dreapta AB include dreapta d, înseamnã cã dreapta AB nu este suportul unei laturi a poligonului convex L, deci µ § are cel mult douã puncte. Am demonstrat cã existã µ § aºa încât µ §. Dacã µ §, considerãm linia poligonalã µ §, punctele µ § ºi µ § se afã pe o dreaptã de o parte ºi de alta a dreptei d. Din problema 4 rezultã cã µ § ºi deci µ §. Dacã µ § se considerã linia poligonalã µ § ºi ajungem la aceeaºi concluzie, deci AB ºi L au douã puncte comune.
Într-un poliedru convex se noteazã cu m numãrul muchiilor, cu µ § numãrul feþelor triunghiulare, patrulatere, pentagonale ºi cu µ § numãrul vârfurilor din care pleacã 3,4,5... muchii. Sã se arate cã: 1) µ § 2) Dacã notãm cu f numãrul feþelor ºi cu v numãrul vârfurilor unui poligon convex oarecare, atunci µ § ºi µ §. Demonstraþie: - Orice muchie a unui poliedru convex este comunã la douã feþe, deci: µ § - Orice muchie a poliedrului trece prin douã vârfuri, deci µ § 2) Þinând cont de 1), avem µ § ºi µ §, iar din relaþia v+f-m=2 µ § m+2=v+f
Prin însumarea celor douã egalitãþi avem: µ §, deci µ §, dar µ § µ § µ § ºi la fel µ §. Problema 10. Adunând mãsurile unghiurilor tutror feþelor unui poliedru convex, se obþine dublul sumei mãsurilor unghiurilor unui poligon convex având acelaºi numãr de vârfuri. Demonstraþie: Notãm cu µ § numãrul feþelor care au i laturi ºi cu µ § suma unghiurilor feþei µ § avem: µ §, atunci S a mãsurilor unghiurilor poliedrului va fi: µ §
µ § Problema 11. Arãtaþi cã dacã un punct variazã în interiorul unui poliedru regulat, suma distanþelor sale la planele feþelor rãmâne constantã. Demonstraþie: Fie un poliedru regulat cu feþele µ § unde µ § ºi M un punct în interiorul sãu. Dacã unim M cu vârful poliedrului se obþin n piramide cu vârful în M ºi bazeleµ §. Fie µ § piciorul perpendicularelor din M pe feþele µ § atunci avem: µ § unde V este volumul poliedrului. Dar µ § deci avem: µ §. §4. UNELE PROBLEME DE INEGALITÃÞI ÎN TETRAEDRU Problema 1. În interiorul tetraedrului se alege punctul M. Sã se arate cã una din laturile tetraedrului se vede din punctul M sub unghi µ §, astfel încât: µ §. Demonstraþie: Presupunem prin absurd cã toate muchiile tetraedrului [ABCD] se vãd din punctul M sub unghiuri de cosinus mai mare decât µ §. Considerând vârfurile tetraedrului pe dreptele MA, MB, MC, MD le luãm astfel încât toate vârfurile tetraedrului sã fie la distanþa 1 de M. Este clar cã prin acest procedeu unghiurile sub care se vãd laturile tetraedrului din punctul M nu s-au schimbat. Fie ABC faþa cea mai apropiatã de punctul M, iar AD cea mai lungã muchie dintre AD, BD, CD. Ducem prin M dreapta perpendicularã pe ABC ºi alegem punctul D1, astfel ca MD1=1, iar D1 este de aceeaºi parte a planului ABC ca ºi punctul D. Dacã µ §, atunci µ §. Aceste inegalitãþi ne spun cã toate laturile tetraedrului se aflã de o parte a planului µ § ce trece prin mijlocul segmentului DD1, perpendicular pe acest segment. Se obþine o contradicþie deoarece punctul M se aflã în planul µ §, iar pe de altã parte este dat în interiorul tetraedrului. Deci µ §. Cum µ §, toate muchiile tetraedrului [ABCD1] se vãd din M sub un unghi de cosinus mai mare ca (-1/3). Tot de aici deducem cã proiecþia punctului M pe planul (ABC) coincide cucentrul cercului circumscris triunghiului ABC. Cum ABC este cea mai apropiatã faþã a tetraedrului de punctul M, centrul cercului circumscris lui ABC este ascuþitunghic. Fie µ §ºi AB cea mai mare laturã a triunghiului ABC. Avem:
µ §, µ §, µ § ºi deci µ §. (Raza cercului circumscris lui ABC este µ §). Dar µ §. Acum din teorema cosinusului avem: µ §. Contradicþie. Problema 2. În orice tetraedru [ABCD] cu notaþiile cunoscute, avem inegalitãþile: a) µ § b) µ §
Demonstraþie: a) Din inegalitatea mediilor avem: µ §. b) Se ºtie cã dacã µ § sunt laturile unui triunghi atunci: µ § (1) Înlocuind în (1) pe µ § ºi µ § obþinem inegalitatea cerutã. Problema 3. Sã se demonstreze cã orice tetraedru [ABCD] poate fi inclus în regiunea cuprinsã între douã plane paralele (inclusiv cele douã plane) astfel încât distanþa d dintre aceste plane sã satisfacã inegelitatea: µ §, unde p reprezintã suma pãtratelor muchiilor tetraedrului. Demonstraþie: Notãm cu SM, EF ºi PQ bimedianele tetraedrului [ABCD]. Avem: µ § µ § (1). Presupunem cã, de exemplu, µ §; Din (1) µ §. Ducem prin AB planul µ § paralel cu CD ºi prin CD planul µ § paralel cu AB. Evident µ §, iar distanþa dintre µ § ºi µ § nu depãºeºte SM. Notãm cu M mulþimea punctelor cuprinse între planele µ § ºi µ § inclusiv cele douã plane. Cum M este o mulþime convexã ºi A,B,C,Dµ § M rezultã cã tetraedrul [A1A2A3A4] este inclus în M.
În orice tetraedru [ABCD] folosind notaþiile cunoscute avem inegalitãþile: a) µ § b) µ §
Demonstraþie: a) Avem µ § ºi analoagele. Conform inegalitãþii mediilor avem: µ § ºi analoagele; µ §. b) Din inegalitatea mediilor avem µ § ºi analoagele; prin adunare µ §.
În orice tetraedru [ABCD] are loc inegalitatea: µ §.
Notaþiile sunt cele cunoscute în tetraedrul [ABCD]. Demonstraþie: µ § (ºi analoagele). Notãm cu µ § µ §; µ §. Însã µ § µ §; µ § µ §. Inegalitatea din enunþ este echivalentã cu a demonstra cã: µ §; µ §; µ §, inegalitate adevãratã. Egalitatea are loc numai dacã µ § este echifacial. Problema 6. Folosind notaþiile cunoscute într-un tetraedru [ABCD] sã se arate cã: a) µ § b) µ §
c) µ § Demonstraþie: a) µ §, etc. µ § µ §
(am folosit inegalitatea: µ §) b) µ §,etc. µ §. c) µ § µ §.
Egalitãþile au loc numai dacã [ABCD] este echifacial. IV. CONSIDERAÞII METODICE Este evident faptul cã niciodatã în istoria ºcolii, a învãþãmântului românesc nu a existat atâta preocupare pentru perfecþionare, pentru modernizarea multidirecþionalã a acestui secto de activitate socialã. Dinamismul societãþii contemporane, determinat de acþiunea concomitentã a revoluþiei social-politice în domeniul ºtiinþei ºi tehnicii solicitã ºcoala la reorientarea ºi reorganizarea acþiunilor ei instructiv-educative, în vederea integrãrii ei rapide, eficiente, creatoare a tinerelor generaþii într-o viaþã socialã cu ritmuri extrem de rapide ale dezvoltãrii. În condiþiile societãþii noastre elevul nu mai poate fi considerat un obiect asupra cãruia se exercitã acþiunea educativã, ci ºi subiect al formãrii propriei sale personalitãºi. Cadrul diddactic nu mai acþioneazã unilateral ci este animat de principiul colaborãrii cu elevul în tot ce întreprinde asumându-ºi sarcina diagnosticãrii ºi satisfacerii nevoilor celui care învaþã, cãutând sã acþioneze la maximum activitatea elevului, determinând din partea acestuia o autenticã muncã independentã, orientatã spre cãutare ºi dobândire prin eforturi proprii a cunoºtinþelor, a priceperilor ºi deprinderilor. Datoria principalã a profesorului de matematicã este aceea de a-i învãþa pe elevi sã gândeascã matematic, deci el trebuie sã se strãduiascã nu numai sã transmitã informaþii ci ºi sã dezvolte la elevii sãi capacitatea de a utiliza informaþiile în rezolvarea problemelor practice ce li se pun. ªtiut este faptul cã un numãr din ce în ce mai mare de persoane, lucrând în cele mai diverse domenii, sunt puse în situaþia de a avea de rezolvat probleme similare cu cele cu care este confruntat omul de ºtiinþã. Amplificarea în avalanºe a informaþiilor ºtiinþifice, progresele tehnice care au loc într-un ritm extraordinar îi obligã pe profesioniþti sã fie gata sã acþioneze noi informaþii tehnico-ºtiinþifice, noi deprinderi de muncã ºi mai ales sã gãseascã soluþii originale la probleme imediate. De aceea învãþãmântul trebuie sã se orienteze în douã direcþii: dezvoltarea creativitãþii ºi formarea deprinderilor, acest lucru impunând o metodologie ºi o tehnicã adecvatã. Trãim într-o epocã în care „eficienþa unei activitãþi” este criteriul numãrul unu de apreciere, dar aceastã eficienþã presupune economie de materie primã, de forþã de muncã, de energie, valutã etc., ºi aceasta, la rândul ei, presupune optimizarea activitãþii respective, pe care o dorim eficientã. Matematica este prima care trebuie sã-ºi aducã aportul în aceastã direcþie ºi asta prin modernizarea sa. Modernizarea matematicii, dupã pãrerea mea, în liceu, înseamnã nu neapãrat încãrcarea programei ºcolare cu un volum mare de informaþie, uneori prezentatã sofisticat de manualele ºcolare, ci cuprinderea de cãtre programa ºcolarã a cât mai multor lecþii de matematicã aplicatã. Aceste lecþii ºi-ar aduce un mai mare aport la înþelegerea multor discipline ºcolare, mai ales a celor de specialitate ºi ar elucida multe din problemele de pregãtire în meserie a elevilor. Consider cã „teoria grafurilor” poate fi înþeleasã de majoritatea elevilor ºi aceasta rãspunde imediat rezolvãrii multor cerinþe ale învãþãmântului românesc, deci ar fi necesarã în cultura generalã a elevilor. Iatã o problemã practicã, care, ca alte mii ºi mii de probleme din viaþa de toate zilele, poate fi modelatã matematic cu ajutorul teoriei grafurilor. Ne propunem sã realizãm o reþea de telecomunicaþii între n localitãþi. Între orice douã localitãþi, instalarea unei linii telefonice presupune un anumit cost. Dorim sã realizãm aceastã reþea de telecomunicaþii cu un cost minim. Cum procedãm? În vederea rezolvãrii acestei probleme ne vom folosi de un graf neorientat, conex, obþinut în felul urmãtor: localitãþile care intrã în reþeaua de telecomunicaþii reprezintã vârfurile grafului grupate în mulþimea X; legãturile telefonice dintre douã localitãþi µ § reprezintã muchiile grafului grupate în mulþimea U; costul instalãrii unei linii telefonice între douã localitãþi µ § va fi funcþia cost ataºatã grafului µ § dupã cum urmeazã: µ §, iar µ § reprezintã costul muchiei µ §. Costul total al grafului G este µ §. Graful astfel construit este un graf valorizat prin funcþia cost c. Rezolvarea problemei noastre se reduce la determinarea unui graf parþial µ § al grafului G care sã aibã cost minim, adicã µ § este minimã. Teoremã 1. Un graf parþial µ § al grafului conex µ §, H fiind de cost minim, este un arbore parþial, deoarece arborii sunt singurele grafuri conexe minimale. Într-adevãr, dacã H este un graf parþial de cost minim al lui G ºi H conþine o muchie µ § a cãrei suprimare conduce la un alt graf parþial de cost minim H1 conex, rezultã cã: µ § Dar inegalitatea obþinutã µ § contrazice minimalitatea grafului H. Pentru gãsirea unui arbore parþial de cost minim, prezint urmãtorul algoritm. Algoritmul APM (arbore parþial minim) Pentru graful µ § conex ºi valorizat prin funcþia µ §, se alege o muchie „u” cu costul c(u) minim. Dintre muchiile nealese se va selecta mereu muchia de cost minim care nu formeazã ciclu cu muchiile deja alese. Aplicarea acestui algoritm se terminã când se obþine o mulþime de muchii V, deci un graf parþial µ § a lui G cu µ §, cu proprietatea cã oricare dintre muchiile rãmase ale lui G formeazã cicluri cu muchiile lui H. Deci H este graful fãrã cicluri maximal cu aceeaºi mulþime de vârfuri ca ºi G. Conform teoremei demonstrate, rezultã cã H este arborele parþial al lui G. Muchiile din V ne vor indica soluþia optimã de instalare a liniilor telefonice între cele n localitãþi, iar c(H) va reprezenta costul minim de realizare eficientã a activitãþii propuse. Fie exemplul de mai jos în care costurile muchiilor sunt date de numerele de pe muchii. Alegem mai întâi muchia de cost minim, de exemplu [1,2], cu costul 2, apoi muchia [1,4], tot de cost 2. În continuare existã douã muchii nealese, de cost minim 3 ºi anume [2,3] ºi [3,4]. O alegem de exemplu pe [2,3]; muchia rãmasã de cost minim este [3,4], dar ea nu mai poate fi aleasã deoarece formeazã ciclul [1,2,3,4,1], cu muchiile alese. În continuare alegem dintre muchiile de cost 4 muchia [1,5] fãrã sã formeze cicluri cu muchiile deja alese. Am obþinut muchiile [1,2], [2,3], [1,4], [1,6], [1,5] deci am obþinut 5 muchii. Existã o proprietate a arborilor cã un arbore cu n vârfuri are exact n-1 muchii. Deci în cazul nostru arborele format cu cele 5 muchii este arborele parþial de cost minim. Acest arbore este reprezentat în figura a); mai sunt douã soluþii reprezentate în figurile b) ºi c) obþinute alegând alte muchii de acelaºi cost. a) b) c)
Închei aceastã problemã printr-un algoritm AMP care este uºor programabil pe calculatorul electronic. Se observã cã se pleacã de la un graf H, care are n vârfuri izolate ºi nici o muchie, H fiind graf parþial al lui G. Ulterior, prin adãugare de muchii se formeazã grafuri parþiale care nu conþin cicluri, deci care au drept componente conexe arbori. Se observã cã o nouã muchie poate fi selectatã dacã are un cost minim printre muchiile nealese ºi dacã extremitãþile ei aparþin unor componente conexe ale grafului parþial obþinut pânã în acel moment. În caz contrar apare un ciclu, deoarece conform teoremei demonstrate un arbore este un graf fãrã cicluri maximal. Pentru a memora numerele de ordine ale componentelor conexe în care se gãsesc la un moment dat vârfurile grafului G vom folosi o listã cu n poziþii, astfel încât poziþia i din listã, notatã cu µ § sã indice numãrul de ordine al componentei în care se gãseºte vârful i al grafului. Pentru a uºura cãutarea muchiei de cost minim, vom alcãtui lista muchiilor grafului G în ordinea crescãtoare a costurilor. Algoritmul se va opri dupã ce a selectat n-1 muchii, deoarece un arbore cu n vârfuri are n-1 muchii. Algoritmul devine: Pentru µ § se face lista µ §. Se alcãtuieºte lista muchiilor grafului G în ordine crescãtoare a costurilor. Fie [p,q] prima muchie din ºirul muchiilor lui G. Au fost selectate n-1 muchii? Dacã da, stop. Am obþinut un arbore parþial minim. Dacã nu, mergem la pasul 5. Se verificã dacã µ §. Dacã da, se considerã urmãtoarea muchie din ºirul de muchii ale lui G. Se noteazã cu p, respectiv q cele douã extremitãþi ale acestei muchii ºi se repetã pasul 5. Dacã µ § se merge la pasul 6. Se selecteazã muchia [pq] ca o nouã muchie a arborelui parþial minim. Dacã de exemplu µ §, toate elementele µ § se înlocuiesc cu valoarea µ § ºi se merge la pasul 4. Se observã cã dacã µ §, cele douã extremitãþi ale muchiei [p,q] sunt în acelaºi arbore, deci alegerea lui [p,q] ar crea un ciclu în graful parþial, obþinut la momentul respectiv. Deci trebuie consideratã urmãtoarea muchie din ºirul de muchii. La pasul 6 se unificã componentele conexe cãrora le aparþin cele douã extremitãþi ale muchiei [p,q] dând tuturor vârfurilor din reuniunea celor douã componente numãrul de ordine egal cu p. La sfârºitul aplicãrii algoritmului lista L va avea toate poziþiile egale cu 1. Optimizarea tuturor problemelor, indiferent de domeniul în care se gãsesc acestea, se finalizeazã cu ajutorul calculatorului electronic, motiv pentru care în perspectivã destul de apropiatã ºcolile vor fi dotate cu asemenea aparate a cãror activitate va fi dirijatã de profesorii de matematicã. Yüklə 175,66 Kb. Dostları ilə paylaş:
|