Létezik olyan eljárás, ami egy n pontú teljes gráfot totálisan jól színez n+1 színnel?
Figyelt kérdés
2019. okt. 21. 15:58
1/4 anonim 
válasza:
válasza:Kifejtenéd bővebben?
Mert így önmagában elég nagy marhaság, amit írtál...
2/4 anonim válasza:
válasza:Totális színezési sejtés: χ″(G) ≤ Δ(G) + 2, ami ugye a teljes gráfodra n+1-es jobb oldalt jelentene. A sejtést viszont még csak néhány gráfcsaládra igazolták, teljes gráfokra még nem. Ha létezik is ilyen eljárás, egyelőre még nem ismerjük.
3/4 A kérdező kommentje:
Tudtommal teljes gráfra bizonyízott, hogyha n páros, n színnel, ha páratlan, n+1 színnel jól színezhető.
2019. okt. 21. 16:18
4/4 anonim válasza:
válasza:Igazad van, közben utánaolvastam, és valóban bizonyították már teljes gráfokra. Viszont azt is olvasom, hogy a színezés megtalálása NP nehéz, és csak izomból, exponenciális időben lehet megoldani.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!