TOVÁBBI FELADATOK A II. FEJEZETHEZ

A feladatok megoldása a „feladat” szóra kattintással érhető el. Ahol a feladatnak a), b), stb. része van, ott e betűkre kell kattintani. A megoldásoknál a feladat szövege az első szóra kattintva érhető el.

21. feladat: Maximálisan hány éle lehet egy n pontú, nem összefüggő gráfnak?

22. feladat: Mutassuk meg, hogy ha egy összefüggő gráf bármely köréből elhagyunk egy élt, akkor összefüggő marad.

23. feladat: Mutassuk meg, hogy ha egy n pontú gráfban n él van és összefüggő, akkor pontosan egy kör van benne.

24. feladat: Bizonyítsuk be, hogy egy n pontú körmentes gráfban van legalább n/2 független pont.

25. feladat: Bizonyítsuk be, hogy egy fában bármely két út közös része vagy üres, vagy egy út.

26. feladat: Bizonyítsuk be, hogy egy összefüggő gráf bármely két leghosszabb útjának van közös pontja.

27. feladat: Bizonyítsuk be, hogy egy fa összes leghosszabb útja átmegy egy ponton.

28. feladat: Egy fa bármely két x,y pontjának d(x,y) távolsága a köztük futó egyetlen út hossza. Melyik n pontú fára lesz a d(x,y)-k összege minimális?

29. feladat: Bizonyítsuk be, hogy egy gráf pontosan akkor 2-átmérőjű, ha
a) bármely két nem-szomszédos pontjának van közös szomszédja;
b) bármely pontjára igaz, hogy az x gyökerű szélességi faváz magassága legfeljebb kettő és van olyan x, amelyre pontosan kettő.

30. feladat: Ha egy tíz pontú gráfban minden pont foka legalább öt, akkor összefüggő. Írhatunk-e öt helyett kisebb számot is ebben az állításban? Igaz-e, hogy az ilyen gráf 2-átmérőjű?
Mit mondhatunk általában 2n pontú gráfra? Vagyis: melyik az a legkisebb k, amelyre igaz a következő: ha egy 2n pontú gráfban minden pont foka legalább k, akkor összefüggő? És melyik a legkisebb k, amely esetén az átmérője biztosan 2?

31. feladat: Adott n pont a síkon, semelyik kettő távolsága nem egyenlő. Definiáljuk e ponthalmaz távolsággráfját a következőképpen: Minden pontot összekötünk a hozzá legközelebbivel. Bizonyítandó, hogy az így kapott gráf
a) minden pontja legfeljebb ötödfokú;
b) körmentes;
c) tartalmaz üres n/2-est;
d) élszáma legalább  n/2  és legfeljebb  n–1;
Igaz-e ugyanez, ha minden pontot a tőle legtávolabbival kötünk össze?

32. feladat: Mutassuk meg, hogy egy gráf pontosan akkor nem összefüggő, ha pontjai két nem üres osztályba sorolhatók úgy, hogy a két osztály között nem fut él.

33. feladat: Mutassuk meg, hogy egy gráf és a komplementere közül legalább az egyik összefüggő. Hogyan élesíthető az állítás?

34. feladat: Bizonyítsuk be, hogy egy összefüggő gráf bármely körmentes részgráfja kiegészíthető a gráf favázává.

35. feladat: Anna és Béla a következő gráfjátékot játssza n ponton: felváltva húznak be éleket, és az veszít, aki kört zár be. Kinek van nyerő stratégiája?

36. feladat: Egy teniszverseny n résztvevője között egyértelmű erősorrend van: ha a megveri b-t és b megveri c-t, akkor a megveri c-t. Hány mérkőzéssel lehet megtudni, hogy ki a legerősebb játékos közöttük?

37. feladat: Az előző versenyen most ki szeretnénk választani a második legerősebbet is. Bizonyítsuk be, hogy ehhez n versenyző esetén n+élog₂nù–2 mérkőzés elég.

