43. feladatsor

Gráfelmélet

EMLÉKEZTETŐ

gráf:	Gráfnak nevezzük a csúcsoknak és éleknek a halmazát, ahol az élek pontokat kötnek össze, illetve az élek végére csúcsok illeszkednek úgy, hogy minden élre legalább egy, de legfeljebb két csúcs illeszkedik.
fokszám:	Az egy csúcsból induló élek száma. Például a B csúcs fokszáma 3, a C csúcs fokszáma 1.
izolált pont:	Olyan pont, amelyből nem indul ki él. Például az F pont.
többszörös él:	Többszörös élről beszélünk, ha két pontot több él is összeköt.
hurokél:	Olyan él, amelynek minkét vége ugyanarra a pontra illeszkedik.
egyszerű gráf:	Olyan gráf, amely nem tartalmaz többszörös élt és hurokélt.
összefüggő gráf:	Olyan gráf, amelyben élek mentén valamilyen úton el lehet jutni bármely pontjából bármely pontjába.
kör:	Az élek olyan sorozata egy gráfban, melyek visszavezetnek a kiindulási ponthoz.
teljes gráf:	Olyan egyszerű gráf, melyben bármely két pontot él köt össze.
komplementer gráf:	Olyan gráf, mely az eredeti gráf éleivel együtt teljes gráfot alkot.
fagráf:	Olyan összefüggő gráf, melyben nincs kör.
gráfra vonatkozó összefüggések:	1. Egy gráf összfokszáma (a csúcsok fokszámainak összege) mindig páros szám, az élek szá má nak kétszerese. 2. Egy n pontú teljes gráf éleinek száma: n(n -1)/2. 3. Egy n pontú fagráf éleinek száma: n-1.

FELADATOK

43.1. Rajzolj egy 5 pontú, 10 élű gráfot, amely tartalmaz többszörös élt!
Írd a pontok fölé a megfelelő fokszámot!

Max p.	Kapott p.
6 pont

---

43.2. Egy hattagú társaságban mindenkinek 3 ismerőse van.
Rajzold meg az „ismerősök” egy lehetséges gráfját!
Rajzold meg a „nem ismerősök” komplementer gráfját is!

Max p.	Kapott p.
6 pont

---

43.3. Tekintsük egy kocka csúcsait gráfpontoknak, éleit pedig a gráf éleinek.
a) Mennyi az egyes csúcsok fokszáma?
b) Mennyi a gráf összfokszáma?
c) Hány él hiányzik a teljes gráfhoz?

Max p.	Kapott p.
6 pont

---

43.4. Egy urnában 1 piros, 2 fehér és 3 zöld golyó van.
Ábrázold gráf segítségével a kihúzási sorrend lehetőségeit, ha elsőre piros golyót húzunk!

Max p.	Kapott p.
6 pont

---

43.5. Lehetséges-e olyan 15 fős csoport, melyben mindenkinek pontosan 5 barátja van?

Max p.	Kapott p.
6 pont

---

43.6. Az alábbi gráfok közül melyek rajzolhatók meg a ceruzánk felemelése nélkül úgy, hogy minden élt és minden pontot csak egyszer érintünk?

Max p.	Kapott p.
6 pont

---

43.7. Egy születésnapi összejövetelre érkezők kézfogással üdvözlik egymást.
Hányan vettek részt a partin, ha 120 kézfogás történt?

Max p.	Kapott p.
6 pont

---

43.8. A következő állításokról döntsd el, hogy igazak (I) vagy hamisak (H)!
a) Van olyan gráf, melynek összfokszáma 0.
b) Egy 5 pontú gráfnak maximum 10 éle lehet.
c) Van 10 élű és 10 pontú fagráf.
d) Nincs olyan 7 pontú gráf, melyben minden csúcs fokszáma 3.
e) Van olyan gráf, melynek több pontja van, mint éle.
f) Ha egy gráf összefüggő, akkor van benne kör.

Max p.	Kapott p.
6 pont

---

1. feladatsor

NÉV:
EREDMÉNY:

Ssz:	Max p.	Kap p.	Par.	Bemenet
1.
2.
3.
4.
5.
6.
7.
Össz