Informatikai és Hírközlési Minisztérium Oktatási Minisztérium Apache Php Mysql Fazekas Mihály Gyakorlóiskola
  Bejelentkezás
Üdvözöljük a Matematika portálon!  
Recski András, Gráfok színezése Előadások, 2007/2008. tanév

Recski András

Gráfok színezése

című 2008. január 22-ei előadását lejegyezte Lenger Dániel és Prok Tamás



1. Az alapfeladatok

Gráfok színezésével kapcsolatos klasszikus feladat a térképszínezési probléma: adott egy síkba rajzolható gráf, amely tartományokra osztja a síkot; legkevesebb hány színnel lehet kifesteni a tartományokat úgy, hogy élben szomszédos tartományok színe mindenhol különböző legyen. Az előadásban erről a feladatról nem esett szó, mert a gráf éleinek és pontjainak színezése volt a téma. Két probléma szokott felmerülni a pontok és élek színezésével kapcsolatban:

1. Legkevesebb hány színnel lehet egy gráf pontjait kiszínezni úgy, hogy semelyik két szomszédos pont ne kaphasson azonos színt?
2. Legkevesebb hány színnel lehet egy gráf éleit kiszínezni úgy, hogy semelyik két egy csúcsba futó él ne kaphasson azonos színt?

Példák: Egy négyszög egyik átlóját behúzzuk. Próbáljuk meg kiszínezni az így kapott gráfot!

Csúcsszínezés. Színezzük a bal oldali ábrán látható A és B csúcsot pirossal és kékkel, ekkor, közös szomszédjuk, a C csúcs már nem lehet se piros, se kék, kell egy harmadik szín, például zöld. Végül a negyedik csúcs nem lehet se piros, se zöld, de kék még igen, -- persze másmilyen is, de az a cél, hogy minél kevesebb színnel színezzünk --, így legyen kék. Kevesebb nyilván nem elég, mert van három pont, amik páronként szomszédosak, tehát csak ezek miatt kell legalább három szín.

Élszínezés. Induljunk ki a C pontból. Ennek fokszáma három, tehát a három él indul ki belőle. A kikötés miatt ezeknek nem szabad azonos színűnek lenni, így legalább három színre szükség van: például pirosra, kékre és zöldre. A (B, A) él nem lehet piros és kék, de zöld még igen, és az (A, D) él pedig már nem lehet zöld vagy kék, de piros még igen, tehát piros lesz.

A példákban véletlenül a pont- és élszínezés olyan feladat volt, hogy mindkettőt meg lehetett csinálni három színnel, de kettővel már nem. Általában a két feladat természetesen teljesen különböző. A görög ábécé χ betűjével szokták jelölni a gráf kromatikus számát, azaz, hogy legalább hány szín szükséges a gráf pontjainak színezéséhez, esetünkben ez 3. Az élek színezése esetén ezt kromatikus indexnek szokták nevezni, jelöljük ezt χe-vel, éppenséggel ez is 3.

Folytatás a PDF fájlban:



Kiemelt támogatónk 2006-ban:
Tigra Computer
Támogatóink 2003-ban:
Oktatási Minisztérium
Powered by:
Apache + Php + Mysql
Kapcsolat
hraskoa@fazekas.hu
Copyright © 2004-2010 Fazekas Mihály Fővárosi Gyakorló Általános Iskola és Gimnázium. Served by pingvin.