INTRODUCERETeoria grafurilor, dezvoltndu-se paralel cu algebra modern, i-a furit un limbaj al su i nsi noiunea de graf a cptat mai multe accepii. Teoria grafurilor este prezentat n sensul lui Koning i Berge.

Cu metodele teoriei grafurilor se rezolv un mare numr de probleme din teoria circuitelor electrice, teoria reelelor de transport, teoria informaiilor, cibernetic, teoria mulimilor sau alte discipline abstracte. De remarcat este faptul c discipline foarte variate ajung s utilizeze teoreme analoage; tim c noiunea de matrice de inciden introdus de Kirchhof pentru studiul circuitelor electrice a fost reluat de ctre Henri Poincor n topologie, noiunea de punct de articulaie folosit n sociologie, de mult vreme, acum se folosete n electronic.Pentru a putea fi aplicat n domenii att de variate, teoria grafurilor trebuie s fie n mod esenial abstract i formalizat.Teoria grafurilor fiind una dintre cele mai solicitate teorii n rezolvarea problemelor din economie i viaa social, m-a determinat s aleg aceast lucrare: GRAFURI PLANARE, POLIEDRE CONVEXE I APLICAII, gndindu-m c, cu o parte din elevi, prin cercurile de matematic, se pot dezbate marea majoritate a problemelor din lucrarea de fa, lrgindu-le astfel sfera de cunotine privitoare la matematicile aplicate.

Primul capitol Elemente de teoria grafurilor, la nceput, prezint aplicaii univoce, aplicaii multivoce, precum i nchiderea tranzitiv a unei aplicaii multivoce. Toate acestea sunt noiuni de teoria mulimilor necesare n definirea noiunilor de graf, multigraf, graf parial, subgraf, drum circuit, lan ciclu.n continuare sunt lmurite noiunile de: graf simetric, graf antisimetric, graf complet, graf conex, graf neconex, graf tare conex i sunt prezentate: matricea asociat, matricea transpus, matricea complementar a grafului.

Al doilea capitol Grafuri planare prezint noiunile de graf planar, graf planar de tip 1 i graf planar de tip 2, teorema lui Euler i teorema lui Kuratovski.

Pentru lmurirea problemelor legate de cromatismul grafurilor planare am definit funciile lui Grundy. Modul n care se pot colora grafurile este dat de teorema lui Hevood i corolarele obinute din aceasta. Mare parte din aceste noiuni pot fi prezentate elevilor din liceu, n cadrul cercurilor de matematic, i este necesar s se sublinieze utilitatea teoriei grafurilor n rezolvarea numeroaselor probleme de matematici aplicate, probleme care au ca scop optimizarea unor procese industriale cum ar fi: problema drumului critic ntr-un graf de activitate, problema arborelui parial minim, problema determinrii fluxului maxim ntr-o reea de transport etc.Toate aceste probleme sunt studiate, de fapt, de elevii claselor de matematic-fizic, n cadrul orelor de matematici aplicate. Suma i produsul a dou matrice poate fi definit cu ajutorul grafurilor.

Ultimul capitol Poliedre convexe are ca scop aprofundarea noiunilor prevazute de programa colar pentru elevii din clasa a IX-a i a X-a, aprofundare care se poate realiza prin cercurile de elevi i prin pregtirile pentru olimpiade.

Am pornit de la noiunea de mulime convex definit n clasa a IX-a i am lmurit noiunile de poligoane convexe i suprafa poligonal convex. Apoi am prezentat mulimile poliedrale cu proprietile lor, reeaua poligonal simpl, teorema lui Euler i teorema privitoare la numrul posibil de poliedre regulate.

n final am prezentat rezolvarea problemelor dificile i deosebit de dificile din manualele de clasa a IX-a i a X-a privitoare la mulimi convexe.

Legtura dintre grafuri i poliedre este realizat prin teorema Euler, aceasta nu poate fi demonstrat cu ajutorul grafurilor n clasa a X-a deoarece elevii nu cunosc noiunea de liniar independen.I. ELEMENTE DE TEORIA GRAFURILOR

1. Noiunea de graf

Fie X i Y dou mulimi date, o lege care face s corespund fiecrui element un element bine definit din Y notat cu , se numete aplicaie univoc a lui X i Y, sau o funcie definit n X cu valori n Y. O aplicaie definit pe X cu valori n Y, care face s corespund fiecrui element x a lui X o submulime a lui Y notat cu , se numete aplicaie multivoc a lui X n Y. Putem avea .Fie X o mulime i . Dac atunci imaginea lui A prin aplicaia este .Dac A1, A2, ...,An sunt submulimile lui X avem:

10.

20.

30. Dac este o alt aplicaie a lui X n X produsul de compoziie este aplicaie definit prin: Aplicaiile 2, 3, ...sunt definite prin:

2x=(x)

3x=(3x) ... etc.

40. nchiderea tranzitiv a lui este o aplicaie a lui X n X definit prin

50. Inversa aplicaiei este aplicaia -1 definit prin:

Dac B este submulime a lui X se poate atunci scrie:

Exemplul 1.X = mulimea de indivizi, iar x un individ

x = mulimea copiilor lui x

= mulimea nepoilor lui x

= mulimea format din x, copiii lui x i nepoii lui x.

Exemplul 2Se consider jocul de ah; o poziie n jocul de ah este constituit dintr-o diagram i prin indicarea juctorului care trebuie s joace. Fie X mulimea tuturor poziiilor posibile i, dac , fie x mulimea poziiilor care, potrivit regulilor de joc, pot urma imediat poziiei x; avem dac x este poziia de mat sau de pat.Avem apoi:

= mulimea poziiilor care pot fi obinute n trei mutri dup poziia lui x

= mulimea poziiilor care pot fi ntlnite imediat sau mai trziu dup poziia lui x

(cu ) este mulimea poziiilor care pot deveni ntr-o singur mutare o poziie a lui AAcest sistem de notaie permite s se pun sub form de formul mulimea poziiilor avute n vedere i de a reduce unele proprieti. n cazul jocului de ah, regula este complet determinat de mulimea X i aplicaia , dar din cauza unui mare numr de poziii posibile va fi imposibil s se reprezinte poziiile prin puncte i aplicaia prin sgei unind unele dintre aceste puncte.Se numete graf i se noteaz cu perechea format din mulimea X i o aplicaie multivoc a lui X n X.

Cnd este posibil, elementele mulimii X vor fi reprezentate prin puncte ale planului i dac dou puncte x i y sunt astfel nct vom duce o linie continu prevzut cu o sgeat de la x spre y, figura de mai jos:

Din acest motiv un element al lui X l numim punct sau vrf al grafului, iar perechea (x,y) cu se numete arc al grafului. Mulimea arcelor grafului G o notm cu U, iar arcele le vom nota cu u, v, w.Atunci graful G=(X,) poate fi notat i sub forma G=(X,U).

Un subgraf al grafului G =(X, ) este prin definiie un graf G= (A, A), unde , iar .Un graf parial al lui G = (X, ) este prin definiie un graf de forma G= (X, ) unde pentru orice x, x = x.

Un subgraf parial al lui G = (X, ) este prin definiie un graf de forma (A, A) unde i . Pentru un arc u = (a, b), vrful a este extremitate iniial, iar b este extremitate final sau terminal.Dou arce u i v se numesc adiacente dac sunt distincte i au o extremitate comun.

Se spune c vrfurile x i y sunt adiacente dac sunt distincte i exist un arc u = (x,y).

Se spune c arcul u este incident cu vrful x spre exterior dac x este extremitate iniial a lui u i dac extremitatea terminal a lui u este diferit de x.

Se definete la fel un arc incident spre interior.

Se spune c un arc u este incident cu A spre exterior, unde A este o mulime de vrfuri date, dac u = (a, x) cu i .Mulimea arcelor incidente cu o mulime A spre exterior se noteaz , iar mulimea arcelor incidente cu A se noteaz cu .

Mulimea arcelor incidente cu A se noteaz .

n graful G = (X, U) se numete drum un ir (u1, u2, ...) de arce, astfel nct extremitatea terminal a fiecrui arc coincide cu extremitatea iniial a arcului urmtor. Un drum este simplu dac nu folosete de dou ori acelai arc i compus n caz contrar. Dac drumul ntlnete succesiv vrfurile x1, x2, ..., xk, xk+1 l notm = [x1, x2, ..., xk, xk+1].Un drumm care nu trece de dou ori prin acelai vrf se numete drum elementar. Un drum poate fi finit sau infinit.

Un circuit este un drum finit = [x1, x2 ... xk] unde x1 = xk. Circuitul este elementar dac pornim dintr-un drum elementar. Lungimea unui drum = (u1, u2, ..., uk) este numrul arcelor irului i o notm cu l(u), iar dac drumul este infinit atunci l(u) = .Se numete bucl un circuit de lungime 1, format dintr-un singur arc (x, x).

Un graf G = (X, U) se numete simetric dac din (ntr-un graf simetric dou vrfuri adiacente sunt legate ntre ele prin dou arce orientate opus unul celuilalt). Pentru a simplifica lucrurile convenim s unim cele dou vrfuri printr-o singur linie continu fr sgei pe ea.

Un graf G = (X, U) se zice antisimetric dac din (orice pereche de vrfuri adiacente sunt legate ntre ele ntr-o singur direcie).Un graf G = (X, U) se numete complet dac (orice perche de vrfuri este legat cel puin n una din cele dou direcii).Un graf G = (X, U) se numete tare conex dac oricare ar fi vrfurile x i y, cu , exist un drum care pleac din x la y. n vrful G = (X, U) o muchie este, prin definiie, o mulime de dou vrfuri x i y astfel ca sau . Aceast noiune nu trebuie confundat cu cea de arc care presupune i o orientare. Convenim ca mulimea muchiilor s o notm cu U, iar muchiile cu literele: u, v...Un lan este un ir de muchii (u1, u2, ...) fiecare muchie uk fiind legat de muchia uk-1 printr-o extremitate i de uk+1 prin cealalt extremitate. Un lan este simplu dac muchiile care-l formeaz sunt diferite ntre ele i este compus n celelalte cazuri. Un ciclu este un lan finit care pleac din x i ajunge tot n x. Ciclul este simplu dac muchiile care l compun sunt diferite ntre ele i compus n celelalte cazuri.

Ciclul este elementar dac orice vrf din acest ciclu este ntlnit o singur dat.

Un graf este conex dac pentru orice pereche de vrfuri distincte exist un lan plecnd de la un vrf la cellalt. Un graf tare conex este i conex ns reciproc nu este adevrat . Notm cu mulimea compus din vrful a dat i din toate vrfurile grafului care pot fi unite cu vrful a printr-un lan. O component comun este subgraful generat de o mulime de forma Ca.Teorem 1.

Diferite componente ale grafului G = (X, ) formeaz o partiie a lui X, adic:(1)

(2)

(3)

Demonstraie:

(1) este adevrat, pentru c

(2) presupunem c i artm c Ca = Cb.

Fie , acest vrf poate fi legat printr-un lan de a i b, deci poate fi legat cu b, deci , deci . Analog .Relaia (3) are loc deoarece

Teorem 2.

Un graf este conex dac i numai dac are o singur component conex.Demonstraie: Dac graful admite dou componente distincte Ca i Cb, el nu este conex, a i b neputnd fi legate printr-un lan. Dac graful nu este conex, exist cel puin dou vrfuri a i b care nu pot fi legate printr-un lan, deci Ca i Cb sunt dou componente distincte.

