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

§1. Poligoane convexe
Se numeºte mulþime convexã o mulþime M de puncte care se bucurã de proprietatea: dacã µ § atunci µ §

Observaþii:

Figura 1a reprezintã o mulþime convexã, iar figura 1b reprezintã o mulþime neconvexã.

Mulþimea vidã ºi mulþimea formatã dintr-un singur punct sunt mulþimi convexe.

Mulþimea formatã din douã puncte distincte nu este convexã.
Teoremã 1

Orice intersecþie de mulþimi convexe este convexã.

Fie M1, M2 ... Mn ... mulþimi convexe. Notãm cu µ § ºi fie µ § µ § µ §este mulþime convexã.

Interiorul unghiului propriu µ § este mulþimea de puncte µ § unde µ § ºi µ § (fig.2).

Proprietãþi

Planul ºi orice dreaptã sunt mulþimi convexe;

Orice segment ºi orice semidreaptã sunt mulþimi convexe;

Semiplanele deschise ºi semiplanele închise sunt mulþimi convexe;

Înteriorul unui unghi µ § este o mulþime convexã, fiind intersecþia a douã semiplane deschise care sunt convexe;

Dacã interiorul unui triunghi ABC se defineºte astfel µ § unde µ §, µ §, µ § atunci µ § este o mulþime convexã.

O linie poligonalã este o mulþime de forma:

µ §, unde punctele µ § se numesc vârfurile 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 numeºte poligon. Figura 3b nu este poligon pentru cã un poligon nu se autointersecteazã. Denumirea poligonului se dã în funcþie de numãrul de laturi pe care le are.

Segmentele PiPK care nu sunt laturi se numesc diagonale. Poligonul cu vârfurile P1,P2,P3, ... Pn va fi notat cu P1P2...Pn. Poligonul P1P2...Pn se numeºte convex, dacã pentru fiecare laturã µ §, toate vârfurile diferite de Pk ºi PK+1 se gãsesc de aceeaºi parte a dreptei PkPK+1, pentru µ § ºi µ § (fig.3c).

Interiorul unui poligon convex este intersecþia semiplanelor deschise limitate de suporturile laturilor poligonului ºi care conþine vârfurile nesituate pe laturile respective (fig.4a).

Dacã notãm µ § pentru µ § ºi µ § atunci µ §.

Reuniunea dintre poligonul convex P1P2...Pn ºi µ § se numeºte suprafaþã poligonalã convexã.

Se numeºte suprafaþã poligonalã o mulþime de puncte din plan care este reuniunea unui numãr finit de suprafeþe poligonale convexe, acestea având douã câte douã interioare disjuncte. (fig.4b)

Dacã S este o suprafaþã poligonalã ºi [L1] [L2] ¡K [LK] sunt suprafeþele poligonale convexe respective, adicã µ § ºi µ § pentru µ §, atunci vom spune cã mulþimea µ § constituie o descompunere a suprafeþei poligonale S (fig.4c).

Pentru suprafaþa poligonalã convexã µ § poligonul µ § se numeºte frontierã.

Un punct P al unei suprafeþe poligonale S se numeºte 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 definiþie rezultã cã orice suprafaþã poligonalã se descompune în suprafeþe poligonale convexe.

Teoremã

O suprafaþã poligonalã convexã cu n-laturi (µ §) se descompune în n-2 suprafeþe triunghiulare.

Demonstraþie

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 P4P5¡KPn sunt de aceeaºi parte a lui P1P3, deci P1P3 P4¡KPn 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, P5¡KPn se aflã în semiplane opuse faþã de P1P3, adicã interiorul triunghiului P1P2P3 ºi interiorul poligonului P1P3 P4¡KPn se aflã în semiplane opuse, având intersecþia vidã ºi µ §.

Dacã aplicãm succesiv rezultatul obþinut mai sus pentru suprafeþele poligonale µ §, µ § etc, care au fiecare cu o laturã mai puþin decât precedenta ºi astfel obþinem rezultatul cerut de teoremã, figura 5.

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