Fokszámsorozatok

Definíció: Egy gráf fokszámsorozata pontjai fokszámáinak rendezett (növekvõ) sorozata. Tehát a fokszámsorozat hossza a gráf csúcsszámával egyezik meg.

Feladat: Állapítsuk meg a következõ egyszerû gráfok fokszámsorozatát.

• Vegyünk egy egység élhosszú kockát és minden lapjára ragasszunk egy ``alacsony'' négyzet alapú gúlát (alapja egységnégyzet, azaz a kocka lapjaival azonos méretû). Az így kapott test csúcsai és élei egy gráfot adnak.
• Egy hat elemû halmaz három elemû részhalmazai alkotják gráfunk csúcsait. Két csúcs össze van kötve, ha a megfelelõ két hármasnak pontosan két közös eleme van.
• Egy hat elemû halmaz három elemû részhalmazai alkotják gráfunk csúcsait. Két csúcs össze van kötve, ha a megfelelõ két hármasnak pontosan egy közös eleme van.
• Egy négy elemû halmaz sorbaállításai alkotják gráfunk csúcsait. Két csúcs össze van kötve, ha az egyik sorbaállításból a másik két szomszédos elem megcserélésével kapható.
• Egy sakktábla 64 mezõje alkotja gráfunk csúcshalmazát. Két mezõ szomszédos, ha egyikrõl a másikra szabályos huszárlépés vezet.
• * Egy 4 x 4 méretú sakktábla dominókkal való fedései alkotják gráfunk csúcshalmazát. (Egy dominó alakja két szomszédos mezõ alakja (ami lehet álló és fekvõ is). A dominó fedésben minden dominó két mezõt fed le úgy, hogy mind a 16 mezõ egyszeresen lesz lefedve.) Egy dominófedés szomszédait úgy kapjuk meg, hogy keresünk két dominót, amelyek együtt egy 2 x 2-es részt fednek le, majd ha ezek álló dominók voltak, akkor `elfektetjük', ha fekvõ dominók voltak, akkor `felállítjuk' õket.

Feladat: Rajzoljuk fel az összes legfeljebb 8 pontú egyszerû gráfot, amely minden pontjának foka 3.

Definíció: Egy gráfot regulárisnak nevezünk, ha minden pontjának ugyanannyi a foka. Ha a közös fokszám k, akkor azt mondjuk gráfunk k-reguláris.

Feladat: Egy gráfról annyit tudunk, hogy 19 éle van és minden fokszáma 2 vagy 3. Mi gráfunk lehetõ legnagyobb pontszáma és mi a lehetõ legkisebb?

Feladat: Lehet-e 0,1,2,3,4,5,6,7,8,9 egy gráf fokszámsorozata?

Feladat: Lehet-e 0,1,2,3,4,5,6,7,8 egy gráf fokszámsorozata?

Feladat: Lehet-e 0,1,2,3,4,5,6,7,8 egy egyszerû gráf fokszámsorozata?

Feladat: Legyen S egy ponthalmaz a G gráfban. Fejezzük ki más gráfelméleti paraméterekkel az S-beli pontok fokszámainak összegét.

A válasz.

Definíció: Egy G gráfot páros gráfnak nevezünk, ha pontjai két diszjunkt osztályba vannak sorolva úgy, hogy tetszõleges él két végpontja különbözõ osztályba esik.

Megjegyzés: Az elõzõ feladatból (de józan gondolkodással is egyszerûen) adódik, hogy egy páros gráfra az egy-egy csúcsosztályba esõ csúcsok fokszámainak összege azonos és egyenlõ az élek számával.

Feladat: Egy partin 8 nõ vesz részt. Az érkezésnél minden nõ 9 férfival fog kezet. A férfiak mindegyike 6 nõvel fog kezet. hány férfi vett részt a partin?

Feladat: Lehet-e 3,3,3,3,3,3,4,6,6,6,6,6,6,6 egy páros gráf fokszámsorozata?

Feladat: Egy 2n pontú gráf minden fokszáma ugyanaz. bizonyítsuk be, hogy tetszõlegesen két egyenlõ részre osztva a gráf ponthalmazát a két részen belül az élek száma megegyzik.

Feladat: Egy iroda vesz 8 printert és 12 számítógépet, majd bizonyos gépeket összeköttett bizonyos printerekkel. Úgy szeretnék megtervezni az összeköttetéseket, ha legfeljebb 8 gép szeretne egyszerre nyomtatni, akkor az összeköttetések megengedjék az egyszerre történõ nyomtatást. Mi a minimálisan szükséges összeköttetések száma?

Feladat: Egy 2n pontú gráf minden fokszáma ugyanaz. bizonyítsuk be, hogy tetszõlegesen két egyenlõ részre osztva a gráf ponthalmazát a két részen belül az élek száma megegyzik.

Feladat: Egy gráf átlag foka d. Bizonyítsuk be, hogy található olyan részgráfja, amelyben minden fokszám legalább d/2.