- Hívószám-hamisítás
- Samsung Galaxy Watch7 - kötelező kör
- Youtube Android alkalmazás alternatívák reklámszűréssel / videók letöltése
- Mi nincs, grafén akku van: itt a Xiaomi 11T és 11T Pro
- Nokia 8 Sirocco - tudja, honnan fúj a szél
- Samsung Galaxy A53 5G - kevesebbet többért
- Akciófigyelő: Jelentősen olcsóbban nyit az Ulefone új mindenese
- VoLTE/VoWiFi
- Samsung Galaxy S23 Ultra - non plus ultra
- Xiaomi Mi 11 Ultra - Circus Maximus
Ú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!
- Intel Core Ultra 7 265 /// Bontatlan, Teljesen Új // Üzletből, Számlával és Garanciával
- Csere-Beszámítás! Ryzen 9 9950X Processzor!
- Újszerű Gamer Asztali PC Számítógép 2026-ig Garis ASUS H510M-K R2.0 i5 11400F RTX 4060 8GB Dobozába
- Samsung Galaxy Tab A8 (2021) , 3/32 GB,
- Samsung Galaxy S6 Lite (2022) , 4/64 GB ,Wi-fi
- TAVASZI BOMBA AKCIÓK! STEAM, UBISOFT CONNECT, EA APP, XBOX EREDETI KULCSOK 100% GARANCIA
- Apple iPhone 12 64GB, Kártyafüggetlen, 1 Év Garanciával
- ÁRGARANCIA!Épített KomPhone Ryzen 7 5700X3D 32/64GB RAM RX 7800 XT 16GB GAMER PC termékbeszámítással
- Lenovo ThinkPad X13 G2 multitouch
- Csere-Beszámítás! RTX Számítógép PC Játékra! R5 8400F / RTX 3070Ti / 32GB DDR5 / 1TB SSD
Állásajánlatok
Cég: PC Trade Systems Kft.
Város: Szeged
Cég: PC Trade Systems Kft.
Város: Szeged