38. feladat: Most a legerősebbet és a leggyengébbet is szeretnénk megtalálni. Bizonyítsuk be, hogy ehhez elegendő 3n–2 mérkőzés.

39. feladat: a) Bizonyítsuk be, hogy ha egy körmentes gráfban van él, akkor legalább két elsőfokú pontja van.
b) Egy körmentes összefüggő gráfban pontosan két elsőfokú pont van. Mit mondhatunk a többi pont fokszámáról?
Ld. még: 41. feladat, 42. feladat

40. feladat: Egy n pontú gráfban nincs páratlan kör. Legfeljebb hány éle lehet?

41. feladat: Egy konvex szabályos n-szöget n–3 (páronként nem metsző) átlójával háromszögekre bontottunk. Bizonyítsuk be, hogy ha n legalább öt, akkor legalább két legrövidebb átlót használtunk.

42. feladat: Adottak a  d₁, d₂, ..., d_n  pozitív egészek. Bizonyítsuk be, hogy pontosan akkor van olyan  n  pontú fa, amelynek pontjai rendre  d₁, d₂, ..., d_n  fokúak, ha  åd_i = 2n–2. (OKTV)

43. feladat: Egy háromszög alapú hasáb minden csúcsára egy-egy valós számot írtunk. Minden csúcson a vele szomszédos csúcsokon álló számok átlaga áll. Hány különböző szám szerepelhet a csúcsokon?

44. feladat: Mi a helyzet, ha hasáb helyett kockára kérdezzük ugyanazt, amit az előző feladat kérdez? És ha szabályos n oldalú hasábra? Milyen általános állítás mondható ki?

45. feladat: Adott n³5 egész szám. Minden lehetséges módon számpárokat képeztünk belőlük, s vettük minden számpárban a számok összegét. Az így kapott (n²–n)/2 összeg közül legalább  (n²–3n+4)/2 racionális. Bizonyítandó, hogy akkor az összes racionális. Következik-e a feltételből az is, hogy minden megadott szám is racionális?

46. feladat*: Egy nxn-es négyzetrácson Első és Második a következő játékot játsszák: kezdetben minden él színtelen. Felváltva választanak egy még ki nem színezett élt és kékre színezik. (Élnek az olyan szakaszokat nevezzük, amelyek – legalább – egy kis négyzetet határolnak.) Az nyer, akinek először sikerül kört bezárnia. Kinek van nyerő stratégiája? És mi a helyzet akkor, ha az veszít, aki először zár be kört? (Kvant)

47. feladat: Egy országban bizonyos repülőterek között oda-vissza járatok közlekednek. Tudjuk a következőket: minden repülőtérről legfeljebb öt járat indul. Minden repülőtérről el lehet jutni minden másikra legfeljebb három átszállással. Maximálisan hány repülőtér lehet az országban?

48. feladat: a) Igaz-e, hogy ha egy összefüggő gráfban minden út legfeljebb 2k hosszú, akkor van olyan pontja, amelytől minden pont legfeljebb k távolságra van?
b) Igaz-e, hogy ha egy összefüggő gráfban minden út legfeljebb 2k hosszú, akkor bármely két pont távolsága legfeljebb k (vagyis az átmérője legfeljebb k)?

49. feladat: a) Legalább hány éle van egy n pontú 2-átmérőjű gráfnak?
b) Igaz-e, hogy ha egy 2-átmérőjű gráfban van elsőfokú pont, annak szomszédja telített pont?
c) Melyek azok a 2-átmérőjű gráfok, amelyekben nincs telített pont és három, négy vagy öt pontjuk van?
d) A páros gráfok közül melyeknek kettő az átmérője?
e) A körök közül melyeknek kettő az átmérője?
f)* Egy n pontú 2-átmérőjű gráfban nincs telített pont. Bizonyítsuk be, hogy legalább (3n–5)/2 éle van.
g)* Van-e olyan n pontú 2-átmérőjű, telített pont nélküli gráf, amelynek 2n–5 éle van?
h)* Egy n pontú, 2-átmérőjű gráfban nincs telített pont. Minimálisan hány éle van?

