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

§2. Mulþimi poliedrale

Mulþimile poliedrale constituie analogul suprafeþelor poligonale din plan, cu deosebirea cã în acest caz suprafeþele poligonale convexe sunt înlocuite cu prisme, piramide ºi trunchiuri de piramidã.

Se numeºte mulþime poliedralã o mulþime de puncte din spaþiu care este reuniunea unui numãr finit de prisme, piramide ºi trunchiuri de piramidã, acestea având douã câte douã interioare disjuncte.

Dacã P este mulþimea poliedralã, iar µ § sunt prismele piramidale ºi trunchiurile de piramide respective, adicã µ § ºi µ §, µ §, atunci se va spune cã mulþimea P se descompune în mulþimile µ §.

Un punct O al mulþimii poliedrale P se numeºte punct interior al lui P dacã existã un corp sferic cu centrul în O inclus în P. Punctele mulþimii P ce nu sunt interioare acesteia se numesc puncte de frontierã.
Teoremã 1

Orice mulþime poliedralã se poate descompune în tetraedre.

Demonstraþia rezultã din proprietãþile de descompunere a prismelor, piramidelor ºi trunchiurilor de piramidã.

Proprietate 1.

Orice prismã se descompune în prisme triunghiulare.

Demonstraþie :

Se considerã prisma P cu bazele S ºi S' . ªtim cã suprafaþa poligonalã S se descompune în suprafeþe triunghiulare µ §. Prismele determinate de bazele µ §, planul bazei S' ºi având muchiile laterale paralele cu muchiile laterale ale prismei P au interioare disjuncte ºi reuniunea lor coincide cu P. (fig.1a)

Proprietate 2.

Orice prismã triunghiularã se descompune în trei tetraedre.

Demonstraþie :

Se considerã prisma µ § ºi piramidele µ §, µ § ºi µ §, aceste trei piramide au interioare disjuncte, deoarece oricare douã dintre ele au ca intersecþie o faþã sau o muchie, iar reuniunea lor este P, deci P se descompune în µ §. (fig.1b)

Proprietate 3.

Orice piramidã se descompune în piramide triunghiulare.

Proprietatea rezultã din faptul cã baza piramidei se descompune în suprafeþe triunghiulare care împreunã cu vârful piramidei determinã piramide ce realizeazã descompunerea. (fig.1c)

Proprietate 4.

Orice trunchi de piramidã se descompune în trunchiuri de piramidã triunghiulare.

Proprietatea este consecinþã a proprietãþii 3, fig.2a.

Proprietate 5.

Orice trunchi de piramidã triunghiularã se descompune în trei tetraedre.

Descompunerea este analoagã celei din proprietatea 3, fig.2b.

Dacã douã mulþimi poliedrale sunt congruente ºi una din ele este descompusã în tetraedrele µ § atunci ºi cealaltã poate fi descompusã în tetraedrele µ § astfe ca µ §, i = 1,2,¡Kn.

Un corespondent în spaþiu al suprafeþelor poligonale cu frontiera poligon îl constituie poliedrele.

O mulþime poliedralã P se numeºte poliedru dacã are urmãtoarele proprietãþi :

Pentru orice douã puncte interioare ale lui P, existã o linie poligonalã cu extremitãþile în cele douã puncte, formatã numai din puncte interioare.

Pentru orice douã puncte care nu aparþin lui P existã o linie poligonalã cu extremitãþile în cele douã puncte, formatã numai din puncte care nu aparþin lui P.

Se numeºte vârf al unui poliedru un punct care aparþine frontierei poliedrului ºi nu aparþine nici unui segment deschis inclus în frontierã.

Se numeºte muchie a unui poliedru un segment determinat de douã vârfuri ale poliedrului, inclus în frontierã ºi ale cãrei puncte nu aparþin interiorului nici unei suprafeþe poligonale inclusã în frontierã.

Un poliedru se zice convex dacã este mulþime convexã. În cazul unui poliedru convex, frontiera este o reuniune de suprafeþe poligonale convexe, a cãror laturi sunt muchii ale poliedrului. O astfel de suprafaþã poligonalã convexã se numeºte faþã a poliedrului.

