a) Döntse el, hogy az alábbi négy állítás közül melyik igaz és melyik hamis! Válaszát írja a táblázatba! A: Egy 6 pontot tartalmazó teljes gráfnak 15 éle van. B: Ha egy teljes gráfnak páros számú éle van, akkor a pontok száma is páros. C: Ha egy 51 pontú gráfban nincs kör, akkor legfeljebb 50 éle lehet. D: Nincs olyan 6 pontú gráf, amelyben a fokszámok összege 11. A B C D b) Ha valaki sohasem hallott a gráfokról, és mégis kitölti a fenti táblázatot, akkor mekkora valószínűséggel lesz helyes mind a négy válasza? c) Tagadja az alábbi mondatot: Nincs olyan szerelem, aki el nem múlik. (Népdalgyűjtés) d) Fogalmazzon meg egy olyan szöveges feladatot, amelynek a megoldása így számítható ki: 2 17 .

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1116

a) A következő két állításról döntse el, hogy igaz vagy hamis. Válaszait indokolja! (1) Van olyan ötpontú egyszerű gráf, amelynek 11 éle van. (2) Ha egy ötpontú egyszerű gráf minden csúcsa legalább harmadfokú, akkor biztosan van negyedfokú csúcsa is. b) Az A, B, C, D és E pontok egy ötpontú teljes gráf csúcsai. A gráf élei közül véletlenszerűen beszínezünk hatot. Mekkora a valószínűsége annak, hogy az A, B, C, D, E pontokból és a színezett élekből álló gráf nem lesz összefüggő?

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1408

Tekintsük a következő, egyszerű gráfokra vonatkozó állítást: Ha a gráf minden pontjának fokszáma legalább 2, akkor a gráf biztosan összefüggő. a) Döntse el, hogy igaz vagy hamis az állítás! Válaszát indokolja! b) Fogalmazza meg az állítás megfordítását! Döntse el, hogy igaz vagy hamis az állí- tás megfordítása! Válaszát indokolja! Tekintsük a következő halmazokat: P = {összefüggő gráfok}, Q = {egyszerű gráfok}, R = {kört tartalmazó gráfok}. c) Helyezze el az alábbi gráfok ábrájának sorszámát a fenti halmazábrában a megfele- lő helyre! 1. ábra 2. ábra 3. ábra 4. ábra d) Rajzoljon egy 6 pontú fagráfot az 5. ábrára, és helyezze el ennek a sorszámát is a fenti halmazábrában a megfelelő helyre!

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1417

a) Határozza meg az alábbi kijelentések logikai értékét (igaz-hamis)! Válaszait indokolja! I. Van olyan hatpontú fagráf, amelynek minden csúcsa páratlan fokszámú. II. Ha egy hétpontú egyszerű gráfnak 15 éle van, akkor a gráf összefüggő. III. Van olyan fagráf, amelyben a csúcsok számának és az élek számának összege páros. Egy hatfős társaság tagjai A, B, C, D, E és F. Mindenkit megkérdeztünk, hogy hány is- merőse van a többiek között (az ismeretség kölcsönös). A válaszként kapott hat termé- szetes szám szorzata 180. Az is kiderült, hogy A-nak legalább annyi ismerőse van, mint B-nek, B-nek legalább annyi ismerőse van, mint C-nek, és így tovább, E-nek legalább annyi ismerőse van, mint F-nek. b) Szemléltesse egy-egy gráffal a lehetséges ismeretségi rendszereket!

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1497

a) Egy 9 pontú fagráfban ismerjük 8 pont fokszámát: 1 1 1 1 2 3 3, 3. Határozza meg a kilencedik pont fokszámát! b) Van-e olyan 9 pontú egyszerű gráf, amelyben mind a 9 pontnak más a fokszáma? c) Egy kilenctagú társaságban kézfogással köszöntik egymást az emberek. Eddig 4 kézfogás történt. Hány különböző módon történhetett ez meg, ha senki sem fo- gott kezet egynél többször, és a kézfogások sorrendjére nem vagyunk tekintettel?

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1525

A H halmaz a nyolcpontú egyszerű gráfok halmaza. A következő állítás a H elemeire vonatkozik: Ha egy (nyolcpontú egyszerű) gráf minden pontjának fokszáma legalább 3, akkor a gráf összefüggő. a) Döntse el, hogy az állítás igaz vagy hamis! Válaszát indokolja! b) Fogalmazza meg az állítás megfordítását a H elemeire vonatkozóan, és döntse el a megfordított állításról, hogy igaz vagy hamis! Válaszát indokolja! Az ABCDE konvex ötszög csúcsait piros, kék vagy zöld színűre színezzük úgy, hogy bármely két szomszédos csúcsa különböző színű legyen. c) Hány különböző színezés lehetséges? (Az ötszög csúcsait megkülönböztetjük egymástól.) Egy négypontú teljes gráf élei közül véletlenszerűen kiválasztott négy élt kiszínezünk zöldre. (Teljes gráf: olyan egyszerű gráf, melynek bármely két pontja között van él.) d) Határozza meg annak a valószínűségét, hogy a zöldre színezett élek a gráf egy négypontú körének élei!

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1540