50. feladat*: Legyen G egy összefüggő n pontú gráf, amelynek legalább n éle van. Bizonyítsuk be, hogy van olyan f függvény, amely a gráf pontjain van értelmezve, értékkészlete a gráf élhalmazának része és minden x ponthoz egy olyan élt rendel, amelynek egyik végpontja éppen x.

51. feladat*: a) Legyen X egy n elemű halmaz és legyenek F₁, F₂, …, F_n az X különböző részhalmazai. Bizonyítsuk be, hogy van olyan eleme X-nek, amelyet elhagyva minden F_i-ből továbbra is n különböző halmazt kapunk.
b) Egy n x n-es táblázat minden mezőjében egy betű áll. A táblázat bármely két sora különböző. Bizonyítsuk be, hogy a táblázatban van olyan oszlop, amelyet elhagyva a megmaradó táblázatnak nincs két egyező sora. (Kürschák-verseny 1979)

52. feladat: Egy n csúcsú összefüggő gráf minden élére egy valós számot írtunk, ezt nevezzük az él értékének. A gráf bármely útjának a súlya legyen a benne előforduló legnagyobb értékű él értéke. A gráf bármely x,y csúcsára jelölje f(x,y) az x-ből y-ba vezető legkisebb súlyú út súlyát. Bizonyítsuk be, hogy az f függvény legfeljebb n–1 különböző értéket vesz fel. (KöMaL F. 3209)

53. feladat*: Legyen a G összefüggő gráf élszáma k. Bizonyítsuk be, hogy az élei megszámozhatók az 1, 2, 3, ..., k számokkal úgy, hogy minden olyan csúcs esetén, amelyből legalább két él indul ki, az illető csúcsból kiinduló összes élhez rendelt számok legnagyobb közös osztója egy. (NMDO 1991)

54. feladat**: Legalább hány részre kell a tortát vágnunk, ha biztosítani akarjuk, hogy akár p, akár q vendégünk érkezik, mindkét esetben tudunk a vendégeknek egyenlő részeket adni, A) ha (p,q)=1; B) ha (p,q)=d. (Olimpiai válogató)

55. feladat: Mutassuk meg, hogy ha egy e élű, n pontú összefüggő gráfban e£n, és a gráf nem kör, akkor van elsőfokú pontja.

56. feladat**: Legyen G egy e élű, összefüggő, n pontú gráf. Hány olyan feszítő részgráfja van, amelyben minden pont foka páros?

57. feladat*: a) Az I. fejezet 16. feladatában beláttuk, hogy ha egy 3n tagú társaságban bármely két embernek van közös ismerőse, akkor van közöttük n ember, aki együtt az összes többit ismeri, sőt van n+1 ember, aki együtt mindenkit ismer. Mi a helyzet akkor, ha a feltételt némileg gyengítjük és csak annyit feltételezünk, hogy a társaság ismeretség-gráfja 2-átmérőjű, azaz csak annyit feltételezünk, hogy bármely két egymást nem ismerő embernek van közös ismerőse?
b) Az I. fejezet 26. feladatában élesítettük a 16. feladat állítását és bebizonyítottuk, hogy n embernél lényegesen kevesebb is van, akik együtt a társaság minden tagját ismerik. Mi a helyzet, ha a társaság ismeretség-gráfjáról csak annyit követelünk meg, hogy 2-átmérőjű?

58. feladat**: Adott egy n pontú fa, n>2. Minimális számú új él behúzásával el akarjuk érni, hogy minden pont benne legyen egy körbe. Adjunk eljárást erre! Hány élt kell behúznunk? (Egy 2003-as számítástechnikai versenyfeladat alapján)

59. feladat: Van-e olyan összefüggő gráf, amelynek minden pontja elvágó pont?