Články

5.3: Delécia-kontrakcia a chromatický polynóm - matematika


Cvičenie 243.

V kapitole 2 sme predstavili opakovanie delécie-kontrakcie pre počítanie spanových stromov grafu. Zistite, ako súvisí chromatický polynóm grafu s tými, ktoré sú výsledkom delécie hrany e a kontrakcie tej istej hrany e. Pokúste sa nájsť rekurenciu, ako je tá na počítanie stromov, ktorá vyjadruje rozpätie a ktorá vyjadruje chromatický polynóm grafu v zmysle chromatických polynómov (G - e ) a (G / e ) pre ľubovoľnú hranu e. Pomocou tohto opakovania získate ďalší dôkaz, že počet spôsobov, ako zafarbiť graf farbami x, je polynomickou funkciou (x ). Online nápoveda.

Cvičenie 244

Pomocou opakovania delécie-kontrakcie znížite výpočet chromatického polynómu grafu na obrázku 5.1 na výpočet chromatických polynómov, ktorý môžete ľahko vypočítať. (Výpočty môžete zjednodušiť tým, že sa zamyslíte nad účinkom odstránenia okraja, ktorý je slučkou, alebo odstránenia jedného z niekoľkých okrajov medzi rovnakými dvoma vrcholmi na chromatickom polynóme.)

Obrázok 5.1: Graf.

Cvičenie

  1. Koľkými spôsobmi môžete správne zafarbiť vrcholy cesty na n vrcholoch farbami x? Popíšte závislosť chromatického polynómu dráhy od počtu vrcholov.
  2. ∗ (Nie je to nijako zvlášť náročné.) Koľko spôsobov môžete správne zafarbiť vrcholy cyklu na n vrcholoch farbami (x )? Popíšte závislosť chromatického polynómu cyklu od počtu vrcholov. Online nápoveda.

Cvičenie 246

Koľkými spôsobmi môžete správne zafarbiť vrcholy stromu na n vrcholoch farbami (x )?

Cvičenie 247

Čo pozorujete na znakoch koeficientov chromatického polynómu grafu na obrázku 5.1? Čo so znakmi koeficientov chromatického polynómu dráhy? Cyklu? Stromu? Vytvorte dohady o znakoch koeficientov chromatického polynómu a dokázajte to.