- Samsung Galaxy A56 - megbízható középszerűség
- Milyen okostelefont vegyek?
- Kicsomagolták a Vivo X Fold 5-öt (videó és fotók)
- Szerkesztett és makrofotók mobillal
- iPhone topik
- Honor 200 Pro - mobilportré
- Huawei Mate X6 - keleti oldal, nyugati oldal
- Android alkalmazások - szoftver kibeszélő topik
- VoLTE/VoWiFi
- Samsung Galaxy A54 - türelemjáték
Ú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.
-
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 -
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
Hirdetés
● olvasd el a téma összefoglalót!
● ha kódot szúrsz be, használd a PROGRAMKÓD formázási funkciót!
- AKCIÓ! "ÚJ" Microsoft Surface 5 13,5 notebook - i5 1235U 8GB RAM 256GB SSD Intel Iris Xe IGP 27% áfa
- Beszámítás! Apple Watch SE 2024 44mm Cellular okosóra garanciával hibátlan működéssel
- Magyarország piacvezető szoftver webáruháza
- ÁRGARANCIA!Épített KomPhone i5 14600KF 32/64GB RAM RX 7800 XT 16GB GAMER PC termékbeszámítással
- 0% THM részletfizetés, beszámítás! Gamer PC, notebook, konzol, Apple termék, hardver KAMATMENTESEN!
Állásajánlatok
Cég: Promenade Publishing House Kft.
Város: Budapest
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest