# Chromatinis skaičius II [![PDF](../slides_common/img/pdf.png)](./slides.pdf) Parengė Vytautas Strimaitis, PS 4 k.
## Kartojimas * Grafo $G$ chromatinis skaičius - mažiausias skaičius spalvų, kuriomis grafo viršūnes galima nudažyti taip, kad bet kokios dvi gretimos viršūnės būtų nudažytos skirtinga spalva. * Šis skaičius žymimas $\gamma(G)$. * Paskutinį kartą buvo aptartas euristinis algoritmas "pirma spalva, po to viršūnė" chromatiniam skaičiui rasti.

Euristinis algoritmas "pirma viršūnė, o po to spalva"

  • Viršūnės $h$ laipsnis - tai skaičius spalvų, kuriomis šios viršūnės negalima dažyti, t.y. šiai viršūnei negalimų spalvų skaičius.
  • Viršūnės $k$ laipsnis - tai šiai viršūnei gretimų nenudažytų viršūnių skaičius.
| |h|k| |-----|-|-| |**1**|1|2| |**2**|1|1| |**3**|1|1| |**4**|2|1|

Euristinis algoritmas "pirma viršūnė, o po to spalva"

  • Apibrėžkima viršūnių palyginimą. Viršūnę $u$ laikysime einančia anksčiau už viršūnę $v$, jei:
    • $h(u) > h(v)$
    • $h(u) = h(v), k(u) > k(v)$
    • $h(u) = h(v), k(u) = k(v), u < v$
  • Algoritmas:
    • $p := 0$
    • Kol yra nenudažytų viršūnių:
      1. Pagal apibrėžtą palyginimo operaciją parenkame pirmąją nenudažytą viršūnę $v$;
      2. Jei galima, dažome viršūnę viena iš anksčiau panaudotų spalvų, t.y. viena iš galimų aibės $\{1, 2, \dots, p\}$ spalvų;
      3. Jei nudažyti negalima, tai $p := p+1$ ir dažome $p$-ąja spalva;
      4. Visoms nenudažytoms viršūnėms atnaujiname $h$ ir $k$ laipsnius.

Pavyzdys

| |h|k|spalva| |-----|-|-|-| |**1**|0|3|| |**2**|0|4|| |**3**|0|3|| |**4**|0|2|| |**5**|0|4|| |**6**|0|3|| |**7**|0|3|| |**8**|0|2||

Pavyzdys

| |h|k|spalva| |-----|-|-|-| |**1**|0|3|| |**2**|0|4|R| |**3**|0|3|| |**4**|1|1|| |**5**|1|3|| |**6**|0|3|| |**7**|1|2|| |**8**|1|1||

Pavyzdys

| |h|k|spalva| |-----|-|-|-| |**1**|1|2|| |**2**|0|4|R| |**3**|1|2|| |**4**|1|1|| |**5**|1|3|M| |**6**|0|3|| |**7**|2|1|| |**8**|1|1||

Pavyzdys

| |h|k|spalva| |-----|-|-|-| |**1**|1|2|| |**2**|0|4|R| |**3**|2|1|| |**4**|1|1|| |**5**|1|3|M| |**6**|0|3|| |**7**|2|1|Ž| |**8**|1|1||

Pavyzdys

| |h|k|spalva| |-----|-|-|-| |**1**|2|1|| |**2**|0|4|R| |**3**|2|1|R| |**4**|1|1|| |**5**|1|3|M| |**6**|0|3|| |**7**|2|1|Ž| |**8**|1|1||

Pavyzdys

| |h|k|spalva| |-----|-|-|-| |**1**|2|1|Ž| |**2**|0|4|R| |**3**|2|1|R| |**4**|1|1|| |**5**|1|3|M| |**6**|1|2|| |**7**|2|1|Ž| |**8**|1|1||

Pavyzdys

| |h|k|spalva| |-----|-|-|-| |**1**|2|1|Ž| |**2**|0|4|R| |**3**|2|1|R| |**4**|1|0|| |**5**|1|3|M| |**6**|1|2|R| |**7**|2|1|Ž| |**8**|1|0||

Pavyzdys

| |h|k|spalva| |-----|-|-|-| |**1**|2|1|Ž| |**2**|0|4|R| |**3**|2|1|R| |**4**|1|0|M| |**5**|1|3|M| |**6**|1|2|R| |**7**|2|1|Ž| |**8**|1|0||

Pavyzdys

| |h|k|spalva| |-----|-|-|-| |**1**|2|1|Ž| |**2**|0|4|R| |**3**|2|1|R| |**4**|1|0|M| |**5**|1|3|M| |**6**|1|2|R| |**7**|2|1|Ž| |**8**|1|0|M|

Pratimas

Pritaikę euristinį algoritmą "pirma viršūnė, o po to spalva", nuspalvinkite duotą grafą.

Atsakymas

## Briaunų dažymo uždavinys * Mažiausias skaičius spalvų, kuriomis grafo briaunas galima nudažyti taip, kad bet kurios dvi gretimos briaunos būtų nudažytos skirtinga spalva, vadinamas grafo chromatine klase. * Uždavinys analogiškas viršūnių dažymo uždaviniui, nes galima: * pasiversti grafą į jo briauninį grafą; * spręsti viršūnių dažymo uždavinį gautame grafe.
## Pritaikymo pavyzdžiai * **Paskaitų tvarkaraščio sudarymo uždavinys:** * Turime kažkiek paskaitų, kai kurias paskaitas skaito tas pats lektorius. * Visų paskaitų trukmė vienoda. * Norime sudaryti tvarkaraštį tokį, kad visas paskaitas būtų galima perskaityti per kuo trumpesnį laiką. * Sprendimas - sudaryti grafą, kurio viršūnės yra paskaitos, o dvi viršūnes jungia briauna, jei abi paskaitas skaito tas pats lektorius. * Tokio grafo chromatinis skaičius yra lygus minimaliam valandų skaičiui, kuris reikalingas perskaityti visas paskaitas. * **Darbų paskirstymo uždavinys:** * Turime kažkiek darbų ir mechanizmų, darbams atlikti naudojami mechanizmai. * Visų darbų trukmės lygios. * Mechanizmus reikia paskirstyti taip, kad bendras visų darbų atlikimo laikas būtų minimalus. * Sprendimas - sudaryti grafą, kurio viršūnės yra darbai, o dvi viršūnes jungia briauna, jei atitinkamiems darbams atlikti reikia to paties mechanizmo. * Nudažius tokį grafą, ta pačia spalva nudažyti darbai gali būti vykdomi vienu metu.

Chromatinio skaičiaus įverčiai

  • Tegu $\delta(G) = \min\limits_{v \in V}d(v), \Delta(G) = \max\limits_{v \in V}d(v).$
  • Jungiajam grafui $G$ galima nurodyti tokius chromatinio skaičiaus įverčius:
    1. $\gamma(G) \leq 1 + \Delta(G)$
    2. Brukso teorema. Jei $G$ - jungusis ir nepilnasis grafas, kuriam $\Delta(G) \geq 3$, tai $\gamma(G) \leq \Delta(G)$
    3. $\gamma(G) \leq \max\limits_{1 \leq i \leq n}\min(d(i)+1, i)$
    4. $\gamma(G) \geq \frac{n}{n-\frac{1}{2m}\sum\limits_{i=1}^{n}d^2(i)}$
  • Hadvigerio hipotezė. Bet koks jungusis $n$-chromatinis grafas gali būti sutrauktas į $K_n$ grafą. Ši hipotezė įrodyta, kai $n \leq 5$