Subject: Alapfogalmak
From: "Mentette: a Windows Internet Explorer 9"
Date: Tue, 27 Sep 2011 18:09:30 +0200

Alapfogalmak

A
gráfelmélet a matematika tudományának viszonylag fiatal részterülete. Az első
gráfelméleti probléma a XVIII. sz. elején lépett fel ennek megoldása Euler
nevéhez fűződik. A Königsberg (mai nevén Kalinyingrád) városát átszelő Pregel
folyón két sziget van a város területén. E szigeteket hét híd köti össze a
város egyik és másik partjával, illetve egymással az ábrán látható módon.

A város
lakói vasárnaponként szerettek sétálni a szigeteken. Felvetődött a kérdés, hogy
hogyan lehetne olyan sétát tenni a városban, hogy e közben minden hídon pontosan
egyszer haladjanak át, és visszaérkezzenek a kiindulópontra. A
problémával Eulerhez fordultak, aki akkor a szentpétervári akadémia tanára
volt.  A probléma tárgyalásához
érdemes a gráfok néhány tulajdonságát megvizsgálni. (Józan paraszti
ésszel is megoldható)

Tulajdonképpen innentől számítjuk a gráfelmélet
megszületését és fejlődését.

Ma már a
matematikában, fizikában, geográfiában, kémiában és még számos területen
használják a gráfokat mint modelleket, valamint a gráfelmélet különböző
eredményeit a felmerülő kérdések, problémák megoldására.

Kőnig
Dénes (1884-1944) magyar matematikus, az első tudományos színvonalú gráfelméleti
könyv írója.

Korábban
is találkoztunk olyan problémákkal, amikor bizonyos dolgokat pontokkal, a
köztük levő kapcsolatokat vonalakkal, esetleg nyilakkal jelöltük. Eddig feladat
megoldása során a hosszú szöveg megértését segítették az ilyen típusú
ábrák.

Az előbbi
és a korábbi feladatok (és még számtalan ezekhez hasonló probléma) közös vonása,
hogy mindegyikük jól modellezhető egy olyan ábrával, melyen pontokat és e pontok
közül néhányat összekötő vonallal szemléltetünk. Az ilyen modellt nevezzük
gráfnak.

Def.:  A
síknak véges sok pontjából és az őket összekötő vonalakból álló alakzatokat
gráfnak nevezzük. A pontok a gráf pontjai
(vagy csúcsai), az összekötő vonalak a gráf élei.

Def.:  Ha a gráf valamely két csúcsát egynél
több él köti össze, akkor azt többszörös élnek
nevezzük.

Def.:  Hurokélnek nevezzük az olyan élt, amelynek a
két végpontja ua.

Def.:  Egy gráfot egyszerű gráfnak nevezünk, ha véges (azaz
pontjainak és éleinek a száma véges), és sem hurokélt, sem többszörös élt nem
tartalmaz.

Pl.
Egyszerű gráf
Pl. Nem egyszerű gráf

Def.:  Egy gráf egy pontjának a fokszáma (foka) a pontban találkozó élek
száma.

Pl.

Kukutyim
(1)
Boncida (2)

Munkavég (1)

Álmossarok (4)

Hencida
(4)

Iszapszentkukacos
(2)

Lustafalva
(2)

Dágványoshetye
(2)

Def.:  Ha egy pontban nincs él, azt a pontot
izolált pontnak nevezzük. Az izolált pont  fokszáma 0.

(1)
(0)

Az élek száma: 5

(2)

A pontok fokszámának az összege:

(1)    (4)

1 + 4 + 1 + 2 + 2 + 0 = 10

(2)

Mivel
minden él két pontba fut be a pontok fokszámának az összege minden gráfban
megegyezik az élek számának a kétszeresével.

Tétel:      Minden gráfban a
pontok fokszámának összege az élek számának kétszerese.  (Hurokélnél a pont fokszáma 2, hiszen ha
veszünk egy olyan gráfot, ami csak egy pontból és ahhoz tartozó hurokélből áll,
akkor is teljesül a gráfok pontjaira és éleire vonatkozó
összefüggés.)

Bizonyítás:

A fokszámok összegében minden élet
mindkét végpontjánál beleszámoltunk, ezért a fokszámok összege az élek
számának kétszerese.

Következmény:

Minden gráfban a pontok fokszámának
összege páros szám. ( Naná! Bármely egész szám kétszerese
páros.)

