Új hozzászólás Aktív témák

• #2240 Gyuri16 senior tag Carpigabi #2239

  Új Válasz 2010-12-30 16:07:53 #2240

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Gyuri16

  senior tag

  válasz Carpigabi #2239 üzenetére

  ez a pelda:
  Britain - Ireland
  France - Germany
  France - Swiss
  Swiss - Germany

  ha grafnak megrajzolod ket osszefuggo komponense lesz:
  1 Britain - Ireland

  2 Swiss - France - Germany
  | |
  ------------------

  az elso komponens kromatikus szama 2 a masodiknak 3, ebbol a nagyobb a 3 igy az egesz grafnak is ez lesz a kr. szama.

  ez az egesz csak egyszerusites. mivel a fo algoritmus bonyolultsaga exponencialis, ezert jobb, ha minel kisebb grafokon futtatod.

  ezen kivul lehet optimalizalni az ismert eseteket is. vannak olyan graf osztalyok amiknek ismert a kromatikus szama. pl:
  teljes graf - csucsok szama
  csillag graf - 2
  korgraf - 2 ha paros szamu csucsa van, 3 ha paratlan

  tovabba azok a grafok amiknek 2 a kromatikus szamuk szinten konnyen felismerhetok, mert ezek pontosan a paros grafok (ha tobb mint 1 csucsuk van..)

  ha akarsz kicsit gyorsitani az algoritmuson akar ezeket is be lehet vetni, mivel a fenti osztalyokat polinomialis idoben fel lehet ismerni.

Új hozzászólás Aktív témák