Weboldalunk cookie-kat használhat, hogy megjegyezze a belépési adatokat, egyedi beállításokat, továbbá statisztikai célokra és hogy a személyes érdeklődéshez igazítsa hirdetéseit. További információ

Főoldal Belépés/Regisztráció Egy véletlen kérdés Facebook






Kategória: Közoktatás, tanfolyamok » Házifeladat kérdések

A kérdés

Ha egy gráf maximális fokszáma 5, akkor a gráf kromatikus száma 6, tehát a csúcsait minimálisan hatféle különböző színnel lehet kiszínezni úgy, hogy a szomszédos csúcsok más-más színt kapjanak?


Keress kérdéseket hasonló témákban: gráf, gráfszínezés

  máj. 16. 10:23  Privát üzenet  

A válasz

Nem.

Legyen a gráf csúcsainak halmaza V = {A, B, C, D, E, F}

Az élek halmaza pedig E = {{F,A}, {F,B}, {F,C}, {F,D}, {F,E}}.

Ekkor a (V, E) gráf A, B, C, D és E csúcsainak fokszáma 1, az F csúcsé 5, tehát a maximális fokszám 5, ahogy a feltételedben szerepel.

Viszont az egy jó színezés, hogy az A, B, C, D és E csúcsokat karmazsinnal festjük be (mert nincs köztük él), az F csúcsot pedig okkersárgára színezzük. Ezzel minden csúcsot befestettünk, és csak két színt használtunk, tehát a 2 szín is elég volt, nem kellett 6.


[link]



A válaszíró 86%-ban hasznos válaszokat ad.
# 1/1Időpont máj. 19. 17:28 Privát üzenet
Hasznos számodra ez a válasz?

Értesítsünk róla, ha új válasz érkezik? Válasz küldése



Kapcsolódó kérdések
A három színnel színezhető gráfok jellemezhetők valahogy egyszerűen? Mert az 1,2,4 az egyszerű, de a három nem tűnik triviálisnak.
Gráfos feladatban tudnátok segíteni?
Mennyi G gráf kromatikus száma, ha G csúcshalmaza (1,2,3, . ,100) és ij pontosan akkor él, ha i nem egyenlő j, illetve i és j nem relatív prímek?
Gráfok színezése: Hogyan lehetne megadni a kromatikus számot és stb. próbálgatás nélkül?
Legyen G egy 100-reguláris,613 csúcsú egyszerű gráf. Mennyi az élkromatikus száma?
Mit jelent egy gráf kromatikus száma? Ill. hogyan bizonyíthatjuk be egy gráfról, hogy a kromatikus számuk legalább 3?

Kérdések a Közoktatás, tanfolyamok rovatbólKérdések a Házifeladat kérdések rovatból








Minden jog fenntartva © 2018, www.gyakorikerdesek.hu | GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Sitemap | WebMinute Kft. | 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!