a) Legyen G egy nyolcpontú egyszerű gráf, amelynek összesen 9 éle van. Igazolja, hogy G csúcsai között biztosan van olyan, amelynek a fokszáma legalább 3. b) Az A, B, C, D, E, F, G, H pontok egy szabályos nyolcszög csúcsai. Megrajzoljuk a nyolcszög oldalait és átlóit. A megrajzolt szakaszok közül véletlenszerűen kivá- lasztunk négyet. Határozza meg annak a valószínűségét, hogy mind a négy kivá- lasztott szakasz az A csúcsból indul ki! c) Nyolc sakkozó részére egyéni bajnokságot szerveznek. Hányféleképpen készíthető el az első forduló párosítása, ha ebben a fordulóban mindenki egy mérkőzést játszik? (Két párosítást különbözőnek tekintünk, ha az egyik tartalmaz olyan mérkőzést, amelyet a másik nem.)

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1555

Az ábrán egy 3×3-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ás- hoz a teljesen kirakott képben. a) Rajzolja fel a kirakós játék gráfját (a csúcsok azonosításával együtt), és határozza meg a gráfban a fokszámok összegét! b) Igazolja, hogy a megrajzolt gráfban nincs olyan (gráfelméleti) kör, amely páratlan sok élből áll! c) A teljesen kirakott képen jelöljön meg a puzzle-elemek közül 7 darabot úgy, hogy a kirakósjáték általuk alkotott részlete (a részletnek megfelelő gráf) már ne legyen összefüggő! d) Hányféleképpen lehet a puzzle-elemek közül hármat úgy kiválasztani, hogy ezek a teljesen kirakott képben kapcsolódjanak egymáshoz (azaz mindhárom képrészlet közvetlenül kapcsolódjék legalább egy másikhoz a kiválasztottak közül)? (Az elemek kiválasztásának sorrendjére nem vagyunk tekintettel.)

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 7702

Egy szabályos tízszög legrövidebb átlója 6 cm hosszú. a) Határozza meg a tízszög oldalának hosszát! Legyen G egy tízpontú egyszerű gráf, melynek összesen 6 éle van. b) Igaz-e, hogy G csúcsai közt biztosan van legalább két olyan, amelynek a fokszáma legalább 2? Válaszát indokolja! Egy n pontú teljes gráf egyik élét pirosra színeztük (n 3). Ezután a többi él közül vélet- lenszerűen kiválasztunk egyet. Legyen az A esemény az, hogy a kiválasztott élnek és a pirosra színezett élnek van közös csúcsa, a B esemény pedig az, hogy nincs közös csú- csuk. c) Ha az A és a B esemény egyenlő valószínűségű, akkor hány pontja van a gráfnak?

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 9001

a) Két pozitív egész szám relatív prím, legkisebb közös többszörösük 35 700. Határozza meg az ilyen tulajdonságú számpárok számát! (Az (a, b) és a (b, a) számpárokat nem tekintjük különbözőknek.) b) Legyen H = {1 2 3 4 5 6 7 8 9 10}. Hány olyan részhalmaza van H-nak, amelyben az elemek szorzata osztható 9-cel? (Egyelemű halmaz esetén az elemek szorzatának az egyetlen elem értékét tekintjük.) c) Egy papírlapon adott öt pont. A pontok mellé egy-egy pozitív egész számot írunk. Az adott pontok legyenek egy olyan ötpontú egyszerű gráf csúcsai, amelynek két csúcsa pontosan akkor van éllel összekötve, ha a csúcsok mellé írt számok közül az egyik többszöröse a másiknak. Az alábbi három ábra mindegyikén 5-5 pont látható. Írjon mindhárom ábrán az 5 pont mellé különböző pozitív egész számokat, majd rajzolja meg a fenti szabály szerint a gráf éleit úgy, hogy az első esetben egy teljes gráfot, a második esetben egy fagráfot, a harmadik esetben pedig egy üres gráfot kapjon (az üres gráfnak egyetlen éle sincsen)!

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 10281

a) Három lány és négy fiú moziba megy. Egy sorba szól a jegyük, hét egymás melletti székre. Hányféle sorrendben ülhetnek le, ha két lány nem ülhet egymás mellé? b) A nézőtéren az első és a második sorban már csak 3-3 szabad ülőhely van. A máso- dik sor szabad ülései pontosan az első sor szabad ülései mögött vannak. Hányféleképpen tud leülni egy hatfős társaság a hat szabad helyre úgy, hogy a má- sodik sorban mindenki magasabb legyen a közvetlenül előtte ülőnél? (A hat személy magassága különböző.) c) Egy 8 pontú egyszerű gráfnak 13 éle van, és az egyik pontjának a fokszáma 6. Igazolja, hogy van hárompontú kör (gráfelméleti háromszög) a gráfban!

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 10836