Se numeºte reþea poligonalã simplã o suprafaþã poligonalã [P] cu frontiera poligon, împreunã cu o descompunere a ei în suprafeþe poligonale convexe µ §. Cele f suprafeþe [Pi] se numesc feþele reþelei, iar vârfurile ºi laturile acestora se numesc vârfurile ºi muchiile reþelei, numãrul lor fiind notat cu v respectiv m.
Teoremã 2.

În orice reþea poligonalã simplã avem µ §.

Demonstraþie :

Dacã Pi are 4 laturi sau mai multe, ducând o diagonalã a lui Pi, se obþine o reþea nouã în care numãrul vârfurilor este tot v, dar existã o muchie în plus ºi o faþã în plus, deci numãrul µ § nu s-a modificat. Aºadar, dacã descompunem fiecare [Pi] în suprafeþe triunghiulare, se obþine o reþea pentru care µ § rãmâne acelaºi. Deci este suficient sã demonstrãm teorema pentru cazul când fiecare Pi este triunghi.

Aplicãm inducþia matematicã în raport cu f.

Dacã f = 1 avem un singur triunghi, deci v = 3, m = 3 ºi deci µ §.

Presupunem proprietatea adevãratã pentru orice reþea în care numãrul feþelor este mai mic sau egal cu f-1. Considerãm o suprafaþã triunghiularã [ABC] a reþelei având latura [AB] în comun cu P ºi deosebim douã cazuri:

C este un punct interior lui [P] (fig.3). Scoþând din reþea µ §, se obþine o reþea simplã cu f-1 feþe, v vârfuri ºi m-1 muchii. În virtutea ipotezei din inducþie avem : µ §. Deci µ §.

