- Motorola Edge 50 Neo - az egyensúly gyengesége
- Hívószám-hamisítás
- Magisk
- One mobilszolgáltatások
- iPhone topik
- Íme az új Android Auto!
- Samsung Galaxy S24 Ultra - ha működik, ne változtass!
- Szívós, szép és kitartó az új OnePlus óra
- Samsung Galaxy Fit 3 - keveset, de jól
- Honor Magic6 Pro - kör közepén számok
Ú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!
- sziku69: Fűzzük össze a szavakat :)
- Rágyúr a macOS-re a 3DMark
- sziku69: Szólánc.
- Luck Dragon: Asszociációs játék. :)
- Vicces képek
- Milyen processzort vegyek?
- Milyen asztali (teljes vagy fél-) gépet vegyek?
- AMD K6-III, és minden ami RETRO - Oldschool tuning
- Milyen billentyűzetet vegyek?
- Motorola Edge 50 Neo - az egyensúly gyengesége
- További aktív témák...
- Eladó konfig! Ryzen 7 7800X3D 2TB SSD 64GB DDR5 RX9070XT 16GB!
- Új, makulátlan állapotú Samsung Galaxy Buds FE, fehér, fél év garancia
- Új, makulátlan állapotú Samsung Galaxy Watch7 44mm ezüst, 2 év garancia
- Új, makulátlan állapotú Samsung Z Fold 6 256GB Tengerészkék, független, 2 év garancia
- Használt TP-Link Deco M4 - AC1200 Router (Mesh-ként is használható)
- ÁRGARANCIA!Épített KomPhone i5 12400F 16/32/64GB RAM RTX 3060 12GB GAMER PC termékbeszámítással
- Csere-Beszámítás! PowerColor Red Devil Spectral White RX 9070XT Videokártya! Bemutató Darab!
- Noblechairs HERO Fekete/Platinafehér Gamer Szék
- VÉGKIÁRUSÍTÁS - REFURBISHED - Lenovo ThinkPad 40AC Thunderbolt 3 docking station
- AKCIÓ! Acer Predator Triton Neo 16 15 notebook - Ultra 9 185H 32GB RAM 2TB SSD RTX 4070 WIN11
Állásajánlatok
Cég: CAMERA-PRO Hungary Kft
Város: Budapest
Cég: PC Trade Systems Kft.
Város: Szeged