Exemple de grafuri

1) Harta cilor ferate din ara noastr reprezint un graf n care nodurile de cale ferat reprezint vrfurile grafului, iar legturile directe pe cale aferat reprezint muchiile grafului. Cunoscnd distanele n kilometri, asociate fiecrei muchii, ne putem pune problema gsirii celui mai scurt traseu pe calea ferat ntre dou localiti. Aceasta va corespunde unui lan elementar, care unete cele dou localiti i pentru care suma distanelor asociate muchiilor este minim.2) Dac ne propunem s calculm intesitile curenilor care trec prin ramurile unei reele electrice (fig.1), cunoscnd schema reelei electrice, tensiunile electromotoare i valorile rezistenelor, se scriu legile lui Kirchoff relative la noduri i la ochiuri de reea.

Fcnd abstracie de elementele de circuit care se gsesc pe ramurile schemei putem desena aceast reea sub forma grafului din figura 2. Nodurile reelei vor corespunde vrfurilor grafului, iar ochiurile de reea vor corespunde ciclurilor elementare ale acestui graf. Fizicianul Kirchoff a studiat la mijlocul secolului trecut reele electrice cu metode care aparin astzi teoriei grafurilor, contribuind la dezvoltarea acestei teorii.3) Formulele de structur ale substanelor chimice sunt grafuri pentru care legturile dintre vrfuri corespund legturilor dintre gruprile sau atomii care compun molecula.

Aceste formule de structur au fost reprezentate sub form de grafuri pentru care vrfurile sunt atomii (respectiv gruprile) din molecul, muchiile reprezentnd legturile lor chimice dup cum urmeaz:

Grafurile 3b) i 3c) nu sunt grafuri n sensul definiiei date, deoarece ntre anumite perechi de vrfuri exist mai multe muchii. Un asemenea graf cu muchii multiple se numete multigraf. ntr-un multigraf este desenul moleculei unei substane gradul unui vrf este tocmai valena atomului (gruprii) respective.

2. Matricea asociat unui grafConsiderm un p.graf G = (X, U) i fie x1 x2 ... xn vrfurile sale. Notm cu aij numrul arcelor lui U care pleac de la xi la xj. Matricea ptrat cu n linii i n coloane (aij) se numete matrice asociat p-grafului G = (X, U)

Vectorul ai = (ai1 ai2 ... ain) este al i-lea vector-linie, iar aj = (a1j, a2j, ... anj) este al j-lea vector-coloan.

Exemplu:

X = {x1, x2, x3, x4, x5} Matricea asociat este:

EMBED Equation.3 Faptul c a33 = 1 explic c n vrful x3 este o bucl.Fie A = (aij) o matrice asociat unui p-graf, matricea sa transpus A* = (aij*) se obine din matricea A printr-o simetrie n raport cu diagonala principal; aceasta va fi matricea asociat p-grafului obinut schimbnd orientarea tuturor arcelor.Matricea sa complementar A = (aij) definit prin ; n cazul unui graf (X, ) matricea complementar se obine din A nlocuind cu 1 toi coeficienii i prin 0 toi coeficienii 1. Aceast matrice A este asociat grafului G = (X ) definit prin: = X-x pentru .Teorem 1.

Fie G = (X, ) un graf i A matricea sa asociat. Matricea A este simetric dac i numai dac graful G este simetric. Matricea A este asimetric dac i numai dac graful G este antisimetric. Matricea A este complet dac i numai dac graful G este complet.

Demonstraia teoremei este evident.

Teorem 2.

Se consider dou multigrafuri G = (X, U) i H = (X, V) avnd aceeai mulime de vrfuri i matricele asociate A = (aij) i B = (Bij); matricea A+B corespunde multigrafului format prin reuniunea arcelor din U i V; matricea AB corespunde multigrafului format astfel: de la vrful x la vrful y se duc attea arce cte drumuri distincte sunt care pleac din x la y i sunt formate dintrun arc din U urmat de un arc din V.1) n graful numrul arcelor care pleac din xi spre xj este aij+bij; acest coeficient nu este altul dect coeficientul general al matricei A+B.

2) Numrul drumurilor distincte de forma cu , este egal cu aik bkj; deci pentru a merge din xi la xj numrul total al drumurilor distincte formate cu arcele din U urmate de arce din V este , produs scalar al vectorului-linie ai i al vectorului coloan bj; acest coeficient nu este altul dect coeficientul general al matricei AB.Corolarul 1Dac G este un p-graf i A matricea sa asociat, coeficientul pij al matricei P = A este egal cu numrul drumurilor distincte de lungime care pleac din xi spre xj.

Pentru = 1 teorema este trivial, dac presupunem teorema adevrat pentru -1, ea rmne adevrat pentru , deoarece A = AA-1, i exprim dup teorema precedent, numrul drumurilor de lungime 1+(-1)= care pleac din vrful xi spre vrful xjCorolarul 2 ntr-un graf G exist un drum de lungime dac i numai dac ; nu exist circuite dac i numai dac ncepnd cu un anumit rang.

Acest corolar rezult imediat din corolarul 1.

Aceste rezultate permit s reducem la probleme de matrice un anumit numr de probleme privind p-grafurile. Utilizarea practic a descrierii unui graf prin matricea sa asociat este evident cnd vrem s numrm drumurile unui graf care satisfac anumite condiii date.

Problem 1ntr-un graf G = (X, U) complet i antisimetric s determinm numrul circuitelor de lungime 3.

Teorema 3

Fie G = (X, U) un graf complet, antisimetric, i fie A = (aij) matricea asociat dac este suma coeficienilor liniei a i-a, atunci numrul circuitelor de lungime 3 este:

Numrul circuitelor de lungime 3 este: . Un ciclu de lungime 3 nu este circuit dac i numai dac dou arce sunt identice cu-n acelai vrf xi spre exterior; deci numrul total al ciclurilor de lungime 3, care nu sunt circuite, este exact

Observm c

de unde

3. Matrice de incidenNotm prin u1, u2, ... un, arcele unui graf G = (X, U) i x1, x2, ... xn vrfurile sale i punem

1 dac xi este extremitate iniial a lu uj

sij = -1 dac xi este extremitate final a lui uj

0 dac xi nu este extremitate a lui ujMatricea S = (sij) se numete matrice de inciden a arcelor. Dac u1, u2, ... un sunt muchiile grafului atunci punemrij =1 dac xi este extremitate iniial a lu uj

0 n caz contrar

Matricea R = (rij) este matricea de inciden a muchiilor. O matrice A = (aij) se numete total unimodular dac orice matrice ptrat a lui A are determinantul egal cu 0, +1 sau -1, deoarece el este minor al matricei A de ordinul 1; sunt deci necesare criterii de recunoatere dac o matrice format cu coeficienii 0, +1, -1. este total unimodular.

Fie graful din figura de mai jos (fig.1)

Matricea de inciden a arcelor este:

Matricea R se obine din S nlocuind peste tot n S pe -1 i +1 cu 1.Aceste dou matrice sunt total unimodulare.

Teorem 1 (Heler Tompkins Gole)

Fie A o matrice de coeficieni 0, +1, -1, astfel nct fiecare coloan s conin cel mult doi coeficieni nenuli; matricea A este total unimodular dac i numai dac liniile sale se pot grupa n dou mulimi disjuncte I1 i I2 astfel nct:10dac doi coeficieni nenuli din aceeai coloan au acelai semn, atunci unul este n I1 i cellalt n I2;

20dac doi coeficieni nenuli din aceeai coloan sunt de semne contrare, atunci amndoi sunt n I1 sau n I2.

Demonstraie:

10. Fie A o matrice ale crei linii pot fi mprite conform enunului; orice matrice ptrat B estras din A are de asemenea aceast proprietate. Pentru a arta c matricea A este total unimodular, este suficient s artm c det(B) = 0, +1 sau -1. Aceast propoziie este adevrat pentru matricele B de ordinul 1; presupunem verificat pentru matricele de ordinul q-1 i s deducem c proprietatea este adevrat pentru matrici ptrate de ordinul q, ale cror mulimi disjuncte sunt I1 i I2.Dac orice vector-coloan bj are numai doi coeficieni nenuli, avem:

Vectorii-linie nefiind liniari independeni, avem atunci det(B) = 0. Dac un vector-coloan nu are coeficieni nenuli, avem de asemenea det(B) = 0. n sfrit, dac exist un vector coloan bj numai cu un singur coeficient nenul, fie bij = +1 s notm prin C matricea ptrat dedus din B suprimnd linia i i coloana j; deoarece teorema este presupus adevrat pentru matricele de ordinul q-1, avem sau 0. Propoziia este adevrat deci n toate cazurile.20. Fie A o matrice total unimodular astfel nct fiecare coloan s conin cel mult doi coeficieni nenuli i s artm c exist o partiie (I1, I2) care s verifice enunul. Putem presupune c fiecare coloan care conine un singur coeficient nenul poate fi suprimat, fr s afecteze enunul Matricei A s facem s-i corespund un graf G, neorientat, n modul urmtor: liniei i i asociem un vrf xi i coloanei j muchia uj; aceast muchie va uni xk i xh dac i . Vom spune c o muchie uj este special dac cele dou elemente ale vectorului coloan aj au acelai semn. S artm c fiecare ciclu elementar al grafului conine un numr par de muchii speciale. n adevr, dac ar exista un ciclu elementar care nu ar avea aceast proprietate, fie aceasta de exemplu atunci s considerm determinantul submatricei corespunztoare:

Avem , ; n consecin pentru indici j corespunztori muchiilor nespecifice, care sunt n numr de k - (2p+1). Dac notm prin numrul de inversiuni ale permutrii putem scrie:

Cum matricea este total unimodular avem o contradicie. Astfel, orice ciclu elementar conine un numr par de muchii speciale i de asemenea orice ciclu al grafului are aceast proprietate. Dac restrngem muchiile nespeciale astfel ca cele dou extremiti ale lor s se confunde, se obine un nou graf fr cicluri de lungime impar i acest graf va fi bicolor, dup teorema lui Kning. Dac notm prin I1 mulimea indicilor vrfurilor xi colorate n bleu i prin I2 aceea a vrfurilor xi colorate n rou, atunci mulimile disjuncte I1 i I2 satisfac enunul teoremei.Corolarul 1ntr-un graf matricea de inciden a arcelor S = (sij) este total unimodular.

n adevr, vectorul coloan sj conine coeficienii 0, un coeficient +1 i unul -1. Putem atunci lua i

Corolarul 2Matricea de inciden a muchiilor R = (rij) este total unimodular dac i numai dac graful este bicolor.

n adevr, toi coeficienii nenuli ai lui R fiind egali cu +1, R este total inimodular dac i numai dac vrfurile grafului pot fi mprite n dou mulimi disjuncte, interior stabile:

i

II. GRAFURI PLANARE

1. Proprieti generale. Teorema lui Kuratovski.

Definiie 1.

Un graf G = (X, U) este graf planar dac el poate fi reprezentat pe un plan, aa nct vrfurile s fie puncte distincte, muchiile curbe simple i dou muchii s nu se ntlneasc dect n extremitile lor.

Reprezentarea lui G pe un plan conform cu condiiile impuse se numete graf planar topologic i nu vom considera ca distincte dou grafuri planare topologice dac le putem face s coincid prin deformarea elastic a planului.