Minden gráfban a páratlan fokú pontok
száma páros. ( Naná! Páratlan egész számok  összege csak akkor páros, ha páros
darabszámút adunk össze. Pl. 1 + 3 = 4;
1 + 3 + 5 = 9 )

Feladat:

1. Egy öt
fős csapat buliba készül. Nagyon izgatottak, mert már két napja nem buliztak,
ezért mindenki beszél telefonon mindenkivel. Ábrázoljuk a szituációt
gráfként!

Def.:  Ha egy egyszerű gráf bármely két pontja
össze van kötve éllel, akkor teljes gráfnak nevezzük. (Az
egyetlen pontból - ún. izolált pontból - álló gráf is teljes
gráf.)

Pl. teljes
gráfot kapunk, ha egy konvex sokszögnek megrajzoljuk minden átlóját. Minden
csúcs fokszáma 4.

Ha Sára
bekavart Klárának és ezért Klára nem fogadja a hívását, akkor a gráf már nem
teljes.

2. Egy érettségi banketten a diákok és a tanárok közül sokan
koccintottak egymással. Igazolja, hogy csak páros számú ember végezhetett
páratlan számú koccintást!

Megoldás

Tétel:      Az n pontú teljes
gráf éleinek a száma

Biz.:

Minden csúcsból n–1
másik csúcsba lehet élt húzni, tehát összesen n(n–1) –t.

De így minden élt
kétszer számoltunk. Tehát n pontú teljes gráf éleinek a száma

Egy másik
biz.:

Mivel bármely két pont között van
él, ezért az élek száma annyi, ahányféleképpen az n pontból kettőt ki lehet
választani úgy, hogy a választás sorrendje lényegtelen. Ez pedig  féleképpen lehetséges.

Feladatok

1. Rajzoljon olyan hat pontú egyszerű gráfot, mely
csúcsainak fokszámai:

a) 1, 2, 3, 4, 5,
6

b) 5, 4, 4, 2, 0,
1,

c) 4, 4, 4, 2, 1, 1
,

d) 1, 2, 2, 3, 4, 4

e)4, 4, 2, 2, 2, 1

Megoldás

2. Állapítsa meg az alábbi gráfok egyes pontjainak a
fokszámait!

Megoldás

3. A Repülő Elefántok Társaságának
igazgatótanácsa tíztagú. Az igazgatótanácsi ülésre érkezvén néhányan kezet
fogtak egymással. A titkárnő a társaság minden tagját megkérdezte, hogy hány
másikkal fogott kezet.

A következőket jegyezte fel:

a) 3; 4; 6; 7; 6, 9; 5; 8; 7; 4.
Az igazgató leszidta a titkárnőt, hogy a feljegyzései pontatlanok voltak.
Honnan tudta?

b) Lehetnek-e pontosak a titkárnő
feljegyzései, ha a következőket írta:

2;
2; 1; 1; 1; 1; 1; 1; 1; 9?

c) Lehetnek-e pontosak a titkárnő
feljegyzései, ha a következőket írta:

0;
1; 2; 2; 3; 4;4 ;5 ;6 ;9?

d) Lehetnek-e pontosak a titkárnő
feljegyzései, ha a következőket írta:

9; 6; 4;
9; 6; 9; 8; 9; 9; 3?

Megoldás

4. Egy állami ünnepség alkalmával 10 személy kapott
kitüntetést. Az ünnepség után a kitüntetettek közül néhányan névjegykártyát
cseréltek egymással. Távozáskor az egyik szervező mindenkitől megkérdezte,
hogy hány személlyel cserélt névjegykártyát. Az alábbi válaszlehetőségek közül
melyik lehet jó? Amelyik jó, ahhoz készítsen egy szemléltető
gráfot!

a) 7, 4, 3, 5, 0, 2, 8, 4, 1 ,
5,

b) 1, 1, 2, 2, 1, 1, 2, 1, 4, 9,

c) 1, 3, 4, 7, 0, 2, 9, 1, 5, 6,

d) 6, 9, 7, 9, 9, 4, 9, 3, 6, 4.

Megoldás

5. Egy sakkversenyen minden résztvevő minden résztvevővel
egyszer játszik. Igazoljuk, hogy a verseny bármely szakaszában található két
olyan játékos, aki addig ugyanannyi mérkőzést
játszott!

Megoldás