Gráfelméleti alapok

Oldjuk meg az alábbi gráfos feladatokat:

a) Egy tárgyalás elején minden résztvevő mindenkivel kezet fog. Így összesen minden résztvevő 4 másikkal fog kezet. Hányan vesznek részt a tárgyaláson és hány kézfogás volt összesen?

b) Egy iskolai versenyen Anna, Bence, Cecil, Dávid, Elemér, Fanni, Gábor, és Hanna játszanak egymással. Mindenki mindenkivel pontosan egyszer játszik.

Anna már játszott Bencével, Gáborral és Hannával.

Bence már játszott Annával, Cecillel és Gáborral.

Cecil csak Bencével, Dávid pedig csak Elemérrel játszott.

Rajzoljuk fel azt a gráfot, ami a jelenlegi állást tartalmazza! Hány játszma van még hátra?

c) Egy ötpontú teljes gráf csúcsai A, B, C, D, E.

Mekkora a B csúcs fokszáma?

Ha a gráfból két élt törlünk, milyen lehetséges értékek adódhatnak B fokszámára?

Mekkora lesz a két él törlése után a csúcsok fokszámainak összege?

Hány élt kell törölni ahhoz, hogy minden csúcs fokszáma 3 legyen?

a) Egy hatfős társaságban mindenkit megkérdeztek, hány ismerőse van a többiek között (az ismerettségek kölcsönösek). Az első öt személy válasza: 5, 4, 3, 2, 1. Ábrázoljuk a gráffal a társaság ismerettségi viszonyait! Hány ismerőse van a hatodik személynek a társaságban?

b) Rajzoljunk egy olyan hatpontú gráfot, amelyben a pontok fokszáma: 0, 1, 2, 2, 3, 4.

c) Egy irodában összesen 11-en dolgoznak. Egy adott napon a 11 ember ennyi kollégájával találkozott: 0, 1, 2, 2, 2, 5, 0, 0, 4, 4, 2.

Ábrázoljuk a találkozásoknak egy lehetséges gráfját. Hány találkozás volt összesen?

Oldjuk meg a könisbergi-hidak rejtélyét.

Létezik-e olyan gráf, amelyben a pontok fokszáma:

a)  4, 4, 4, 5, 5, 5, 6, 6

b)  2, 2, 4, 4, 5, 7, 7, 7

c) 3, 3, 4, 4, 5, 7, 7, 7

d) 5, 3, 3, 2, 2, 1, 1, 1

a) A városi középiskolás egyéni teniszbajnokság egyik csoportjába hatan kerültek: András, Béla, Csaba, Dani, Ede és Feri. A versenykiírás szerint bármely két fiúnak pontosan egyszer kell játszania egymással. Eddig András már játszott Bélával, Danival és Ferivel. Béla játszott már Edével is. Csaba csak Edével játszott, Dani pedig Andráson kívül csak Ferivel. Ede és Feri egyaránt két mérkőzésen van túl. Szemléltessük gráffal a lejátszott mérkőzéseket!

b) Egy iskola asztali tenisz bajnokságán hat tanuló vesz részt. Mindenki mindenkivel egy mérkőzést játszik. Eddig Andi egy mérkőzést játszott, Barnabás és Csaba kettőt-kettőt, Dani hármat, Enikő és Feri négyet-négyet.

Rajzold le az eddig lejátszott mérkőzések egy lehetséges gráfját!

Lehetséges-e, hogy Andi az eddig lejátszott egyetlen mérkőzését Barnabással játszotta?

Öt különböző számjegyet leírtunk egy papírlapra. Két számjegyet pontosan akkor kötünk össze egy vonallal (éllel), ha a különbségük páros szám (de egyik számjegyet sem kötjük össze önmagával). Így egy ötpontú gráfot kapunk. Döntsük el az alábbi állításokról, hogy igazak, vagy hamisak!

a) Lehetséges, hogy fagráfot kapunk.

b) Lehetséges, hogy nem összefüggő gráfot kapunk.

Az ábrán egy 3x3-as kirakós játék (puzzle) sematikus képe látható. A kirakós játékot egy gráffal szemléltethetjük úgy, hogy a gráf csúcsai (A1, A2, ..., C3) a puzzle-elemeket jelölik, a gráf két csúcsa között pedig pontosan akkor vezet él, ha a két csúcsnak megfelelő puzzle-elemek közvetlenül (egy oldalban) kapcsolódnak egymáshoz a teljesen kirakott képben.

a) Rajzoljuk fel a kirakós játék gráfját, és határozzuk meg a fokszámok összegét!

b) Igazoljuk, hogy a megrajzolt gráfban nincs olyan kör, amely páratlan sok élből áll!

c) A teljesen kirakott képen jelöljünk meg a puzzle-elemek közül 7 darabot úgy, hogy a kirakós játék általuk alkotott részlete már ne legyen összefüggő!

a) Rajzolj egy olyan 5 pontú gráfot, melyben a pontok fokszáma: 4, 3, 3, 2, 2

b) Rajzolj egy olyan 6 pontú gráfot, melyben a pontok fokszáma: 0, 1, 2, 2, 3, 4.

Létezik-e olyan fa, amelyben a pontok fokszáma:

a) 1, 1, 2, 2, 3, 4?

b) 1, 2, 2, 2, 3, 4?

c) 1, 1, 1, 1, 1, 5?

d) 1, 1, 1, 2, 2, 3?

Létezik-e olyan gráf, amelyben a pontok fokszáma: 6, 3, 3, 3, 2, 2, 2, 1?

Létezik-e olyan egyszerű gráf, amelyben a pontok fokszáma 7, 5, 5, 3, 3, 3, 3, 3?

Létezik-e olyan egyszerű gráf, amelyben a pontok fokszáma 7, 5, 5, 5, 4, 4, 4, 4?

Öt különböző számjegyet leírunk egy papírlapra. Két számjegyet pontosan akkor kötünk össze egy vonallal, ha a különbségük páros szám (de egyik számjegyet sem kötjük össze önmagával). Így egy ötpontú gráfot kapunk.

a) Lehetséges, hogy fagráfot kapunk?

b) Lehetséges, hogy nem összefüggő gráfot kapunk?