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

§4. Cromatismul grafurilor planare.
Primele probleme legate de cromatismul grafurilor planare au fost cele de colorare a hãrþilor geografice. Luãm pe harta e reprezintã împãrþirea administrativ-teritorialã, care este un graf planar, câte un punct situat în interiorul feþelor finite. Considerãm aceste puncte drept vârfuri într-un nou graf. Între douã vârfuri trasãm o muchie dacã ºi numai dacã feþele din graful iniþial pe care ele le reprezintã sunt adiacente. Noul graf este evident tot planar ºi se numeºte dualul celui dat. dacã vrem sã colorãm distinctiv subîmpãrþirile teritoriale ale hãrþii, feþele adiacente trebuie sã aibã culori diferite.

Problema determinãrii numãrului minim de culori necesare revine, aflãrii numãrului cromatic al grafului dual. Principalul rezultat obþinut în aceastã privinþã este dat de propoziþia:

Propoziþia 1 Orice graf planar ºi conex cu cel puþin 5 vârfuri este 5-cromatic.

Demonstraþie Pentru # X = 5, propoziþia este o tautologie.

Deci, dacã vom demonstra pentru cazul #X = n prin inducþie matematicã, atunci propoziþia va fi valabilã pentru orice # X.

Fie G un graf planar cu n vârfuri ºi x un vârf al sãu cu µ §. Suprimând acest vârf, subgraful rãmas este 5-cromatic (din presupunerea fãcutã în inducþie). Deci îi putem colora vârfurile cu culorile µ §.

Dacã µ §, pentru x poate fi disponibilã cel puþin una din aceste culori.

Dacã µ § ºi printre vârfurile adiacente cu x, µ § sunt cel puþin douã cu aceeaºi culoare, de asemenea putem folosi una din culorile neutilizate atribuind-o lui x. Rãmâne cazul µ § în ipoteza cã toþi ai sunt distincþi coloraþi.

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, cãci altfel ar exista feþe adiacente identic colorate.

Demonstrãm µ §

Graful parþial G1,2 cu muchile colorate 1 ºi 2 este planar ºi are toate vârfurile de gradul 2 (fig.2). Deci acest graf are o faþã finitã á ºi o faþã infinitã â. La fel pentru G1,3 ale cãrui feþe le etichetãm cu ã ºi ä (fig.3). Prin suprapunerea lui G1,2 cu G1,3 pe feþele lui G se obþin 4 combinaþii (fig.4) pentru care luãm µ §, µ §, µ §, µ § sau orice altã permutare a culorilor ci.

Douã feþe adiacente nu pot fi la fel colorate fãrã sã fie contrazisã ipoteza.

Demonstrãm µ §

Adoptãm un sens de rotaþie în plan notat cu +, iar sensul contrar îl notãm cu -. Punem µ § când 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 feþe pornind de la o muchie oarecare. Când trecem printr-un vârf marcat cu -1, culorile muchiilor ciclului pe care acest punct le separã se succed în sensul sãgeþii prin permutarea circularã (µ §), pe când la trecerea prin vârful x cu p(x) = +1 ele se permutã în sens invers. Deci, când ajungem din nou la muchia iniþialã, suma algebricã (x) va fi în mod necesar un multiplu de 3.

Demonstrãm µ §

Evident, cãci putem aplica de-a lungul fiecãrui contur procedeul de mai sus, trecând de la marcajul dat al vârfurilor, la colorarea arcelor. la închiderea conturului nu poate surveni o contradicþie decât dacã marcajul vârfurilor nu satisface condiþia (x).

Oricãrei etichetãri a vârfurilor care satisface condiþia (x) îi corespund trei posibilitãþi de colorare a arcelor, dupã cum afectãm arcului iniþial pe 1, 2 sau 3. Cele trei soluþii se deduc una din alta prin permutarea circularã a culorilor. Pentru grafurile planare, conexe ºi fãrã istmuri, ale cãror vârfuri au toate gradul 3, din propoziþia 2 decurg corolarele:

Corolarul 1 Când numãrul muchiilor conturului oricãrei feþe este un multiplu de 3, e posibilã colorarea feþelor cu 4 culori.

Corolarul 2 Când numãrul muchiilor conturului oricãrei feþe este un multiplu de 2, e posibilã colorarea feþelor cu 4 culori.

§5. Probleme rezolvate

Problema 1

Fie douã grafuri µ § ºi µ § având aceeaºi mulþime de vârfuri ºi B B’ matricele asociate corespunzãtor.

Sã se verifice:

matricea B+B’ corespunde grafului µ §

matricea B·B’ corespunde grafului definit astfel: de la un vârf j se duc atâtea arce câte 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 B·B’ corespunde grafului reprezentat dupã enunþul b) din problemã, figurate mai jos:

Matricele sunt:

µ § µ §
Matricea B+B’ este tocmai matricea ataºatã grafului din figura a), iar matricea B·B’ este tocmai matricea ataºatã grafului din figura b).

µ § µ §

Problema 1’ Fie o mulþime µ §. În mulþimea X se defineºte o aplicaþie à prin urmãtoarea corespondenþã:

µ §

Se cere sã se reprezinte graful µ §

Rezolvare: Considerãm cã elementele mulþimii X sunt vârfurile grafului, aplicaþia definitã în enunþul exerciþiului defineºte 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 definiþie închiderea tranzitivã a grafului µ § este tot un graf µ §, obþinut din graful dat, unde à este o aplicaþie a lui X în X, care asociazã fiecãrui vârf x o submulþime a lui X formatã din x ºi din toate vârfurile 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 funcþiei Grundy pentru graful µ § reprezentat mai jos.

Rezolvare:

Prin definiþie o funcþie g definitã pe mulþimea X este o funcþie Grundy, dacã orice valoare a sa este un întreg pozitiv sau zero ºi g(x) este cel mai mic întreg pozitiv care nu aparþine mulþimii µ §.

Altfel spus, funcþia g definitã pe mulþimea X este o funcþie Grundy dacã:

(1) µ § µ § cu µ §

(2) µ §

Pentru determinarea valorilor funcþiei g folosim urmãtorul algoritm:

Presupunem submulþimea µ § din definiþia funcþiei Grundy pentru orice µ § g(x) = 0;

Pentru orice x din µ § luãm g(x)=1;

Procedãm din aproape în aproape, determinãm submulþimea µ § ºi pentru orice x din Xi, vom lua µ § ºi µ §. Pentru un graf dat, funcþia 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) µ §

cãci µ § ºi µ §,

deci µ §

e) µ § cãci µ §,

deci µ §

Deci valorile funcþiei Grundy pentru graful dat sunt:

µ §
ºi aceste valori determinã o partiþie a mulþimii X în submulþimile:

µ § pentru care µ §

µ § pentru care µ §

µ § pentru care µ §

care sunt clase de echivalenþã determinate de relaþia µ §

III. POLIEDRE CONVEXE