Exemplul 1.Problema celor trei orae i a celor trei uzine.

Fie trei orae a, b, c, pe care trebui es le legm prin conducte cu o uzin de ap d, cu o uzin de gaze e i cu o uzin electric f. Puntem plasa, pe un plan, cele trei orae, cele trei uzine i conductele, astfel nct dou conducte s nu se ntlneasc dect la capete? Experiena arat c putem plasa ntotdeauna 8 conducte, iar cea de-a 9-a taie ntotdeauna una din cele 8. (fig.1)

(ap) (gaz) (electric)

Definiie 2. Fie G = (X, U) un graf planar topologic; o fa a lui G este o regiune a planului limitat de muchii i astfel nct dou puncte arbitrare din aceast regiune pot fi unite printr-o linie continu care nu ntlnete nici muchii, nici vrfuri.

Vom nota mulimea feelor cu Z, o fa cu z, iar frontiera unei fee z este mulimea muchiilor care ating faa z. Dou fee z i z se zic adiacente dac frontierele lor au o muchie comun ns dou fee care se ating doar ntr-un vrf nu sunt adiacente.

ntr-un graf topologic, frontiera unei fee z este format din unul sau mai multe cicluri elementare disjuncte, de muchii suspendate sau care unesc dou cicluri disjuncte (istmuri).

Se numete contur al unei fee z, conturul ciclurilor sale elementarecare conin n interiorul lor toate celelalte mucii ale frontierei. Exist ntotdeauna o fa nelimitat i numai una pe care o numimfa infinit i care nu are contur. Toate celelalte fee sunt fee finite i admit contur.

Teorema 1

ntr-un graf planar topologic G, contururile diferitelor fee finite constituie o baz fundamental de cicluri independente.

Teorema este adevrat dac G are dou fee finite; presupunem teorema adevrat pentru orice graf cu (f-1) fee finite i artm plecnd de aici c teorema este adevrat pentru un graf planar topologic G cu f fee finite.

Presupunem c contururile nu ar fi toate cicluri disjuncte (n sensul muchiilor), caz n care teorema de demonstrat ar fi evident. Putem atunci, suprimnd o muchie u, s obinem un graf G cu f-1 fee finite, ale cror contururi constituie o baz fundamental de cicluri independente. Repunnd muchia u se creeaz o nou fa finit al crei contur este un ciclu independent de cele precedente i conine o muchie pe care celelalte nu o au. Dar adunarea unei muchii nu poate mri dect cu o unitate numrul ciclomatic, deci rezult c feele finite ale lui G determin o baz fundamental de cicluri independente.Corolarul 1Dac ntr-un graf planar topologic conex exist n vrfuri, m muchii i f fee, atunci avem n m + f = 2 (formula lui Euler).

Numrul finit este egal cu numrul ciclomatic v de unde:

Corolarul 2n orice graf planar conex, care nu este multigraf, exist un vrf x cu proprietatea c gradul su .

ntr-adevr, n graful planar topologic corespunztor, fiecare fa este nconjurat de cel puin trei muchii distincte. Dac se formeaz graful simplu de inciden fa muchii , atunci numrul arcelor este pe deoparte i pe alt parte. Deci . Rezult c i deci . Dac fiecare vrf este extremitate a cel puin 6 muchii, atunci se obine, n acelai mod, , deci, dup formula lui Euler, avem:

ceea ce este absurd. Formula lui Euler este utiln anumite mprejurri.

Exemplul 1

Fie un poliedru conex cu n vrfurim m muchii i f fee, din spaiul cu trei dimensiuni. Putem s reprezentm acest poliedru pe o sfer, aa nct dou muchii s nu se taie dct la extremiti; efectund apoi o proiecie steriografic al crei centru va fi n mijlocul unei fee, l putem reprezenta pe un plan. Graful fiind planar, se obine o relaie fundamental a poliedrelor conexe i anume: .

Exemplul 2

Artm, cu ajutorul formulei lui Euler, c graful celor 3 orae i 3 uzine nu poate fi un graf planar. Presupunnd c ar fi planar, am avea.

Fiecare fa are cel puin 4 muchii n conturul su (deoarece dac o fa s nu ar avea dect 3 muchii, ea ar fi mrginit de 3 vrfuri, dintre care 2 aparin aceleiai categorii: orae sau uzine; ori dou vrfuri din aceeai categorie nu pot fi adiacente).Dac se formeaz graful simplu de incident fee muchie, atunci numrul de arce este pe deoparte i pe de alt parte, deci:

c.c. e absurd.Exemplul 3

Artm c graful complet cu 5 vrfuri nu este planar.Presupunnd c acest graf ar fi planar, am avea ceea ce este absurd, pentru c i fiecare fa are cel puin 3 muchii n conturul su. Dac se formeaz graful simplu de inciden fee muchii, atunci numrul de arce este pe deoparte i pe de alt parte, ceea ce conduce la; .

Exemplele 2 i 3 ne permit s definim o categorie de grafuri neplanare i anume de tip1 i de tip2, grafuri n care putem aduga pe fiecare muchie ate vrfuri vrem i obinem alte grafuri neplanare. Aceast observaie are o reciproc care este teorema lui Kuratovski.Dac este un ciclu elementar, cruia i asociem n mod arbitrar un sens, i dac a i b , atunci notm prin secvena vrfurilor lui ntlnite mergnd de la a spre b n sensul pozitiv inclusiv a i b.

Dac G este un graf cu o mulime de articulaii A, se numete pies a grafului G, relaiv la A, o component conex C a subgrafului generat de X-A, mpreun cu muchiile incidente cu C i extremitile lor.Teorema lui KuratovskiCondiia necesar i suficient pentru ca un graf G s fie planar, este ca el s nu admit subgrafuri pariale de tip 1 sau de tip 2.

Demonstraie:

Am vzut c un graf care admite un subgraf parial de tip 1 sau de tip 2 nu este planar; invers artm c un graf G care nu admite subgrafuri pariale de tip 1 sau de tip 2 este planar.

Dac G are una, dou sau trei muchii, enunul este adevrat. Presupunem enunul adevrat pentru orice graf cu mai puin de m muchii i artm c el rmne adevrat pentru un graf cu m muchii.

Fie G un graf cu m muchii care nu admite subgrafuri de tip 1 sau de tip 2 i este neplanar. Acest graf este conex pentru c, dac nu ar fi aa, componentele sale fiind planare, G ar fi planar. De asemenea, acest graf va fi nearticulat, deoarece, dac un nu ar fi aa, piesele lui G relative la punctul de articulaie a, fiind planare, pot fi reprezentate planar astfel nct punctul de articulaie a s fie pe feele lor infinite i G ar fi planar.

10.S artm c, dac scoatem din G o muchie , mai rmne un ciclu elementar care trece prin a i b. Dac nu ar fi aa, atunci graful G obinut din grafull G prin suprimarea muchiei ar fi articulat, dup teorema lui Menger, deci vrfurile a, b, relativ la punctul de articulaie c vor fi pe dou piese distincte Ca i Cb.Graful Ca obinut plecnd de la Ca adugndu-i muchia este planar, deoarece nu conine grupuri de tip 1 sau de tip 2. Putem deci, fcnd o proiecie steriografic, s-l reprezentm planar pe Ca astfel nct muchia s fie conturul feei infinite. La fel procedm cu Cb, deci muchia adugat la Cb va fi pe conturul feei infinite. unind apoi pe a cu b se obine un graf planar care conine pe G de unde rezult contradicia.20. S considerm n graful planar topologic G obinut prin suprimarea muchiei un ciclu elementar care trece prin a i b i nglobeaz n interiorul su cel mai mare numr de fee. Dndu-i lui o orientare arbitrar, mparte planul n dou regiuni i piesele lui G avnd vrfurile lor n interior (respectiv exterior) vor fi numite piese interioare (respectiv piese exterioare). O pies exterioar nu poate conine mai mult de un vrf din , deoarece altfel am putea construi un ciclu care s nglobeze n interiorul su un numr mai mare de fee; precum i din o pies exterioar nu ntlnete dect n unul sau dou puncte. Exist cel puin o pies exterioar i o pies interioar care ntlnesc n acelai timp i , deoarece nu putem trasa planar muchia .30. S artm c exist o pies interioar C i o pies exterioar D care ntlnesc pe i pe , astfel nct punctele de contact c i d ale lui D cu i punctele de contact e i f ale lui C cu sunt pe ntr-o ordine alternat: c, e, d, f.Dac presupunem c nu ar fi aa, fie C1 o pies interioar care ntlnete pe i i fie e1 i f1 dou puncte de contact consecutive pe . Se poate desena o linie continu v care s uneasc e1 i f1 n interiorul lui i care s nu ntlneasc nici o muchie existent (deoarece prin ipotez nu exist piese exterioare care s ntlneasc) i . Orice pies interioar care ntlnete numai poate fi transferat n exterior pe faa limitat de v i , aceasta este tocmai cazul pentru piesa C1.Va rmne cel puin o pies interioar C2 care nu poate fi transferat, deoarece a i b ar putea fi unite planar, i aceast pies are dou puncte de contact consecutive e2 i f2 pe , cel puin unul fiind pe . Vom continua acelai procedeu de transfer cu C2 n loc de C1 etc.; acest procedeu nu se va opri niciodat i avem o contradicie deoarece graful este finit. Notm cu e, f, g, i h punctele de contact ale lui C i care verific relaiile , , i . Evident i , ns am putea avea e = g i e = h.40.Dac vrfurile e i f sunt unul pe i cellalt pe , atunci vom putea pune de exemplu e = g, f = h, i se vede imediat c G conine un graf de tip 1, ceea ce este contrar ipotezei nostre (fig.3.a).

50. Dac vrfurile e i f sunt ambele pe putem presupune h = c, deoarece dac , atunci regsim una dintre figurile eliminate n cazul 40. obinem un graf care conine un graf de tip 1, ceea ce este absurd. Din aceleai motive vom nltura cazul n care e i f sunt ambele pe (fig.3.c).

60.Dac e = a, , fie exemplul , atunci se obine figura (3.c) care conine un graf de tip 1 ceea ce este absurd.70.Dac e = a, f = b, vom presupune c g = d i h = c, deoarece altfel vom regsi o figur eliminat la 40 i la 60. Considerm dou cazuri i anume:

dac lanurile lui C care unesc cd i ef au mai mult de un vrf comun, atunci se obine figura (3.d) care conine un graf de tip 1, ceea ce este absurd.

dac lanurile lui C care unesc cd i ef au un singur vrf comun, atunci se obine figura (3.e) care conine un graf de tip 2, ceea ce este de asemenea absurd. Toate poziiile lui e i f fiind examinate, graful G, aa cum a fost definit mai nainte, nu poate exista. Deci, teoria este demonstrat.2. Funciile lui Grundy. Numr cromatic; clas cromatic.

Fie graful G = (X, U), o funcie se numete funcie a lui Grundy pe graful respectiv dac g(x)

Deci din (1)

Funciile Grundy sunt folosite i pentru grafuri finite i pentru grafuri infinite.Propoziie 1. Dac un graf are mcar o bucl, atunci el nu admite funcii ale lui Grundy

Evident, deoarece vrful cruia i este ataat bucla se precede pe sine nsui i este o absurditate.

