Funcția Mobius - inversiunea lui Mobius

Extras din referat Cum descarc?

In acest referat, vom da o aplicatie a multimilor partial ordonate la probleme de
numarare. Tipul problemei pe care o vom considera, implica o sumare dupa o multime partial
ordonata, a carei inversiune da formula de numarare. Urmatoarea problema este din aceasta
categorie.
Problema 1: Problema colorarii hartilor.
O harta este definita ca un plan divizat intr-un numar finit de regiuni nesuprapuse, numite
tari, conectate printr-un numar finit de arce care se intersecteaza dar nu la capete (deci intersectia
a doua 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.
Doua tari Tj si Tk sunt adiacente daca au o frontiera comuna care este unul dintre arce,
adica daca (.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 daca este definita
prin conditia urmatoare:
C(Tj)= ci daca Tj este colorata cu culoarea ci.
Definitie. O functie de colorare c : {T1, ,Tn} > C se numeste colorare proprie daca este
indeplinita conditia urmatoare:
(Ti,Tj) adiacente =>c(Ti).c(Tj).
(adica orice doua tari am considera, ele sunt colorate cu aceeasi culoare).
Problemele care se pun sunt : (Numarul colorarii proprii ale unei harti)
Se dau : a) o harta;
b) k culori.
Se cere : sa se determine numarul de functii de colorare proprie.
(De Morgan 1850) (problema celor 4 culori). Sa se stabileasca daca numarul colorarii ale
oricarei harti cu 4 culori este strict pozitiv.
Reformulare. Sa se stabileasca adevarul sau falsul urmatorului enunt:
,,Pentru orice harta, exista cel putin o colorare proprie cu k = 4 culori ".
Raspunsul la problema (2) este afirmativ: pentru orice harta, numarul colorarilor proprii
cu k=4 culori este pozitiv. Problema a fost rezolvata in 1985 utilizand 1200 ore de calculator.
Scopul urmarit in continuare: Se cere ca pentru orice harta H exista un polinom cu
coeficienti intregi P Z[X] astfel incat PH (4) reprezinta numarul colorarii ale lui H de ordin k
(adica cu k culori).
PH(k) se numeste polinomul cromatic asociat hartii H. Prin polinomul cromatic asociat
hartii H este furnizata o solutie la problema (1).
In limbajul polinomului cromatic, problema celor 4 culori are urmatorul enunt.
Sa se stabileasca calitatea logica a urmatoarei propozitii:
,,Pentru orice harta H, PH(4)>0, unde PH(4) este polinomul cromaticasociat hartii H".
Cu alte cuvinte, sa se stabileasca care dintre urmatoarele enunturi este adevarat:
(1) (.H harta ) PH(4)>0.
(2) (.H harta) PH(4)=0.
Dupa cum am precizat anterior, enuntul (1) este adevarat.
Definim o subharta a hartii ca fiind harta obtinuta din stergand anumite arce.
Multimea subhartilor lui o notam cu s(.).
Definim pe s(.) o relatie de ordine ,,." astfel:
(.(E,.). s2(.)) E E este o subharta a lui 
( s(.)) f(.)= numarul colorarii proprii ale lui cu k culori.
g(.)=numarul total de colorari.
Notam cu c(.)numarul de tari din 
Atunci :g(.)=kc(.)(numarul aplicatiilor de la multimea tarilor la multimea culorilor).
Pentru orice colorare E a lui , exista o unica subharta E a lui si o colorare proprie c* a
lui E astfel incat este o extensie a lui c*.

Fisiere in arhiva (1):

 Functia Mobius - Inversiunea lui Mobius.pdf