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

• Carpigabi csendes tag

  #2241

  #2240 Gyuri16

  2010-12-30 17:37:03

  Új Válasz

  Ú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

  

  Carpigabi

  csendes tag

  #2240 Gyuri16

  #2240 Gyuri16

  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.

  kösz, így már érthetőbb... de akkor a következőre h johet ki 2 :

  Portugal - Spain
  Spain - France
  France - Germany
  Germany - Czech
  Czech - Slovakia
  Slovakia - Poland
  ?

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