Propoziie 2 Dac un graf G nu are bucle i nici circuite, atunci el admite o funcie a lui Grundy i numai una.Demonstraie : Fie (2) nivelele ce se obin cnd ordonam graful prin eliminarea succesiv a descendenilor. Din relaia (1) rezult i deci (3).

Definiia funciei Grundy ne d (4)

Pentru vrfurile din Nr obinem:

1 dac

g(x) = 2 dac

3 dac

Tot astfel n nivelele urmtoare, definiia ne permite s asociem fiecrui vrf un numr natural i numai unul care va fi valoarea funciei lui Grundy n acel punct.

Corolarul 1 Grafurile secveniale admit o funcie a lui Grundy i numai una al crei codomeniu este .Corolarul 2Dac ntr-un graf fr bucle i circuite descendenii oricrui vrf aparin tuturor nivelelor urmtoare, atunci funcia lui Grundy pe care o admite graful, coincide cu funcia ordinal a sa.

Exemplul 1

Fie graful

Acest graf admite funcia lui Grundy ale crei valori sunt notate n vrfuri i este evident o funcie ordinal.

Exemplul 2Considerm graful fr bucle i fr circuite din figura

Partiia n nivele a vrfurilor sale, obinut prin eliminarea succesiv a descendenilor este dat de: 1234567891011IIIIIIIVVVIVIIVIIIIX

1111333333310

21122222110

311111110

4112221110

51122210

611110

711222210

81110

911210

10110

110

Redesenez graful cu ordonarea ce rezult din tabel pentru vrfuri, lng care sunt nscrise valorile funciei lui Grundy ce se obine imediat n baza definiiei acesteia.

Propoziie 3 Grafurile formate dintr-un singur circuit admit funcii Grundy dac i numai dac el are o lungime par.

Demonstraie

Suprimnd un arc al circuitului, rezult un drum . Fie i primul i ultimul vrf al drumului , cum drumul este un graf secvenial, n acesta avem:

i dac este par (1)i i dac este impar (2).Reintroducnd apoi arcul constatm c (2) contrazice definiia funciei Grundy, pe cnd (1) nu. Deci n graful dat funcia Grundy coincide cu cea obinut de-a lungul drumului, dac circuitul are un numr par de arce i nu exist dac acest numr e impar.Corolar Grafurile formate dintr-un singur circuit de lungime par admit dou funcii Grundy.

Observaie 1 Propoziia 3 i corolarul su se extind de la sine la grafurile care conin un singur circuit.

Singurul lucru care se schimb n raionamentul de mai sus este c nu mai are obligatoriu valoarea 1.

Exemplul 3 Fie graful:

are un singur circuit de lungime 2. Suprimnd arcul se obine graful fr circuite de mai jos

sau suprimnd arcul obinem a doua soluie cea dat de graful fr circuite de mai jos

Observaie 2.Din propoziia 3 nu rezult c, dac un graf conine circuite de lungime impar, el nu admite funcii Grundy.Exemplul 4

Fie graful cu dou circuite

din care unul de lungime 3 i admite totui funcia Grundy ale crei valori sunt notate n vrfuri. Ea s-a obinut suprimnd arcul comun ambelor circuite, ceea ce conduce la graful urmtor.

Reintroducerea arcului suprimat nu contrazice definiia funciei lui Grundy, deci cea gsit n graful fr circuite este admis i de graful dat. Observm ns pe figur c deschiznd circuitele prin nlturarea arcului nu se obine o soluie

Pentru cutarea funciei Grundy n grafurile cu circuite ne putem folosi de urmtorul algoritm:1) Deschidem toate circuitele, suprimnd arce care le sunt comune i pe care le alegem astfel nct n extremitile lor terminale circuitele s se despart fr a rupe conexiunile grafului. Este recomandabil ca numrul arcelor elementare s fie ct mai mic.2) Cutm funcia lui Grundy n graficul parial astfel obinut.

3) Reintroducem arcele suprimate; dac n extremitile lor are valori distincte, atunci este o funie Grundy pentru graful dat.

Exemplul 5Fie graful

Suprimnd n graful dat arcele i se obine graful fr circuite

n acesta avem i deci am gsit i o funcie Grundy a grafului cu circuite. Soluia nu este unic: prin eliminarea din graful dat a arcelor i se gsete un alt graf parial fr circuite i funcia xx1x2x3x4x5x6x7x8x9x10x11

42133121231

Pentru grafurile neorientate funcia Grundy se definete cernd s se ataeze fiecrui vrf cel mai mic numr natural distinct de cel din vrfurile adiacente.Proprietile ce urmeaz sunt imediate:

1) Orice graf conex neorientat admite cel puin dou funcii Grundy, ele se pot construi inclusiv n cazul arborilor ncepnd de la orice pentru care lum .

2) Orice arbore admite cel puin o funcie Grundy cu valorile din mulimea cci totdeauna putem lua unde este rdcina.

3) Numrul poate diferi de la o funcie Grundy la alta n acelai graf. n legtur cu aceasta se poate cere maximul i minimul lui p pe mulimea tuturor funciilor lui Grundy pe care le admite un graf neorientat. Este evident .4) Toate funciile Grundy dintr-un graf neorientat, dar complet au acelai p i avem p = # X5) Orice graf neorientat care nu conine cicluri de lungimi impare admite cel puin o funcie Grundy cu valori n .6) Grafurile neorientate care conin circuite de lungimi impare au pentru oricare dintre funciile lui Grundy pe care le admit.3.Numr cromatic; clas cromaticFie un graf neorientat i presupunem c colorat vrfurile astfel nct dac dou sunt adiacente ele s nu aib aceeai culoare. Fie p numrul culorilor folosite, atunci G se numete p-cromatic. Cel mai mic numr p pe care-l admite G se numete numrul su cromatic i se noteaz cu .

Legtura dintre funciile Grundy corespunztoare lui G i numrul cromatic a lui G este evident n baza propoziiei 3) din paragraful precedent.

Dac asociem cte o culoare fiecreia dintre cele p valori pe care le ia o anumit funcie Grundy a grafului, acesta devine p-cromatic, iar . Deci avem . Cum ne ntrebm care e condiia necesar i suficient ca . Este evident c oricare arbore se bucur de aceast proprietate.Propoziia 1 (Kning)

Un graf neorientat are numrul cromatic 2 dac i numai dac nu are cicluri de lungime impar.Demonstraie

Dac G nu conine cicluri de lungime impar din propoziia 5, rezult c .

Dac n G exist mcar un ciclu de lungime impar, atunci se aplic proprietatea 6 i deci .

Observaie: E suficient lipsa ciclurilor elementare de lungime impar pentru ca teorema lui Kning s se aplice, cci celelalte se desfac n cicluri elementare dintre care mcar unul este obligatoriu de lungime impar.

Propoziie 2 Orice graf neorientat care admite o funcie Grundy cu valorile 1, 2, ... p este p-cromatic.

E suficient s nlocuim fiecare din cele p valori cu cte o culoare. Din definiia funciei Grundy rezult atunci c orice vrfuri adiacente vor fi colorate diferit. Deci, pentru ca un graf s fie p-cromatic e suficient ca el s admit o funcie Grundy cu p valori.

Procednd invers, adic asociind celor p culori dintr-un graf p-cromatic numerele 1, 2, ... p, nu se obine ntotdeauna o funcie Grundy.Explicaia o d proprietatea urmtoare.

Propoziia 3 Funciile lui Grundy ce se pot deduce din p-cromatismul unui graf au cel mult p valori.

Fie partiia mulimii X a vrfurilor unui graf p-cromatic, dup culoarea lor. Trecem la o nou partiie . Submulimile (cu ) le formm iterativ, astfel:

include pe X1 reunit succesiv cu vrfurile :

a) neadiacente cu cele din X1;b) neadiacente cu cele din X1 i cu cele de la a);

c) neadiacente cu cele din X1 i cu cele de la a) i b);

............................................................................................... .

include pe completat succesiv cu vrfurile:

) neadiacente cu cele din

) neadiacente cu cele din i cu cele din ).

conine pe

Fie r cel mai mare indice al submulimii nevide, astfel obinute . Funcia g(x) definit prin este evident o funcie Grundy n graful dat.

Observaie : Modificnd numerotarea submulimilor Xi, r se poate schimba, dar totdeauna .

Exemplu Graful de mai jos este 4-cromatic, vrfurile sale fiind colorate n alb (a), rou (r), verde (v) i negru (n).

Pornind de la cromatismul grafului cutm ca n demonstraia de mai sus, funciile Grundy.S adoptm ordinea v a n r i rezult ; ; i .

Obinem

Gsim urmtoarea funcie Grundy:

xx1x2x3x4x5x6x7x8x9x10x11x12

231112322132

Cum n graf exist cicluri de lungime impar, nseamn c, pentru mulimea vrfurilor sale, funciile lui Grundy nu pot lua mai puin 3 valori, rezult .Propoziia 4. O condiie necesar i suficient pentru este ca graful s nu admit funcii Grundy cu mai puin de s valori.Clasa cromatic a unui graf neorientat este cel mai mic numr de culori ce pot fi atribuite muchiilor sale astfel nct orice muchii adiacente s fie colorate diferit.

Problema determinrii clasei cromatice a unui graf este echivalent cu aceea a gsirii numrului cromatic al altuia, care se deduce astfel din cel dat:

muchiile grafului dat se reprezint prin vrfuri n cel transformat;

dou vrfuri din al doilea graf se unesc printr-o muchie dac i numai dac muchiile respective sunt adiacente n cel iniial.

Presupunem c am adoptat aceeai numerotare pentru cele cinci vrfuri ca i pentru culorile lor i c vrfurile sunt dispuse n jurul lui x n ordinea numerotrii.

Fie G1,3 subgraful ale crui vrfuri sunt colorate cu c1 i cu c3. Dac a1 i a3 aparin unor componente diferite ale lui G1,3 permutm ntre ele culorile c1 i c3 n componenta ce conine pe a, deci a1 va fi colorat n 3 i deci lui xi se poate da culoarea lui c1.Dac a1 i a3 aparin aceleiai componente n G1,3 atunci a2 i a4 sunt obligatoriu n componente diferiteale subgrafului G2,4, altfel G nu ar fi planar, i se repet cele de mai sus n G2,4 deci x poate fi colorat cu c2.

Din propoziia de mai sus rezult doar c toate grafurile planare conexe au , dar nu i .

Se presupune c , supoziie care poart numele de conjunctura celor patru culori ntruct practica o confirm, dar nu a putut fi nc demonstrat. Exist grafuri planare cu . Conjunctura celor patru culori se refer la mulimea tuturor grafurilor planare.

Propoziia 2 (teorema lui Heowood)

ntr-un graf planar G, conex i fr istmuri, ale crui vrfuri au toate gradul 3, dac una din proprietile urmtoare e adevrat, atunci sunt toate adevrate.

1) Feele lui G pot fi distinctiv colorate cu 4 culori;2) Muchiile lui G pot fi distinctiv colorate cu 3 culori;

3) Fiecare vrf x poate fi etichetat cu un numr p(x) egal cu +1 sau -1, astfel ca de-a lungul conturului al oeicrei fee s avem: mod 3 (*)

Demonstraie

Demonstraie

