Adrian.Leverkuhn kérdése:
Gráfos feladatban tudnátok segíteni?
Figyelt kérdés
A G gráf csúcshalmaza {1,2,..., 100}. Legyen {i, j} él pontosan akkor, ha 1<=|i-j|<=6. Mennyi a gráf kromatikus és élkromatikus száma?2018. febr. 18. 15:08
1/3 A kérdező kommentje:
Az élkromatikus számmal kapcsolatban próbáltam becsléseket felállítani. Mivel a gráfban egy csúcs maximális fokszáma 12, ezzel máris alsó becslésünk van az élkromatikus számra.
Az is világos, hogy a gráf egyszerű, így használható a Vizing-tétel, mely szerint maximális fokszám+1, azaz 13 lesz az élkromatikus szám egyik felső becslése.
Annyi a kérdés, hogy innentől hogyan döntöm el, hogy a 12 vagy a 13 a nyertes?
2018. febr. 18. 15:11
3/3 Baluba 
válasza:
válasza:A kromazikus száma 7. Tartalmaz K_7-et, tehát legalább 7, viszont 7 színre a modulo 7 színezés jó, tehát legfeljebb 7 a kormatokus szám.
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!