curs 7: colorare

Curs 7: ColorareTeoria grafurilor

Radu Dumbraveanu

Universitatea de Stat “A. Russo” din Balt, iFacultatea de S, tiint,e Reale

Aceasta prezentare este pusa la dispozitie sub Licenta Atribuire -Distribuire-ın-conditii-identice 3.0 Ne-adaptata (CC BY-SA 3.0)

Balt, i, 2013

R. Dumbraveanu (USARB) Curs 7: Colorare Balt,i, 2013 1 / 1

Colorare

Definit, ieFie G = (V ,E) un graf. O k-colorare a lui V , unde k ∈ N, poate fidefinita ca o funct, ie c : V → {1, 2, ..., k}.

Colorarea se numes, te proprie daca ∀u, v ∈ V , u s, i v vecine, c(u) 6= c(v).

Graful care cont, ine bucle nu poate avea colorari proprii.

In cele ce urmeaza ın loc de termenul ”colorare proprie” vom folosi simplutermenul ”colorare”.

../../resources/diapozitive11/g90.png3-colorare

http://www.personal.kent.edu/ rmuhamma/GraphTheory/MyGraphTheory/coloring.htm

Numarul cromatic

Numarul minim de culori necesare unei colorari proprii a unui graf G s.n.numarul cromatic al grafului s, i se noteaza cu χ(G).

Numarul cromatic. Marginea de sus

TeoremaFie G un garf simplu atunci χ(G) ≤ ∆(G) + 1

Teorema (Brook)Fie G un graf simplu conex. Daca G nu este un graf complet s, i nu estegraful ciclu, atunci χ(G) ≤ ∆(G).

Numarul cromatic. Marginea de sus

TeoremaFie G un garf simplu atunci χ(G) ≤ ∆(G) + 1

Teorema (Brook)Fie G un graf simplu conex. Daca G nu este un graf complet s, i nu estegraful ciclu, atunci χ(G) ≤ ∆(G).

Numararea colorarilor

Fie G = (V ,E) un graf. Notam prin P(G, k) sau πk(G) numarul decolorari posibile cu k culori.

Numararea colorarilor la En

E1P(G, k) = k

E2 P(G, k) = k · k

E3P(G, k) = k · k · k

... EnP(G, k) = k · k · ... · k︸︷︷︸

Numararea colorarilor la Kn

K1P(G, k) = k

K2P(G, k) = k(k − 1)

K3P(G, k) = k(k − 1)(k − 2)

... KnP(G, k) = k(k − 1)(k − 2)...(k − (n − 1))︸︷︷︸

Polinomul cromatic I

TeoremaP(G, k) este un polinom. Mai mult, daca graful G este simplu atunci

P(G, k) = P(G − e, k)− P(G/e, k).

Demonstrat, ie IDemonstram prin induct, ie pe n = ||G||. Pentru n = 0 avem graful nulpentru care P(En , k) = kn (polinom). Deci teorem este verificata.

Demonstrat, ie IIPresupunem ca teorema are loc pentru orice graf cu numarul de muchiimai mic decıt n. Fie G un graf cu n muchii, n ≥ 1. In G alegem o muchies, i notam capetele acesteia prin u s, i v. Daca eliminam muchia e obt, inemdoua grafuri noi: G − e s, i G/e.

Demonstrat, ie IIIAcum, pentru G − e avem mai multe posibilitat, i de colorare decıt pentruG: orice colorare a lui G − e ın care u s, i v au culori diferite este s, i ocolorare a lui G, iar colorarile ın care u s, i v au aceeas, i culoare nu pot ficonsiderate colorari ale lui G.

Demonstrat, ie IV

Pe de alta parte aceste colorari sınt colorari pentru G/e ıntrucıt ın el u s, iv au fost combinate ıntr-un singur vırf. Deci

P(G, k) = P(G − e, k)− P(G/e, k).

Notat, ia P(G, k) se numes, te polinom cromatic, iar demonstrat, ia teoremeipoate fi utilizata drept algoritm de determinare a polinomului cormatic.

Proprietat, i ale polinomului cromatic

1. P(G, k) = kn − a1kn−1 + a2kn−2 − ... unde ai ≥ 0 s, i n este numarulde vırfuri ale grafului.

2. P(G, k) = kn −mkn−1 + ... unde m este numarul de muchii agrafului G

3. P(G, k) este divizibil prin k4. Semnele coeficient, ilor alterneaza5. Cel mai mic i pentru care a1 6= 0 reprezinta numarul de componente

a grafului6. Daca G = G1 ∪G2 de grafuri disjuncte, atunci

P(G, k) = P(G1, k)P(G2, k)

curs 7: colorare

Documents