Fie cele patru culori ale feelor 1, 2, 3, culorile pe care le vom folosi pentru muchii. Colorm cu 1 muchiile ce separ pe c1 de c2 i pe cele dintre c3 i c4. Apoi folosim:4. Cromatismul grafurilor planare.Primele probleme legate de cromatismul grafurilor planare au fost cele de colorare a hrilor geografice. Lum pe harta e reprezint mprirea administrativ-teritorial, care este un graf planar, cte un punct situat n interiorul feelor finite. Considerm aceste puncte drept vrfuri ntr-un nou graf. ntre dou vrfuri trasm o muchie dac i numai dac feele din graful iniial pe care ele le reprezint sunt adiacente. Noul graf este evident tot planar i se numete dualul celui dat. dac vrem s colorm distinctiv submpririle teritoriale ale hrii, feele adiacente trebuie s aib culori diferite.

Problema determinrii numrului minim de culori necesare revine, aflrii numrului cromatic al grafului dual. Principalul rezultat obinut n aceast privin este dat de propoziia:

Propoziia 1Orice graf planar i conex cu cel puin 5 vrfuri este 5-cromatic.

Demonstraie Pentru # X = 5, propoziia este o tautologie.Deci, dac vom demonstra pentru cazul #X = n prin inducie matematic, atunci propoziia va fi valabil pentru orice # X.

Fie G un graf planar cu n vrfuri i x un vrf al su cu . Suprimnd acest vrf, subgraful rmas este 5-cromatic (din presupunerea fcut n inducie). Deci i putem colora vrfurile cu culorile .

Dac , pentru x poate fi disponibil cel puin una din aceste culori.

Dac i printre vrfurile adiacente cu x, sunt cel puin dou cu aceeai culoare, de asemenea putem folosi una din culorile neutilizate atribuind-o lui x. Rmne cazul n ipoteza c toi ai sunt distinci colorai.Pe coloana muchiilor ce despart pe c1 de c3 i c2 de c4 i atribuim pe 3 muchiilor ce despart pe c1 de c4 i c2 de c3 (fig.1). rezult o colorare diferit a muchiilor adiacente, cci altfel ar exista fee adiacente identic colorate.

Demonstrm

Graful parial G1,2 cu muchile colorate 1 i 2 este planar i are toate vrfurile de gradul 2 (fig.2). Deci acest graf are o fa finit i o fa infinit . La fel pentru G1,3 ale crui fee le etichetm cu i (fig.3). Prin suprapunerea lui G1,2 cu G1,3 pe feele lui G se obin 4 combinaii (fig.4) pentru care lum , , , sau orice alt permutare a culorilor ci.

Dou fee adiacente nu pot fi la fel colorate fr s fie contrazis ipoteza.

Demonstrm

Adoptm un sens de rotaie n plan notat cu +, iar sensul contrar l notm cu -. Punem cnd muchiile incidente n x i colorate n 1, 2, 3 se succed n sensul + i n caz contrar (fig.5) (n figur sensul + este sensul trigonometric).Parcurgem n sensul + conturul al unei fee pornind de la o muchie oarecare. Cnd trecem printr-un vrf marcat cu -1, culorile muchiilor ciclului pe care acest punct le separ se succed n sensul sgeii prin permutarea circular (), pe cnd la trecerea prin vrful x cu p(x) = +1 ele se permut n sens invers. Deci, cnd ajungem din nou la muchia iniial, suma algebric (x) va fi n mod necesar un multiplu de 3.Demonstrm

Evident, cci putem aplica de-a lungul fiecrui contur procedeul de mai sus, trecnd de la marcajul dat al vrfurilor, la colorarea arcelor. la nchiderea conturului nu poate surveni o contradicie dect dac marcajul vrfurilor nu satisface condiia (x).

Oricrei etichetri a vrfurilor care satisface condiia (x) i corespund trei posibiliti de colorare a arcelor, dup cum afectm arcului iniial pe 1, 2 sau 3. Cele trei soluii se deduc una din alta prin permutarea circular a culorilor. Pentru grafurile planare, conexe i fr istmuri, ale cror vrfuri au toate gradul 3, din propoziia 2 decurg corolarele:Corolarul 1 Cnd numrul muchiilor conturului oricrei fee este un multiplu de 3, e posibil colorarea feelor cu 4 culori.

Corolarul 2 Cnd numrul muchiilor conturului oricrei fee este un multiplu de 2, e posibil colorarea feelor cu 4 culori.

5. Probleme rezolvateProblema 1

Fie dou grafuri i avnd aceeai mulime de vrfuri i B B matricele asociate corespunztor.

S se verifice:

a) matricea B+B corespunde grafului

b) matricea BB corespunde grafului definit astfel: de la un vrf j se duc attea arce cte drumuri distincte sunt, care pleac dintr-un arc U urmat de un arc din V.Grafurile fiind:

Rezolvare: Matricea B+B corespunde grafului , iar matricea BB corespunde grafului reprezentat dup enunul b) din problem, figurate mai jos:

Matricele sunt:

Matricea B+B este tocmai matricea ataat grafului din figura a), iar matricea BB este tocmai matricea ataat grafului din figura b).

Problema 1 Fie o mulime . n mulimea X se definete o aplicaie prin urmtoarea coresponden:

Se cere s se reprezinte graful

Rezolvare:Considerm c elementele mulimii X sunt vrfurile grafului, aplicaia definit n enunul exerciiului definete complet graful . Pentru aceasta, vom defini arcul (a,b) dac i numai dac , dup cum se vede n figura de mai jos.

Problema 2

Fie graful reprezentat mai jos. S se determine nchiderea tranzitiv a acestui graf.

Prin definiie nchiderea tranzitiv a grafului este tot un graf , obinut din graful dat, unde este o aplicaie a lui X n X, care asociaz fiecrui vrf x o submulime a lui X format din x i din toate vrfurile accesibile din x prin drumuri posibile din graful G. Cu alte cuvinte, pentru x din X avem

unde ,

Avem:

de unde rezult

Problem 3

S se determine valorile funciei Grundy pentru graful reprezentat mai jos.

Rezolvare:

Prin definiie o funcie g definit pe mulimea X este o funcie Grundy, dac orice valoare a sa este un ntreg pozitiv sau zero i g(x) este cel mai mic ntreg pozitiv care nu aparine mulimii .Altfel spus, funcia g definit pe mulimea X este o funcie Grundy dac:

(1)

cu

(2)

Pentru determinarea valorilor funciei g folosim urmtorul algoritm:

a) Presupunem submulimea din definiia funciei Grundy pentru orice g(x) = 0;b) Pentru orice x din lum g(x)=1;

c) Procedm din aproape n aproape, determinm submulimea i pentru orice x din Xi, vom lua i . Pentru un graf dat, funcia Grundy dac exist, nu este obligatoriu s fie unic.Pentru graful dat avem:

a) pentru c ; deci

b) pentru c dar deci

c) pentru c Deci

d)

cci i , deci

e) cci ,

deci

Deci valorile funciei Grundy pentru graful dat sunt:

i aceste valori determin o partiie a mulimii X n submulimile:

pentru care

pentru care

pentru care

care sunt clase de echivalen determinate de relaia

III. POLIEDRE CONVEXE1. Poligoane convexeSe numete mulime convex o mulime M de puncte care se bucur de proprietatea: dac atunci

Observaii:

1) Figura 1a reprezint o mulime convex, iar figura 1b reprezint o mulime neconvex.

2) Mulimea vid i mulimea format dintr-un singur punct sunt mulimi convexe.3) Mulimea format din dou puncte distincte nu este convex.

Teorem 1Orice intersecie de mulimi convexe este convex.

Fie M1, M2 ... Mn ... mulimi convexe. Notm cu i fie este mulime convex.Interiorul unghiului propriu este mulimea de puncte unde i (fig.2).Proprieti 1) Planul i orice dreapt sunt mulimi convexe;

2) Orice segment i orice semidreapt sunt mulimi convexe;

3) Semiplanele deschise i semiplanele nchise sunt mulimi convexe;

4) nteriorul unui unghi este o mulime convex, fiind intersecia a dou semiplane deschise care sunt convexe;

5) Dac interiorul unui triunghi ABC se definete astfel unde , , atunci este o mulime convex.

O linie poligonal este o mulime de forma:

, unde punctele se numesc vrfurile liniei L, iar segmentele se numesc laturile ei; laturile i se zic vecine (fig.3a).Linia poligonal nchis este linia poligonal pentru care (fig.3b), i simplu nchis dac n plus orice dou laturi vecine nu au punct comun i dou laturi vecine au suporturi diferite.

O linie poligonal simplu nchis se numete poligon. Figura 3b nu este poligon pentru c un poligon nu se autointersecteaz. Denumirea poligonului se d n funcie de numrul de laturi pe care le are.

Segmentele PiPK care nu sunt laturi se numesc diagonale. Poligonul cu vrfurile P1,P2,P3, ... Pn va fi notat cu P1P2...Pn. Poligonul P1P2...Pn se numete convex, dac pentru fiecare latur , toate vrfurile diferite de Pk i PK+1 se gsesc de aceeai parte a dreptei PkPK+1, pentru i (fig.3c).

Interiorul unui poligon convex este intersecia semiplanelor deschise limitate de suporturile laturilor poligonului i care conine vrfurile nesituate pe laturile respective (fig.4a).

Dac notm pentru i atunci .Reuniunea dintre poligonul convex P1P2...Pn i se numete suprafa poligonal convex.

Se numete suprafa poligonal o mulime de puncte din plan care este reuniunea unui numr finit de suprafee poligonale convexe, acestea avnd dou cte dou interioare disjuncte. (fig.4b)

Dac S este o suprafa poligonal i [L1] [L2] [LK] sunt suprafeele poligonale convexe respective, adic i pentru , atunci vom spune c mulimea constituie o descompunere a suprafeei poligonale S (fig.4c).Pentru suprafaa poligonal convex poligonul se numete frontier.

Un punct P al unei suprafee poligonale S se numete punct interior al lui S dac exist un disc cu centrul s inclus n S. Punctele lui S care nu sunt interioare lui S sunt puncte frontier pentru S i formeaz frontiera lui S.

Din definiie rezult c orice suprafa poligonal se descompune n suprafee poligonale convexe.

Teorem

O suprafa poligonal convex cu n-laturi () se descompune n n-2 suprafee triunghiulare.

Demonstraie Se consider poligonul convex i dreapta P1P3, o dreapt care nu este suportul unei laturi a lui L are cel mult dou puncte comune cu L, deci dreapta P1P3 intersecteaz poligonul L numai n P1 i P3. Deci punctele P4P5Pn sunt de aceeai parte a lui P1P3, deci P1P3 P4Pn este un poligon convex. Deoarece P3 se afl n interiorul P2P1Pn rezult c P2 i Pn se afl de o parte i de alta a dreptei P1P3. Deci punctele P2 i P4, P5Pn se afl n semiplane opuse fa de P1P3, adic interiorul triunghiului P1P2P3 i interiorul poligonului P1P3 P4Pn se afl n semiplane opuse, avnd intersecia vid i .Dac aplicm succesiv rezultatul obinut mai sus pentru suprafeele poligonale , etc, care au fiecare cu o latur mai puin dect precedenta i astfel obinem rezultatul cerut de teorem, figura 5.

Consecin: Orice suprafa poligonal poate fi descompus n triunghiuri i descompunerea nu este unic.

2. Mulimi poliedrale

