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

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

Cu metodele teoriei grafurilor se rezolvã un mare numãr de probleme din teoria circuitelor electrice, teoria reþelelor de transport, teoria informaþiilor, ciberneticã, teoria mulþimilor sau alte discipline abstracte. De remarcat este faptul cã discipline foarte variate ajung sã utilizeze teoreme analoage; ºtim cã noþiunea de „matrice de incidenþã” introdusã de Kirchhof pentru studiul circuitelor electrice a fost reluatã de cãtre Henri Poincoré în topologie, noþiunea de „punct de articulaþie” folositã în sociologie, de multã vreme, acum se foloseºte în electronicã.

Pentru a putea fi aplicatã în domenii atât de variate, teoria grafurilor trebuie sã fie în mod esenþial abstractã ºi formalizatã.

Teoria grafurilor fiind una dintre cele mai solicitate teorii în rezolvarea problemelor din economie ºi viaþa socialã, m-a determinat sã aleg aceastã lucrare: „GRAFURI PLANARE, POLIEDRE CONVEXE ªI APLICAÞII”, gândindu-mã cã, cu o parte din elevi, prin cercurile de matematicã, se pot dezbate marea majoritate a problemelor din lucrarea de faþã, lãrgindu-le astfel sfera de cunoºtinþe privitoare la matematicile aplicate.

Primul capitol „Elemente de teoria grafurilor”, la început, prezintã aplicaþii univoce, aplicaþii multivoce, precum ºi închiderea tranzitivã a unei aplicaþii multivoce. Toate acestea sunt noþiuni de teoria mulþimilor necesare în definirea noþiunilor de graf, multigraf, graf parþial, subgraf, drum circuit, lanþ ciclu.

În continuare sunt lãmurite noþiunile 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ã noþiunile de graf planar, graf planar de tip 1 ºi graf planar de tip 2, teorema lui Euler ºi teorema lui Kuratovski.

Pentru lãmurirea problemelor legate de cromatismul grafurilor planare am definit funcþiile lui Grundy. Modul în care se pot colora grafurile este dat de teorema lui Hevood ºi corolarele obþinute din aceasta. Mare parte din aceste noþiuni 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 parþial minim”, „problema determinãrii fluxului maxim într-o reþea 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 noþiunilor 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 pregãtirile pentru olimpiade.

Am pornit de la noþiunea de mulþime convexã definitã în clasa a IX-a ºi am lãmurit noþiunile de poligoane convexe ºi suprafaþã poligonalã convexã. Apoi am prezentat mulþimile poliedrale cu proprietãþile lor, reþeaua poligonalã simplã, teorema lui Euler ºi teorema privitoare la numãrul 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 mulþimi convexe.

Legãtura 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 noþiunea de „liniar independenþã”.

ELEMENTE DE TEORIA GRAFURILOR