18. FEJEZET: Gráfok{mchap:k_i_grafok}
Feladat: 18.1. {berg1_02}
Egy társaságban öt ember találkozott. Megkérdeztük őket, kinek
hány ismerőse van ötük között. A válaszok:
A: - Négy embert ismerek.
B: - Kevesebb ismerősöm van, mint
A-nak.
C: - Ugyanannyi ismerősöm van, mint
D-nek.
D: - Eggyel kevesebb ismerősöm van, mint
E-nek.
E: - Páratlan számú embert ismerek.
Ismeri-e egymást
C és
D?
Feladat: 18.2. {berg1_42}
Rajzoljunk ,,térképet", amin 5 város van, a városok között utak.
a) Az egyes városokból 1,2,2,3,4 út indul. Hány út van a
térképen?
b) Az egyes városokból 1,2,2,3,3 út indul. Hány út van a
térképen?
Feladat: 18.3. {k_i_graf_dsrg_060520_01}
Igaz-e, hogy bármely 9 tagú társaságban van olyan ember,
akinek páros számú ismerőse van?
Feladat: 18.4. {Komal_F2411_1983_11_123}[
115]
Van-e olyan tíztagú társaság, amelyben az embereknek rendre
a)
4,3,3,3,3,3,3,3,3,3;
b)
9,3,3,3,3,3,3,3,2,0;
c)
9,3,3,3,3,3,3,3,2,2;
d)
9,9,9,8,8,8,7,6,4,4
ismerőse van? (Az ismeretséget kölcsönösnek tételezzük fel.)
Feladat: 18.5. {SurgrafI_1_07fel}[
114]
Egy város telefonközpontjában számontartják, hogy a központhoz
tartozó telefonállomások mindegyikéről hány másikat hívtak fel
aznap (ha egy állomást többször is felhívtak, azt is csak egynek
számítják). Igaz-e, hogy van két telefonállomás, amelyről
ugyanannyit hívtak?
Feladat: 18.6. {SurgrafI_1_01fel_vari}[
114]
Egy társaságban némely emberek kezet fogtak egymással. Igaz-e,
hogy mindig van két ember, aki ugyanannyiszor fogott kezet?
Feladat: 18.7. {SurgrafI_1_01fel}[
114]
a) Egy társaságban lejátszottak néhány sakkmérkőzést.
Bármely két ember legfeljebb egy mérkőzést játszott egymás ellen.
Bizonyítsuk be, hogy mindenképpen volt két olyan ember, aki
ugyanannyi emberrel mérkőzött meg.
b) Igaz marad-e az állítás akkor is, ha megengedjük, hogy
két ember többször is mérkőzzön egymással?
Feladat: 18.8. {SurgrafI_1_21fel}[
114]
Egy táncos estén négy fiú és négy lány vett részt. Megkérdeztük a
lányokat, hogy hány fiúval táncoltak és a következő válaszokat
kaptuk: 3, 1, 2, 2. Megkérdeztük a fiúkat is, hogy hány lánnyal
táncoltak és a következő válaszokat adták: 2, 2, 3, 2. Mutassuk
meg, hogy valaki nem az igazat mondta!
Feladat: 18.9. {SurgrafI_1_22fel}[
114]
a) Egy táncos estén 21 fiú és 21 lány vett részt. Minden
fiú vagy négy lánnyal vagy két lánnyal táncolt, kivéve egyet, aki
hat lánnyal táncolt. Lehetséges-e, hogy minden lány három vagy öt
fiúval táncolt?
b) Egy 21 tagú társaságból mindenki két vagy négy
másiknak írt levelet, kivéve egyet, aki hat társának írt levelet.
Lehetséges-e, hogy mindenki három vagy öt levelet kapott?
Feladat: 18.10. {k_i_graf_dsrg_060520_12}
Adjunk meg, ha
lehet olyan gráfot, amelyben a fokszámok:
a) 1
2
3
4
5
6;
b) 5
5
5
6
6
6
7
7
7;
Feladat: 18.11. {milan_hejny_05_11_11_01}[
146]
Az
1. ábrán néhány községet és a
köztük futó utakat tüntettük fel sematikusan. Tudjuk, hogy a
vidéken két buszjárat közlekedik, melyek rendre az alábbi
községeket keresik fel:
I. járat:
C
E
F
B;
II. járat:
F
C
A
D.
1. ábra{fig:milan_hejny_05_11_11_01_fel}
Az állomások az egyes járatokon a feltüntetett sorrendben
következnek. Jelöljük be a térképen (külön
a)-n, illetve
b)-n) az
A-nak megfelelő községet!
Feladat: 18.12. {SurgrafI_1_17fel}[
114]
Egy társaságban öt házaspár van jelen. Azok, akik nem ismerik
egymást, bemutatkozásul kezet fognak egymással. Kovács úr
megkérdezi minden jelenlevőtől, hogy hány emberrel fogott kezet és
csupa különböző számot kap válaszul. Hány emberrel fogott kezet
Kovácsné? És Kovács úr?
Feladat: 18.13. {SurgrafI_1_24fel}[
114]
Egy összejövetelen 21 gyerek vett részt. Mindegyiktől sorra megkérdeztem, hány osztálytársa van a jelenlévők közt. Az első 13 válaszoló közül öten mondtak hármat, nyolcan négyet. Vajon hány osztálytársa volt jelen a többi gyereknek, ha azt tudjuk, hogy mindegyiküknek volt jelen legalább egy osztálytársa?
Feladat: 18.14. {SurgrafI_1_25fel}[
114]
Egy tíztagú társaságról tudjuk, hogy minden tagja legalább hét
másikat ismer. Igazoljuk, hogy a társaságból bármely három
személynek van közös ismerőse. Hogyan általánosítható a feladat?
Fogalmazzuk meg az általános állítást gráfelméleti nyelven!
Feladat: 18.15. {Eulerut_05_11_12_HA_01}
Rajzoljuk le az
1. ábrán látható
figurákat a ceruza felemelése nélkül! Minden vonalon csak egyszer
szabad haladni, de már megrajzolt vonalat keresztezni szabad.
1. ábra{fig:Eulerut_05_11_12_HA_01}
Jelöljük meg, hogy honnan indulva és hová érkezve sikerült
elkészíteni a rajzot! Hasonlítsuk össze a különböző megoldók
eredményeit és keressünk magyarázatot! (Vigyázat, nem mindegyik
esetben van megoldás!)
Feladat: 18.16. {Eulerut_05_11_12_HA_02_berg1_55}[
39]
Az
1. ábrán egy
3×3-as
,,rács" látható. Kis négyzetekből áll. Rakjuk össze
1. ábra{fig:Eulerut_05_11_12_HA_02}
a) nyolc darab három
b) négy darab hat
c) hat darab négy
d) három darab nyolc hosszúságú cérnából!
A cérnát elvágni nem szabad.
Feladat: 18.17. {Eulerut_05_11_12_HA_03_berg1_104}[
39]
A sakktáblán úgy helyeztünk el figurákat, hogy minden sorban és
minden oszlopban
a) pontosan
b) legalább
2 bábú
található. Biztosak lehetünk-e benne, hogy ebben az esetben le
lehet venni a tábláról néhány figurát úgy, hogy minden sorban és
minden oszlopban pontosan 1 figura maradjon?
Feladat: 18.18. {Eulerut_05_11_12_HA_04_berg1_109}[
39]
Van egy készlet dominónk. E dominókra a 0, 1, 2,
…, 10
számok vannak írva, mindegyik dominóra két szám. Készletünk
teljes, azaz a fent említett számokból képzett bármely számpárhoz
pontosan egy olyan dominó található, amelyre az a két szám van
fölírva.
a)A készletből maximálisan hány dominó rakható ki az
asztalra a játék szabályainak megfelelően?
b)Mi a helyzet akkor, ha teljes készletünk darabjaira a
0, 1, 2,
…, 9 számok vannak írva?
Feladat: 18.19. {k_i_graf_ha_080308_01}
Hány olyan ötpontú gráf van, amelynek fokszámai:
a)
1,2,2,3,3;
b)
1,2,2,2,3?
Feladat: 18.20. {k_i_graf_dsrg_060520_14}
Hogyan
helyezkedhet el 4 pont a síkban, ha a köztük
fellépő távolságok között nincs három
különböző?
Feladat: 18.21. {berg1_19}
A Bergengóc Közlekedési Minisztérium felkért egy légitársaságot,
hogy indítson ingajáratokat az ország legfontosabb városai között
úgy, hogy egy városból legfeljebb három másikba induljon járat, de
legfeljebb egy átszállással el lehessen jutni bármelyik városból
bármelyik másikba. Legfeljebb hány város között lehet megszervezni
ilyen összeköttetést? (Ingajárat: két város közti összeköttetés)
Feladat: 18.22. {berg1_90}
Néhány évvel a Délnyugati Birodalom széthullása után a területén
létrejött 16 hercegség mindegyike 3 másikkal barátságban élt, a
többivel pedig ellenségeskedett. A hajdani birodalom
szomszédságában található 8 állam elhatározta, hogy segítséget
nyújt a viszályokban tönkrement hercegségeknek, méghozzá mindegyik
állam 2 egymással barátkozó hercegségnek nyújt támogatást. Meg
lehet-e szervezni minden esetben a segélyezést úgy, hogy mindegyik
hercegség részesüljön belőle?
Feladat: 18.23. {berg2_224}
Egy kocka lapjait 4-4 négyzetre osztottuk föl. Tekintsük azokat a
kis szakaszokat, amelyek a kocka lapjain található összesen 24
négyzet közül egyszerre kettőnek is oldalai. Ezek közül 26 piros.
Bizonyítsuk be, hogy van olyan zárt töröttvonal, ami csupa piros
szakaszból áll!
1. ábra{fig:berg2_224}
Feladat: 18.24. {k_i_graf_ha_080308_10}
A Bergengóc Közlekedési Minisztérium takaréskoskodik. A lehető legkevesebb ingajárattal szeretné megoldani, hogy
10 legnagyobb városából a
10 közül bármelyik másikba el lehessen jutni, ha szükséges átszállásokkal. Adjuk meg az ingajáratok minimális számát! (Ingajárat: két város közti összeköttetés)
Feladat: 18.25. {k_i_graf_vt_haft_060526_20}
Hét csillagász ül a saját bolygóján. Mindegyikük távcsővel figyeli
a hozzá legközelebbi csillagász bolygóját. Van-e mindig olyan
csillagász, akinek a bolygóját egyikük se figyeli?
Feladat: 18.26. {k_i_100818SL01}
Egy hat vívó körmérkőzést játszik. Igazoljuk, hogy bármely pillanatban igaz, hogy vagy van három köztük, akik közül egyik sem játszott a másikkal, vagy van három köztük, aki közül mindegyik játszott mindegyikkel. (Vö. Kürschák 195?)