Mulimile poliedrale constituie analogul suprafeelor poligonale din plan, cu deosebirea c n acest caz suprafeele poligonale convexe sunt nlocuite cu prisme, piramide i trunchiuri de piramid.

Se numete mulime poliedral o mulime de puncte din spaiu care este reuniunea unui numr finit de prisme, piramide i trunchiuri de piramid, acestea avnd dou cte dou interioare disjuncte.

Dac P este mulimea poliedral, iar sunt prismele piramidale i trunchiurile de piramide respective, adic i , , atunci se va spune c mulimea P se descompune n mulimile .Un punct O al mulimii poliedrale P se numete punct interior al lui P dac exist un corp sferic cu centrul n O inclus n P. Punctele mulimii P ce nu sunt interioare acesteia se numesc puncte de frontier.

Teorem 1Orice mulime poliedral se poate descompune n tetraedre.

Demonstraia rezult din proprietile de descompunere a prismelor, piramidelor i trunchiurilor de piramid.

Proprietate 1.Orice prism se descompune n prisme triunghiulare.

Demonstraie:

Se consider prisma P cu bazele S i S' . tim c suprafaa poligonal S se descompune n suprafee triunghiulare . Prismele determinate de bazele , planul bazei S' i avnd 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.

Demonstraie:

Se consider prisma i piramidele , i , aceste trei piramide au interioare disjuncte, deoarece oricare dou dintre ele au ca intersecie 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 suprafee triunghiulare care mpreun cu vrful 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 proprietii 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 mulimi poliedrale sunt congruente i una din ele este descompus n tetraedrele atunci i cealalt poate fi descompus n tetraedrele astfe ca , i= 1,2,n.Un corespondent n spaiu al suprafeelor poligonale cu frontiera poligon l constituie poliedrele.

O mulime poliedral P se numete poliedru dac are urmtoarele proprieti:

1. Pentru orice dou puncte interioare ale lui P, exist o linie poligonal cu extremitile n cele dou puncte, format numai din puncte interioare.2. Pentru orice dou puncte care nu aparin lui P exist o linie poligonal cu extremitile n cele dou puncte, format numai din puncte care nu aparin lui P.

Se numete vrf al unui poliedru un punct care aparine frontierei poliedrului i nu aparine nici unui segment deschis inclus n frontier.

Se numete muchie a unui poliedru un segment determinat de dou vrfuri ale poliedrului, inclus n frontier i ale crei puncte nu aparin interiorului nici unei suprafee poligonale inclus n frontier.

Un poliedru se zice convex dac este mulime convex. n cazul unui poliedru convex, frontiera este o reuniune de suprafee poligonale convexe, a cror laturi sunt muchii ale poliedrului. O astfel de suprafa poligonal convex se numete fa a poliedrului.Se numete reea poligonal simpl o suprafa poligonal [P] cu frontiera poligon, mpreun cu o descompunere a ei n suprafee poligonale convexe . Cele f suprafee [Pi] se numesc feele reelei, iar vrfurile i laturile acestora se numesc vrfurile i muchiile reelei, numrul lor fiind notat cu v respectiv m.Teorem 2.n orice reea poligonal simpl avem .

Demonstraie:

Dac Pi are 4 laturi sau mai multe, ducnd o diagonal a lui Pi, se obine o reea nou n care numrul vrfurilor este tot v, dar exist o muchie n plus i o fa n plus, deci numrul nu s-a modificat. Aadar, dac descompunem fiecare [Pi] n suprafee triunghiulare, se obine o reea pentru care rmne acelai. Deci este suficient s demonstrm teorema pentru cazul cnd fiecare Pi este triunghi.

Aplicm inducia matematic n raport cu f.

Dac f = 1 avem un singur triunghi, deci v = 3, m = 3 i deci .Presupunem proprietatea adevrat pentru orice reea n care numrul feelor este mai mic sau egal cu f-1. Considerm o suprafa triunghiular [ABC] a reelei avnd latura [AB] n comun cu P i deosebim dou cazuri:

a) C este un punct interior lui [P] (fig.3). Scond din reea , se obine o reea simpl cu f-1 fee, v vrfuri i m-1 muchii. n virtutea ipotezei din inducie avem: . Deci .

b) Dac , (fig.4), atunci [AC] sau [BC] descompune reeaua [P] n reele poligonale simple[P'] i [P''] cu v', m', f' respectiv v'', m'' i f'' vrfuri, muchii i fee pentru care i . Deoarece , i i deci .Teorema 3.

Dac v, m, f reprezint respectiv numrul vrfurilor, muchiilor i feelor unui poliedru convex, atunci .

Demonstraie:

Fie o fa a lui P, planul lui L, iar un plan paralel cu , astfel ca poliedrul P s fie situat ntre i . Lum un punct i o dreapt , N i IntP fiind de o parte i de alta a lui . Notm 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 vrfurile unei reele poligonale simple avnd v vrfuri, m muchii i f fee.din teorema 2 deci .Observaie:

Dac se suprim faa L se obine o reea spaial simpl R, aezat pe suprafaa poliedrului P. Acesteia i-am asociat prin proiectarea din N o reea poligonal simpl n planul . Bazndu-ne pe intuiie, putem s obinem asocierea respectiv i n alt mod. Ne imaginm c reeaua R este realizat dintr-o membran elastic pe care o ntindem pn ce devine plan, ea se deformeaz i muchiile devin arce de curbe, dar acestea pot fi nlocuite cu segmente de drepte fr a schimba numrul v, m i f-1 i teorema 3 rezult din teorema 2. Acest procedeu poate fi aplicat ori de cte ori reeaua spaial, presupus elastic, poate fi ntins astfel nct s devin plan. Deci relaia lui Euler este valabil i pentru alte tipuri de poliedre, nu numai pentru cele convexe.

Fie corpul din figura 6 pentru care v = 9, m = 16, f = 9 i

EMBED Equation.3 acest corp poate fi ntins n plan.

Dac considerm corpul din figura 7, de form inelar, reeaua feelor rmase nu se mai poate ntinde pe un plan i avem: v = 16, m = 32, f = 16 i .Dac un corp este strpuns de p ori, zicem c suprafaa lui este de gen p i n acest caz .

Numrul se numete caracteristica eulerian a suprafeei respective. Suprafaa unui poliedru convex este de gen O i are carqacteristica eulerian egal cu 2.Un poliedru convex P se numete poliedru regulat dac fiecare vrf a lui P aparine aceluiai numr de muchii, toate feele sunt suprafee poligonale regulate congruente i toate unghiurile diedre, determinat de fee cu muchie comun sunt congruente.

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

Demonstraie:

Notm prin q numrul muchiilor de pe o fa i cu p numrul muchiilor care pleac dintr-un vrf. Pentru c fiecare muchie e inclus n dou fee i are dou vrfuri, rezult: , deci

(1) i

Dar din relaia lui Euler avem

sau(2)

Deci (3) de unde .

Deci , la fel i , iar dac atunci .

Aadar 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. Artm c pentru fiecare pereche din irul 4 exist un poliedru regulat.

1) Dac p = 3 i q = 3

Din (2) obinem m = 6, iar din (1) obinem v = 4 i f = 4, acesta este tetraedrul regulat.2) Dac p = 3 i q = 4 i , acesta este cubul sau hexaedrul regulat (figura 8a).3) Cazul i f = 8, acest poliedru poate fi realizat lund ca vrfuri centrele feelor unul cub (figura 8a).

4) Cazul i f = 20, acest poliedru poate fi realizat n felul urmtor:

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 nct G s fie mijlocul arcului mic A'B'. Determinm distana aa nct , notm 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 lum punctul L pentru care O'L=OF se obin alte cinci triunghiuri echilaterale de latur a: GHL, HIL, IJL, JKL, KGL i [FABCDEGHIJKL] este un poliedru regulat cu 20 de fee, numit icosaedru regulat (figura 8b i 8c).

5) Cazul

Centrele feelor unui icosaedru regulat formeaz vrfurile unui poliedru regulat cu 12 fee numit dodecaedru regulat (figura 8d).

3. PROBLEME REZOLVATE

Problema 1

Un vrf al unui patrulater ABCD se marcheaz dac i numai dac el este situat n interiorul unghiului opus. S se demonstreze:

a) Cel puin unul din vrfurile A, B, C, D va fi marcat;

b) Dac dou vrfuri sunt marcate, atunci patrulaterul este convex i toate vrfurile vor fi marcate.

Demonstraie:

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

1) Dac ABCD este patrulater convex , din faptul c diagonalele unui patrulater convex au un punct comun, c toate vrfurile sale sunt situate n interiorul unghiului opus i deci toate vrfurile sunt marcate.2) Dac ABCD este patrulater neconvex, exist cel puin o latur, s zicem [AB], al crui suport separ celelalte vrfuri C i D, deci i . Evident c deoarece definiia poligonului nu admite poligoane care se autointersecteaz. Din

EMBED Equation.3 i sau .

Cazul I.

Vom arta c , i adic B este un vrf marcat, iar A, C, D sunt nemarcate.Notm AB = a, BC = b, DA = d, i avem i , dar i din i , dar , dar i , din , dar i deci i = =.Artm c , i .

1)

EMBED Equation.3

EMBED Equation.3 2)

EMBED Equation.3 din , dar .

EMBED Equation.3 ,

EMBED Equation.3 Cazul II. - se trateaz analogb) Dac dou vrfuri ale unui patrulater sunt marcate, atunci patrulaterul este convex, un patrulater neconvex are un singur vrf nemarcat, deci toate vrfurile sunt marcate.Problema 2.Intersecia semiplanelor nchise limitate de suporturile laturilor unui poligon convex P coincide cu mulimea .

Demonstraie:Fie poligonul

Fie I intersecia considerat. Se tie c este intersecia semiplanelor deschise limitate de suporturile laturilor poligonului i care conine vrfurile nesituate pe laturile respective. Dar orice semiplan deschis este inclus n semiplanul nchis mrginit de aceeai dreapt, deci intersecia semiplanelor nchise .Din convexitatea poligonului P rezult c pentru fiecare latur , toate vrfurile diferite de PK i PK+1 se gsesc de aceeai parte a dreptei PKPK+1. Deci exist n I un singur semiplan nchis mrginit de PKPK+1 care include frontiera sa. Dar , deci i .Demonstrm incluziunea invers, adic . Fie , deci tuturor semiplanelor nchise nemrginite de suporturi laturile .

Pentru M avem urmtoarele situaii:

1) dar M aparine tuturor semiplanelor nchise mrginite de dreapta , deci M aparine interseciei lor, deci .2) Exist K, aa nct , dar M se gsete i n toate celelalte n-1 semiplane nchise mrginite de suporturile celorlalte laturi diferite de . Deci M se gsete i n semiplanul nchis mrginit de dreptele i care conine i celelalte vrfuri diferite de Pk-1 i Pk, rezult deci c M i Pk+1 sunt de aceeai parte a dreptei i deci . La fel se gsete i n semiplanul mrginit de dreapta i care conine celelalte vrfuri M i Pk sunt de aceeai parte a dreptei deci .Din i

i deci , iar din dubla incluziune .Problema 3

Reuniunea unui poligon convex cu interiorul su este o mulime convex.

Demonstraie:

Din problema 2 avem , adic intersecia celor n semiplane nchise limitate de suporturile laturilor . Dar semiplanele nchise sunt mulimi convexe i deci ntersecia acestora este tot o mulime convex.

