Funcția Mobius - inversiunea lui Mobius

Î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*.