Dacã µ §, (fig.4), atunci [AC] sau [BC] descompune reþeaua [P] în reþele poligonale simple [P'] ºi [P''] cu v', m', f' respectiv v'', m'' ºi f'' vârfuri, muchii ºi feþe pentru care µ § ºi µ §. Deoarece µ §, µ § ºi µ § µ § ºi deci µ §.

Teorema 3.

Dacã v, m, f reprezintã respectiv numãrul vârfurilor, muchiilor ºi feþelor unui poliedru convex, atunci µ §.
Demonstraþie :

Fie µ § o faþã a lui P, µ § planul lui L, iar µ § un plan paralel cu µ §, astfel ca poliedrul P sã fie situat între µ § ºi µ §. Luãm un punct µ § ºi o dreaptã µ §, N ºi IntP fiind de o parte ºi de alta a lui µ §. Notãm cu µ §, µ §, µ § este un poligon convex asemenea cu µ § ºi dacã N este suficient de aproape de M, punctele µ § se aflã în interiorul lui µ §. Prin urmare punctele µ § sunt vârfurile unei reþele poligonale simple având v vârfuri, m muchii ºi f feþe.din teorema 2 µ § deci µ §.

Observaþie :

Dacã se suprimã faþa L se obþine o reþea spaþialã simplã R, aºezatã pe suprafaþa poliedrului P. Acesteia i-am asociat prin „proiectarea din N ” o reþea poligonalã simplã în planul µ §. Bazându-ne pe intuiþie, putem sã obþinem asocierea respectivã ºi în alt mod. Ne imaginãm cã reþeaua R este realizatã dintr-o membranã elasticã pe care o întindem pânã ce devine planã, ea se deformeazã ºi muchiile devin arce de curbe, dar acestea pot fi înlocuite cu segmente de drepte fãrã a schimba numãrul v, m ºi f-1 ºi teorema 3 rezultã din teorema 2. Acest procedeu poate fi aplicat ori de câte ori reþeaua spaþialã, presupusã elasticã, poate fi întinsã astfel încât sã devinã planã. Deci relaþia lui Euler este valabilã ºi pentru alte tipuri de poliedre, nu numai pentru cele convexe.

(fig.5)

Fie corpul din figura 6 pentru care v = 9, m = 16, f = 9 ºi µ § µ §µ § acest corp poate fi întins în plan.

Dacã considerãm corpul din figura 7, de formã inelarã, reþeaua feþelor rãmase nu se mai poate întinde pe un plan ºi avem: v = 16, m = 32, f = 16 ºi µ §.

Dacã un corp este strãpuns de p ori, zicem cã suprafaþa lui este de „gen p” ºi în acest caz µ §.

Numãrul µ § se numeºte caracteristica eulerianã a suprafeþei respective. Suprafaþa unui poliedru convex este de „gen O” ºi are carqacteristica eulerianã egalã cu 2.

Un poliedru convex P se numeºte poliedru regulat dacã fiecare vârf a lui P aparþine aceluiaºi numãr de muchii, toate feþele sunt suprafeþe poligonale regulate congruente ºi toate unghiurile diedre, determinat de feþe cu muchie comunã sunt congruente.

Teoremã 4

Existã numai cinci tipuri de poliedre regulate ºi anume: tetraedrul, hexaedrul (cubul) octoedrul, dodecaedrul ºi icosoedrul regulat.

Demonstraþie:

Notãm prin q numãrul muchiilor de pe o faþã ºi cu p numãrul muchiilor care pleacã dintr-un vârf. Pentru cã fiecare muchie e inclusã în douã feþe ºi are douã vârfuri, rezultã: µ §, deci

(1) µ § ºi µ §

Dar din relaþia lui Euler avem µ §

sau (2) µ §

Deci (3) µ § de unde µ §.

Deci µ §, la fel ºi µ §, iar dacã µ § atunci µ §.

Aºadar singurele perechi µ § care verificã inegalitatea (3) sunt:

(4) (3,3), (3,4), (3,5), (4,3), (5,3)

Deci existã cel mult cinci tipuri de poliedre regulate. Arãtãm cã pentru fiecare pereche din ºirul 4 existã un poliedru regulat.

Dacã p = 3 ºi q = 3

Din (2) obþinem m = 6, iar din (1) obþinem v = 4 ºi f = 4, acesta este tetraedrul regulat.

Dacã p = 3 ºi q = 4 µ § ºi µ §, acesta este cubul sau hexaedrul regulat (figura 8a).

Cazul µ § ºi f = 8, acest poliedru poate fi realizat luând ca vârfuri centrele feþelor unul cub (figura 8a).

Cazul µ § ºi f = 20, acest poliedru poate fi realizat în felul urmãtor:

Se considerã într-un plan µ § un pentagon regulat ABCDE, de centru O ºi laturã a. Pe dreapta dusã prin O, perpendicularã pe µ § se ia un punct F astfel ca AF = a. Atunci triunghiurile FAB, FBC, FCD, FDE ºi FEA sunt echilaterale.

Se ia un punct O’ pe semidreapta opusã lui /OF, se duce planul µ § prin O’, paralel cu µ § ºi se proiecteazã punctele A,B pe µ § în A'B'. Înscriem în cercul C(O',OA) situat în µ § un pentagon regulat GHIJK astfel încât G sã fie mijlocul arcului mic A'B'. Determinãm distanþa µ § aºa încât µ §, notãm în acest scop cu M mijlocul segmentului (AB) ºi cu N mijlocul arcului mic AB al cercului circumscris lui ABCDE; rezultã µ §. Între planele µ § ºi µ § se formeazã zece triunghiuri echilaterale: ABG, BCH, DEJ, EAK, GHB, HIC, IJP, JKE, KGA.

Pe semidreapta opusã lui O'F luãm punctul L pentru care O'L=OF se obþin alte cinci triunghiuri echilaterale de laturã a: GHL, HIL, IJL, JKL, KGL ºi [FABCDEGHIJKL] este un poliedru regulat cu 20 de feþe, numit icosaedru regulat (figura 8b ºi 8c).

Cazul µ §

Centrele feþelor unui icosaedru regulat formeazã vârfurile unui poliedru regulat cu 12 feþe numit dodecaedru regulat (figura 8d).

fig.8a

fig.8b

fig.8c

fig.8d

§3. PROBLEME REZOLVATE

Problema 1

Un vârf al unui patrulater ABCD se marcheazã dacã ºi numai dacã el este situat în interiorul unghiului opus. Sã se demonstreze:

Cel puþin unul din vârfurile A, B, C, D va fi marcat;

Dacã douã vârfuri sunt marcate, atunci patrulaterul este convex ºi toate vârfurile vor fi marcate.

Demonstraþie:

Fie ABCD un patrulater, el poate fi convex sau neconvex.

Dacã ABCD este patrulater convex µ §, din faptul cã diagonalele unui patrulater convex au un punct comun, cã toate vârfurile sale sunt situate în interiorul unghiului opus ºi deci toate vârfurile sunt marcate.

Dacã ABCD este patrulater neconvex, existã cel puþin o laturã, sã zicem [AB], al cãrui suport separã celelalte vârfuri C ºi D, deci µ § ºi µ §. Evident cã µ § deoarece definiþia poligonului nu admite poligoane care se autointersecteazã. Din µ §µ § ºi µ § sau µ §.

Cazul I. µ §

Vom arãta cã µ §, µ § ºi µ § adicã B este un vârf marcat, iar A, C, D sunt nemarcate.

Notãm AB = a, BC = b, DA = d, µ § ºi avem µ § ºi µ §, dar µ § ºi µ § din µ § ºi µ §, dar µ §, dar µ § ºi µ §, din µ §, dar µ § ºi deci µ § ºi µ §= =µ §.

Arãtãm cã µ §, µ § ºi µ §.

1) µ §µ §µ §

2) µ §µ § din µ §, dar µ § µ §.