Observaie: se numete 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.

Demonstraie:

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.Demonstraie:

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 aa nct prin ipotez i deci , dar i aadar.

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 aa nct i deci Pi sau Pi+1 aparin semiplanului . La fel exist aa nct de unde sau , deci ar exista vrfuri ale poligonului de o parte i de alta a dreptei .Problema 6.

Dac este un poligon convex unde atunci este tot un poligon convex.

Demonstraie:

Notm i . Din problema 5 rezult c d nu poate avea mai mult de dou puncte comune cu poligonul convex P. De aici avem cci altfel d ar avea trei puncte comune cu poligonul P. Deci , adic . La fel gsim care indic c . Procednd analog pn la segmentul gsim c se gsesc de aceeai parte a suportului laturii . Pentru celelalte laturi ale poligonului vrfurile diferite de extremitile laturilor respective se gsesc de aceeai parte a suportului su, 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.

Demonstraie:

Folosind problema 6, din poligon convex, este poligon convex i aa mai departe este poligon convex. Putem renuna la un numr de vrfuri consecutive i obinem un poligon format din vrfurile rmase care este tot convex. Folosind aceeai procedur ca mai sus, din poligonul renunnd la vrfurile , obinem poligonul , care este tot convex cu . Putem continua acest procedeu i obinem astfel poligonul care va fi tot convex.Problema 8.

Fie un poligon convex, i . S se arate c . Cte puncte are aceast mulime?

Demonstraie:

Se tie c este intersecia tuturor semiplanelor deschise limitate de suporturile laturilor ale poligonului i care conine vrfurile pe laturile respective. Din sau .

1) Dac .

2) Dac i exist k astfel nct B s nu aparin semiplanului mrginit de dreapta i care conine celelalte vrfuri. Punctul A aparine acestui semiplan, deci A i B se gsesc de o parte i de alta a dreptei . Am demonstrat c exist mai multe drepte astfel nct A i B s se gseasc de o parte i de alta a lor, rezult .3) Fie cel mai mic dintre segmentele . Presupunem c i i , dar i deci A i sunt de o parte i de alta a cel puin unei drepte . Deci exist aadar.Din .

Din ceea ce este n contradicie 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 aa nct . Dac , considerm 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 aceeai concluzie, deci AB i L au dou puncte comune.

Problema 9.

ntr-un poliedru convex se noteaz cu m numrul muchiilor, cu numrul feelor triunghiulare, patrulatere, pentagonale i cu numrul vrfurilor din care pleac 3,4,5... muchii. S se arate c:

1)

2) Dac notm cu f numrul feelor i cu v numrul vrfurilor unui poligon convex oarecare, atunci

i

.

Demonstraie:

1) - Orice muchie a unui poliedru convex este comun la dou fee, deci:

- Orice muchie a poliedrului trece prin dou vrfuri, deci

2) innd cont de 1), avem i , iar din relaia v+f-m=2

m+2=v+f

Prin nsumarea celor dou egaliti avem:

, deci ,

dar

i la fel .Problema 10.

Adunnd msurile unghiurilor tutror feelor unui poliedru convex, se obine dublul sumei msurilor unghiurilor unui poligon convex avnd acelai numr de vrfuri.

Demonstraie:

Notm cu numrul feelor care au i laturi i cu suma unghiurilor feei avem: , atunci S a msurilor unghiurilor poliedrului va fi:

Problema 11.

Artai c dac un punct variaz n interiorul unui poliedru regulat, suma distanelor sale la planele feelor rmne constant.

Demonstraie:

Fie un poliedru regulat cu feele unde i M un punct n interiorul su. Dac unim M cu vrful poliedrului se obin n piramide cu vrful n M i bazele. Fie piciorul perpendicularelor din M pe feele atunci avem:

unde V este volumul poliedrului.

Dar deci avem: .

4. UNELE PROBLEME DE INEGALITI

N TETRAEDRUProblema 1.

n interiorul tetraedrului se alege punctul M. S se arate c una din laturile tetraedrului se vede din punctul M sub unghi , astfel nct:

.

Demonstraie:Presupunem prin absurd c toate muchiile tetraedrului [ABCD] se vd din punctul M sub unghiuri de cosinus mai mare dect . Considernd vrfurile tetraedrului pe dreptele MA, MB, MC, MD le lum astfel nct toate vrfurile tetraedrului s fie la distana 1 de M. Este clar c prin acest procedeu unghiurile sub care se vd laturile tetraedrului din punctul M nu s-au schimbat. Fie ABC faa 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 aceeai parte a planului ABC ca i punctul D. Dac , atunci . Aceste inegaliti ne spun c toate laturile tetraedrului se afl de o parte a planului ce trece prin mijlocul segmentului DD1, perpendicular pe acest segment. Se obine o contradicie deoarece punctul M se afl n planul , iar pe de alt parte este dat n interiorul tetraedrului. Deci . Cum , toate muchiile tetraedrului [ABCD1] se vd din M sub un unghi de cosinus mai mare ca (-1/3). Tot de aici deducem c proiecia 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 ascuitunghic. 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: . Contradicie.Problema 2.n orice tetraedru [ABCD] cu notaiile cunoscute, avem inegalitile:

a)

b)

Demonstraie:a) Din inegalitatea mediilor avem:

.

b) Se tie c dac sunt laturile unui triunghi atunci:

(1)

nlocuind n (1) pe i obinem 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 nct distana d dintre aceste plane s satisfac inegelitatea: , unde p reprezint suma ptratelor muchiilor tetraedrului.

Demonstraie:Notm 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 distana dintre i nu depete SM. Notm cu M mulimea punctelor cuprinse ntre planele i inclusiv cele dou plane. Cum M este o mulime convex i A,B,C,D M rezult c tetraedrul [A1A2A3A4] este inclus n M.

Problema 4.n orice tetraedru [ABCD] folosind notaiile cunoscute avem inegalitile:

a)

b)

Demonstraie:

a) Avem i analoagele.

Conform inegalitii mediilor avem:

i analoagele;

.

b) Din inegalitatea mediilor avem

i analoagele; prin adunare

.

Problema 5.n orice tetraedru [ABCD] are loc inegalitatea:

.

Notaiile sunt cele cunoscute n tetraedrul [ABCD].

Demonstraie:

(i analoagele). Notm cu ;

.

ns ;

. Inegalitatea din enun este echivalent cu a demonstra c: ;

;

, inegalitate adevrat.

Egalitatea are loc numai dac este echifacial.

Problema 6.Folosind notaiile cunoscute ntr-un tetraedru [ABCD] s se arate c:

a)

b)

c)

Demonstraie:a) , etc.

(am folosit inegalitatea: )

b) ,etc. .

c)

.

Egalitile au loc numai dac [ABCD] este echifacial.IV. CONSIDERAII METODICE

Este evident faptul c niciodat n istoria colii, a nvmntului romnesc nu a existat atta preocupare pentru perfecionare, pentru modernizarea multidirecional a acestui secto de activitate social.

Dinamismul societii contemporane, determinat de aciunea concomitent a revoluiei social-politice n domeniul tiinei i tehnicii solicit coala la reorientarea i reorganizarea aciunilor ei instructiv-educative, n vederea integrrii ei rapide, eficiente, creatoare a tinerelor generaii ntr-o via social cu ritmuri extrem de rapide ale dezvoltrii.

n condiiile societii noastre elevul nu mai poate fi considerat un obiect asupra cruia se exercit aciunea educativ, ci i subiect al formrii propriei sale personaliti.

Cadrul diddactic nu mai acioneaz unilateral ci este animat de principiul colaborrii cu elevul n tot ce ntreprinde asumndu-i sarcina diagnosticrii i satisfacerii nevoilor celui care nva, cutnd s acioneze la maximum activitatea elevului, determinnd din partea acestuia o autentic munc independent, orientat spre cutare i dobndire prin eforturi proprii a cunotinelor, a priceperilor i deprinderilor.Datoria principal a profesorului de matematic este aceea de a-i nva pe elevi s gndeasc matematic, deci el trebuie s se strduiasc nu numai s transmit informaii ci i s dezvolte la elevii si capacitatea de a utiliza informaiile n rezolvarea problemelor practice ce li se pun.

tiut este faptul c un numr din ce n ce mai mare de persoane, lucrnd n cele mai diverse domenii, sunt puse n situaia de a avea de rezolvat probleme similare cu cele cu care este confruntat omul de tiin.

Amplificarea n avalane a informaiilor tiinifice, progresele tehnice care au loc ntr-un ritm extraordinar i oblig pe profesioniti s fie gata s acioneze noi informaii tehnico-tiinifice, noi deprinderi de munc i mai ales s gseasc soluii originale la probleme imediate. De aceea nvmntul trebuie s se orienteze n dou direcii: dezvoltarea creativitii i formarea deprinderilor, acest lucru impunnd o metodologie i o tehnic adecvat.

Trim ntr-o epoc n care eficiena unei activiti este criteriul numrul unu de apreciere, dar aceast eficien presupune economie de materie prim, de for de munc, de energie, valut etc., i aceasta, la rndul ei, presupune optimizarea activitii respective, pe care o dorim eficient.

Matematica este prima care trebuie s-i aduc aportul n aceast direcie i asta prin modernizarea sa. Modernizarea matematicii, dup prerea mea, n liceu, nseamn nu neaprat ncrcarea programei colare cu un volum mare de informaie, uneori prezentat sofisticat de manualele colare, ci cuprinderea de ctre programa colar a ct mai multor lecii de matematic aplicat. Aceste lecii i-ar aduce un mai mare aport la nelegerea multor discipline colare, mai ales a celor de specialitate i ar elucida multe din problemele de pregtire n meserie a elevilor.

Consider c teoria grafurilor poate fi neleas de majoritatea elevilor i aceasta rspunde imediat rezolvrii multor cerine ale nvmntului romnesc, deci ar fi necesar n cultura general a elevilor.Iat o problem practic, care, ca alte mii i mii de probleme din viaa de toate zilele, poate fi modelat matematic cu ajutorul teoriei grafurilor.

Ne propunem s realizm o reea de telecomunicaii ntre n localiti. ntre orice dou localiti, instalarea unei linii telefonice presupune un anumit cost. Dorim s realizm aceast reea de telecomunicaii cu un cost minim. Cum procedm?

n vederea rezolvrii acestei probleme ne vom folosi de un graf neorientat, conex, obinut n felul urmtor:

localitile care intr n reeaua de telecomunicaii reprezint vrfurile grafului grupate n mulimea X;

legturile telefonice dintre dou localiti reprezint muchiile grafului grupate n mulimea U; costul instalrii unei linii telefonice ntre dou localiti va fi funcia cost ataat grafului dup cum urmeaz: , iar reprezint costul muchiei .Costul total al grafului G este .

Graful astfel construit este un graf valorizat prin funcia cost c.

Rezolvarea problemei noastre se reduce la determinarea unui graf parial al grafului G care s aib cost minim, adic este minim.Teorem 1.Un graf parial al grafului conex , H fiind de cost minim, este un arbore parial, deoarece arborii sunt singurele grafuri conexe minimale.

ntr-adevr, dac H este un graf parial de cost minim al lui G i H conine o muchie a crei suprimare conduce la un alt graf parial de cost minim H1 conex, rezult c:

Dar inegalitatea obinut contrazice minimalitatea grafului H. Pentru gsirea unui arbore parial de cost minim, prezint urmtorul algoritm.

Algoritmul APM (arbore parial minim)

Pentru graful conex i valorizat prin funcia , 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 cnd se obine o mulime de muchii V, deci un graf parial a lui G cu , cu proprietatea c oricare dintre muchiile rmase ale lui G formeaz cicluri cu muchiile lui H. Deci H este graful fr cicluri maximal cu aceeai mulime de vrfuri ca i G. Conform teoremei demonstrate, rezult c H este arborele parial al lui G.Muchiile din V ne vor indica soluia optim de instalare a liniilor telefonice ntre cele n localiti, iar c(H) va reprezenta costul minim de realizare eficient a activitii propuse.

Fie exemplul de mai jos n care costurile muchiilor sunt date de numerele de pe muchii. Alegem mai nti 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 rmas 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] fr s formeze cicluri cu muchiile deja alese.

Am obinut muchiile [1,2], [2,3], [1,4], [1,6], [1,5] deci am obinut 5 muchii.Exist o proprietate a arborilor c un arbore cu n vrfuri are exact n-1 muchii.Deci n cazul nostru arborele format cu cele 5 muchii este arborele parial de cost minim. Acest arbore este reprezentat n figura a); mai sunt dou soluii reprezentate n figurile b) i c) obinute alegnd alte muchii de acelai cost.

a)

b)

c)

nchei aceast problem printr-un algoritm AMP care este uor programabil pe calculatorul electronic.

Se observ c se pleac de la un graf H, care are n vrfuri izolate i nici o muchie, H fiind graf parial al lui G. Ulterior, prin adugare de muchii se formeaz grafuri pariale care nu conin 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 extremitile ei aparin unor componente conexe ale grafului parial obinut pn n acel moment.

n caz contrar apare un ciclu, deoarece conform teoremei demonstrate un arbore este un graf fr cicluri maximal.

Pentru a memora numerele de ordine ale componentelor conexe n care se gsesc la un moment dat vrfurile grafului G vom folosi o list cu n poziii, astfel nct poziia i din list, notat cu s indice numrul de ordine al componentei n care se gsete vrful i al grafului.

Pentru a uura cutarea muchiei de cost minim, vom alctui lista muchiilor grafului G n ordinea cresctoare a costurilor. Algoritmul se va opri dup ce a selectat n-1 muchii, deoarece un arbore cu n vrfuri are n-1 muchii.

Algoritmul devine:

1. Pentru se face lista .

2. Se alctuiete lista muchiilor grafului G n ordine cresctoare a costurilor.

3. Fie [p,q] prima muchie din irul muchiilor lui G.

4. Au fost selectate n-1 muchii? Dac da, stop. Am obinut un arbore parial minim. Dac nu, mergem la pasul 5.

5. Se verific dac . Dac da, se consider urmtoarea muchie din irul de muchii ale lui G. Se noteaz cu p, respectiv q cele dou extremiti ale acestei muchii i se repet pasul 5. Dac se merge la pasul 6.6. Se selecteaz muchia [pq] ca o nou muchie a arborelui parial minim. Dac de exemplu , toate elementele se nlocuiesc cu valoarea i se merge la pasul 4. Se observ c dac , cele dou extremiti ale muchiei [p,q] sunt n acelai arbore, deci alegerea lui [p,q] ar crea un ciclu n graful parial, obinut la momentul respectiv. Deci trebuie considerat urmtoarea muchie din irul de muchii.La pasul 6 se unific componentele conexe crora le aparin cele dou extremiti ale muchiei [p,q] dnd tuturor vrfurilor din reuniunea celor dou componente numrul de ordine egal cu p. La sfritul aplicrii algoritmului lista L va avea toate poziiile egale cu 1.

Optimizarea tuturor problemelor, indiferent de domeniul n care se gsesc acestea, se finalizeaz cu ajutorul calculatorului electronic, motiv pentru care n perspectiv destul de apropiat colile vor fi dotate cu asemenea aparate a cror activitate va fi dirijat de profesorii de matematic.

fig.3.a

fig.3.b

fig.8d

fig.8c

EMBED Equation.3

fig.8b

fig.1

EMBED Equation.3

fig.8a

(fig.5)

graf de tip 1.

graf de tip 2.

PAGE 3

_1278263583.unknown

_1278625567.unknown

_1279383706.unknown

_1279575854.unknown

_1279834249.unknown

_1279898686.unknown

_1279926656.unknown

_1279968014.unknown

_1279968786.unknown

_1279972599.unknown

_1279972795.unknown

_1279972814.unknown

_1279972764.unknown

_1279968998.unknown

_1279970105.unknown

_1279968220.unknown

_1279968270.unknown

_1279968185.unknown

_1279928253.unknown

_1279929510.unknown

_1279961098.unknown

_1279961547.unknown

_1279962120.unknown

_1279962770.unknown

_1279962851.unknown

_1279963246.unknown

_1279963281.unknown

_1279962812.unknown

_1279962190.unknown

_1279961849.unknown

_1279961988.unknown

_1279961703.unknown

_1279961337.unknown

_1279961469.unknown

_1279961166.unknown

_1279960706.unknown

_1279960918.unknown

_1279961082.unknown

_1279960747.unknown

_1279929846.unknown

_1279960608.unknown

_1279929807.unknown

_1279928500.unknown

_1279928796.unknown

_1279929194.unknown

_1279928509.unknown

_1279928399.unknown

_1279928428.unknown

_1279928374.unknown

_1279927285.unknown

_1279927788.unknown

_1279928077.unknown

_1279928205.unknown

_1279927958.unknown

_1279927525.unknown

_1279927725.unknown

_1279927500.unknown

_1279926905.unknown

_1279927039.unknown

_1279927099.unknown

_1279927014.unknown

_1279926833.unknown

_1279926856.unknown

_1279926772.unknown

_1279901184.unknown

_1279902832.unknown

_1279905305.unknown

_1279923484.unknown

_1279926064.unknown

_1279926340.unknown

_1279926372.unknown

_1279926161.unknown

_1279923935.unknown

_1279924745.unknown

_1279925084.unknown

_1279926038.unknown

_1279924822.unknown

_1279924857.unknown

_1279924374.unknown

_1279924535.unknown

_1279924180.unknown

_1279923611.unknown

_1279923795.unknown

_1279923509.unknown

_1279905661.unknown

_1279911213.unknown

_1279911522.unknown

_1279911584.unknown

_1279911606.unknown

_1279911624.unknown

_1279911235.unknown

_1279911404.unknown

_1279909265.unknown

_1279911055.unknown

_1279905743.unknown

_1279905399.unknown

_1279905578.unknown

_1279904974.unknown

_1279905148.unknown

_1279905208.unknown

_1279905179.unknown

_1279905072.unknown

_1279905104.unknown

_1279905042.unknown

_1279903068.unknown

_1279903230.unknown

_1279903301.unknown

_1279903092.unknown

_1279903003.unknown

_1279903032.unknown

_1279902869.unknown

_1279901606.unknown

_1279902515.unknown

_1279902589.unknown

_1279902708.unknown

_1279902529.unknown

_1279902449.unknown

_1279902493.unknown

_1279901620.unknown

_1279901425.unknown

_1279901481.unknown

_1279901553.unknown

_1279901457.unknown

_1279901245.unknown

_1279901295.unknown

_1279901221.unknown

_1279899877.unknown

_1279900209.unknown

_1279900833.unknown

_1279901020.unknown

_1279901085.unknown

_1279901005.unknown

_1279900716.unknown

_1279900780.unknown

_1279900304.unknown

_1279900093.unknown

_1279900156.unknown

_1279900191.unknown

_1279900107.unknown

_1279899988.unknown

_1279900022.unknown

_1279899957.unknown

_1279899285.unknown

_1279899474.unknown

_1279899724.unknown

_1279899759.unknown

_1279899593.unknown

_1279899701.unknown

_1279899350.unknown

_1279899415.unknown

_1279899313.unknown

_1279899018.unknown

_1279899149.unknown

_1279899254.unknown

_1279899080.unknown

_1279898881.unknown

_1279898976.unknown

_1279898833.unknown

_1279836886.unknown

_1279898059.unknown

_1279898364.unknown

_1279898545.unknown

_1279898602.unknown

_1279898660.unknown

_1279898571.unknown

_1279898457.unknown

_1279898497.unknown

_1279898389.unknown

_1279898195.unknown

_1279898311.unknown

_1279898342.unknown

_1279898268.unknown

_1279898108.unknown

_1279898160.unknown

_1279898087.unknown

_1279837472.unknown

_1279897727.unknown

_1279897813.unknown

_1279897892.unknown

_1279897792.unknown

_1279897682.unknown

_1279837655.unknown

_1279897663.unknown

_1279837119.unknown

_1279837268.unknown

_1279837360.unknown

_1279837219.unknown

_1279837006.unknown

_1279837077.unknown

_1279836962.unknown

_1279835340.unknown

_1279835911.unknown

_1279836127.unknown

_1279836745.unknown

_1279836773.unknown

_1279836155.unknown

_1279835974.unknown

_1279836094.unknown

_1279835956.unknown

_1279835690.unknown

_1279835829.unknown

_1279835863.unknown

_1279835742.unknown

_1279835622.unknown

_1279835379.unknown

_1279835540.unknown

_1279834491.unknown

_1279835143.unknown

_1279835264.unknown

_1279835297.unknown

_1279835172.unknown

_1279835224.unknown

_1279835119.unknown

_1279834314.unknown

_1279834393.unknown

_1279834295.unknown

_1279731179.unknown

_1279799525.unknown

_1279800392.unknown

_1279833966.unknown

_1279834080.unknown

_1279834202.unknown

_1279833982.unknown

_1279800691.unknown

_1279833896.unknown

_1279800541.unknown

_1279799982.unknown

_1279800268.unknown

_1279800337.unknown

_1279800250.unknown

_1279799754.unknown

_1279799929.unknown

_1279799684.unknown

_1279798590.unknown

_1279799222.unknown

_1279799373.unknown

_1279799473.unknown

_1279799257.unknown

_1279799095.unknown

_1279799176.unknown

_1279798686.unknown

_1279731566.unknown

_1279798525.unknown

_1279798546.unknown

_1279798486.unknown

_1279731472.unknown

_1279731540.unknown

_1279731318.unknown

_1279577053.unknown

_1279725332.unknown

_1279726868.unknown

_1279730823.unknown

_1279730932.unknown

_1279727294.unknown

_1279725431.unknown

_1279725685.unknown

_1279725359.unknown

_1279577496.unknown

_1279725086.unknown

_1279725284.unknown

_1279577598.unknown

_1279577273.unknown

_1279577419.unknown

_1279577240.unknown

_1279576305.unknown

_1279576744.unknown

_1279576863.unknown

_1279576891.unknown

_1279576763.unknown

_1279576608.unknown

_1279576723.unknown

_1279576516.unknown

_1279576068.unknown

_1279576185.unknown

_1279576245.unknown

_1279576121.unknown

_1279575941.unknown

_1279576024.unknown

_1279575869.unknown

_1279486487.unknown

_1279574550.unknown

_1279575173.unknown

_1279575694.unknown

_1279575789.unknown

_1279575820.unknown

_1279575726.unknown

_1279575369.unknown

_1279575532.unknown

_1279575308.unknown

_1279574876.