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

• #2242 Gyuri16 senior tag Carpigabi #2241

  Új Válasz 2010-12-30 17:43:49 #2242

  Ú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 #2241 üzenetére

  ha rendezed, akkor egy osszefuggo grafot kapsz (zarojelben a szinek), innen egyertelmu:

  Portugal(1) - Spain(2) - France(1) - Germany(2) - Czech(1) - Slovakia(2) - Poland(1)

• #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.

  [ Szerkesztve ]

• #2238 Gyuri16 senior tag Carpigabi #2237

  Új Válasz 2010-12-30 14:01:50 #2238

  Ú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 #2237 üzenetére

  iskolai feladatot itt helyetted senki nem fogja megcsinalni, viszont segitunk ha elakadsz, es konkret kerdesed van.

  a feladathoz:
  szetosztod a grafot osszefuggo komponensekre
  mindegyiknek kiszamolod a kromatikus szamat es a legnagyobb lesz a megoldas.

  kromatikus szam egy osszefuggo grafhoz:
  binaris keresessel. egy lepesben kibprobalod eleg e m szin (m legyen mondjuk n/2 az elejen, mivel tudjuk, hogy a kromatikus szam maximum n). ezt bruteforce csinalod.
  innen a siker fuggvenyeben mindig kizarod a fel intervallumot, es megtalalod a legkisebb erteket amire meg atmegy a szinezes

• #2236 Gyuri16 senior tag Carpigabi #2235

  Új Válasz 2010-12-30 13:36:22 #2236

  Ú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 #2235 üzenetére

  ez altalanosan egy NP-teljes problema. en nem ismerek semmilyen ertelmes algoritmust, es ugy tudom nincs is ilyen, szoval marad kiprobalni az osszes lehetoseget. kesz programom nincs, de megirni nem nagy feladat.. persze lassu lesz, de jobb nincs.

  google talal egy par approximalo algoritmust, esetleg azokat is ki lehet probalni, attol fugg mire kell.

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