µ §µ §, µ §µ §

Cazul II. µ § - se trateazã analog

Dacã douã vârfuri ale unui patrulater sunt marcate, atunci patrulaterul este convex, un patrulater neconvex are un singur vârf nemarcat, deci toate vârfurile sunt marcate.

Problema 2.

Intersecþia semiplanelor închise limitate de suporturile laturilor unui poligon convex P coincide cu mulþimea µ §.

Demonstraþie:

Fie poligonul µ §

Fie I intersecþia consideratã. Se ºtie cã µ § este intersecþia semiplanelor deschise limitate de suporturile laturilor poligonului ºi care conþine vârfurile nesituate pe laturile respective. Dar orice semiplan deschis este inclus în semiplanul închis mãrginit de aceeaºi dreaptã, deci intersecþia semiplanelor închise µ §.

Din convexitatea poligonului P rezultã cã pentru fiecare laturã µ §, toate vârfurile diferite de PK ºi PK+1 se gãsesc de aceeaºi parte a dreptei PKPK+1. Deci existã în I un singur semiplan închis mãrginit de PKPK+1 care include frontiera sa. Dar µ § µ §, deci µ § ºi µ § µ §.

Demonstrãm incluziunea inversã, adicã µ §.

Fie µ §, deci µ § tuturor semiplanelor închise nemãrginite de suporturi laturile µ §.

Pentru M avem urmãtoarele situaþii:

1) µ § µ § dar M aparþine tuturor semiplanelor închise mãrginite de dreapta µ §, deci M aparþine intersecþiei lor, µ § deci µ §.

2) Existã K, aºa încât µ §, dar M se gãseºte ºi în toate celelalte n-1 semiplane închise mãrginite de suporturile celorlalte laturi diferite de µ §. Deci M se gãseºte ºi în semiplanul închis mãrginit de dreptele µ § ºi care conþine ºi celelalte vârfuri diferite de Pk-1 ºi Pk, rezultã deci cã M ºi Pk+1 sunt de aceeaºi parte a dreptei µ § ºi deci µ §. La fel se gãseºte ºi în semiplanul mãrginit de dreapta µ § ºi care conþine celelalte vârfuri M ºi Pk sunt de aceeaºi parte a dreptei µ § deci µ §.

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 µ §.
Problema 5.

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 µ §.
Problema 6.

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.
Problema 7.

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.
Problema 9.

Î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.
Problema 4.

Î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

µ §.
Problema 5.

Î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ã.