În acest referat, vom da o aplicatie a multimilor partial ordonate la probleme de
numãrare. Tipul problemei pe care o vom considera, implicã o sumare dupã o multime partial
ordonatã, a cãrei inversiune dã formula de numãrare. Urmãtoarea problemã este din aceastã
categorie.
Problema 1: Problema colorãrii hãrtilor.
O hartã este definitã ca un plan divizat într-un numãr finit de regiuni nesuprapuse, numite
tãri, conectate printr-un numãr finit de arce care se intersecteazã dar nu la capete (deci intersectia
a douã arce este fie zero, fie un singur punct).
Putem scrie : =((T1, ,Tn),(a1, ,am),(m,n)), unde T : n › P (R2), T(j)= Tjtara,
.j. n
A : m › A , i m , A(i) = a i arc.
Douã tãri Tj si Tk sunt adiacente dacã au o frontierã comunã care este unul dintre arce,
adicã dacã (.a A) Tj Tk ={a}.
Fie C={c1, , ck} o multime de culori.
Definitie. O functie c : {T1, ,Tn} › C se numeste functie de colorare dacã este definitã
prin conditia urmãtoare:
C(Tj)= ci dacã Tj este coloratã cu culoarea ci.
Definitie. O functie de colorare c : {T1, ,Tn} › C se numeste colorare proprie dacã este
îndeplinitã conditia urmãtoare:
(Ti,Tj) adiacente =>c(Ti).c(Tj).
(adicã orice douã tãri am considera, ele sunt colorate cu aceeasi culoare).
Problemele care se pun sunt : (Numãrul colorãrii proprii ale unei harti)
Se dau : a) o hartã;
b) k culori.
Se cere : sã se determine numãrul de functii de colorare proprie.
(De Morgan 1850) (problema celor 4 culori). Sã se stabileascã dacã numãrul colorãrii ale
oricãrei hãrti cu 4 culori este strict pozitiv.
Reformulare. Sã se stabileascã adevãrul sau falsul urmãtorului enunt:
„Pentru orice hartã, existã cel putin o colorare proprie cu k = 4 culori ”.
Rãspunsul la problema (2) este afirmativ: pentru orice hartã, numãrul colorãrilor proprii
cu k=4 culori este pozitiv. Problema a fost rezolvatã în 1985 utilizând 1200 ore de calculator.
Scopul urmãrit în continuare: Se cere ca pentru orice hartã H existã un polinom cu
coeficienti intregi P Z[X] astfel încât PH (4) reprezintã numãrul colorãrii ale lui H de ordin k
(adicã cu k culori).
PH(k) se numeste polinomul cromatic asociat hãrtii H. Prin polinomul cromatic asociat
hãrtii H este furnizatã o solutie la problema (1).
În limbajul polinomului cromatic, problema celor 4 culori are urmatorul enunt.
Sã se stabileascã calitatea logicã a urmãtoarei propozitii:
„Pentru orice hartã H, PH(4)>0, unde PH(4) este polinomul cromaticasociat hãrtii H”.
Cu alte cuvinte, sã se stabileascã care dintre urmãtoarele enunturi este adevãrat:
(1) (.H hartã ) PH(4)>0.
(2) (.H hartã) PH(4)=0.
Dupã cum am precizat anterior, enuntul (1) este adevãrat.
Definim o subhartã a hãrtii ca fiind harta obtinutã din stergând anumite arce.
Multimea subhãrtilor lui o notãm cu s(.).
Definim pe s(.) o relatie de ordine „.” astfel:
(.(E,.). s2(.)) E E este o subhartã a lui
( s(.)) f(.)= numãrul colorãrii proprii ale lui cu k culori.
g(.)=numãrul total de colorãri.
Notãm cu c(.)numãrul de tãri din
Atunci :g(.)=kc(.)(numãrul aplicatiilor de la multimea tãrilor la multimea culorilor).
Pentru orice colorare E a lui , existã o unicã subhartã E a lui si o colorare proprie c* a
lui E astfel încât este o extensie a lui c*.
UNIVERSITATEA VASILE ALECSANDRI DIN BACÃU
FACULTATEA DE STIINTE
SPECIALIZAREA MATEMATICÃ
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.