Új hozzászólás Aktív témák
-
Gyuri16
senior tag
válasz Carpigabi #2239 üzenetére
ez a pelda:
Britain - Ireland
France - Germany
France - Swiss
Swiss - Germanyha grafnak megrajzolod ket osszefuggo komponense lesz:
1 Britain - Ireland2 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 paratlantovabba 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 ]
Nem vagyok egoista, csak uborkagyalu!
Új hozzászólás Aktív témák
● olvasd el a téma összefoglalót!
● ha kódot szúrsz be, használd a PROGRAMKÓD formázási funkciót!
- Lenovo P52 P3200MAX-Q 6GB Nvidia kártya, i7 8850H (6C12T), 1TB+250 NVME SSD eladó!
- Üzletből, garanciával, Acer Concept Workstation i7-9750H/32RAM/512SSD/RTX3000/4K LCD/magyar bill.
- Keep Out FX800B //800W//
- Natec Genesis Titan 800
- Tyű-ha Lenovo Thinkpad X1 Carbon Profi Érintős Laptop 14" -50% i7-10610U 4Mag 16GB/512GB FHD IPS
Állásajánlatok
Cég: Ozeki Kft.
Város: Debrecen
Cég: Alpha Laptopszerviz Kft.
Város: Pécs