A számítástudomány alapjai - Régi ZH feladatok vegyesen

Ez az oldal A számítástudomány alapjai régi ZH kérdéseit tartalmazza, vegyesen. A többsége emlékezetből lett leírva. Érdemes először a főoldali ZH sorokat megnézni, majd ebből is szemezgetni.

Kombinatorika

• Hány különböző rendszám adható ki, amely három betűből és azt követő három számból áll?
  • Megoldás:

A rendszámtábla a következőképpen kell, hogy kinézzen a feladat szövege alapján (b-betű,sz-szám): b,b,b,sz,sz,sz. Vegyük azt, hogy az ábécében n db. betű van. Az első helyre n darab betű közül választhatunk, a másodikra szintén, ugyanígy a harmadikra is, tehát ez ismétléses variáció. A számok esetében ugyanígy járunk el, itt mind a három helyre 10 számjegy közül választhatunk. Tehát: -- Andris - 2006.09.24.

• Hányféleképpen állítható sorba n (különböző) gyerek?
• Hányféleképpen ültethető kör alakú asztal köré n lovag?
• Hányféleképpen fűzhető fel n különböző színű gyöngy egy láncra?
• Válaszoljuk meg az előző kérdéseket akkor is, ha Jancsi és Juliska, Sir Lancelot és King Arthur, illetve a kék és a fehér gyöngy egymás mellé kell hogy kerüljenek!
  • Megoldás:
  • A gyerekek sorbaállítása : ismétlés nélküli permutáció : n!
  • A kör alakú asztal köré leültetett lovagok közól az első lovag leültetése nem számít, mert ő lesz a viszonyítási alap. => (n-1)! másképp: az asztalhoz elsőként leültetett lovaghoz képest a pozíciók n esetben megegyeznek. n!/n =(n-1)!
  • Gyöngysor ugyan ilyen, feltéve, hogy nincs rajta kapocs.
  • Jancsi és Juliska egymás mellé ül: vegyük őket egy-nek => a sorba állításban együtt szerepelnek => (n-1)! és köztük is kétféle sorrend lehet => (n-1)!*2
  • Sir Lancelot -ék esetében ugyanígy eljárva: (n-2)!*2

-- ZubanGergo - 2006.10.05.

• Hány olyan hatjegyű szám létezik, amelyben van két azonos számjegy? És hány ilyen 15 jegyű szám létezik?
  • Megoldás:
  • Hatjegyű számok összesen: 9*10^5 és ebből le kell vonnunk, melyekben van 2 azonos számjegy: 9*9*8*7*6*5, tehát:

• • 15 jegyű: mindegyikben van két azonos => az összes megfelel a feltételnek:

-- ZubanGergo - 2006.10.05. Hányféleképpen olvasható ki az alábbi ábrából a "SzA Rulez"?

• S Z A R U
• Z A R U L
• A R U L E
• R U L E Z
  • Megoldás:
  • Az összes lehetősége egy út, ahol a bal fölső sarokból indulunk ki, és a jobb alsóba érkezünk. Írjunk le egy lehetőséget, ahol Jobbra és Le lépegetünk:
  • J,J,J,J,L,L,L (4 db. J, 3 db. L). Egy másik lehetséges út:
  • J,J,L,L,L,J,J (4 db. J, 3 db. L).
  • Vegyük észre, hogy J,J,J,J,L,L,L lehetséges út ismétléses permutációi felölelik az összes kiolvasási lehetőséget, hiszen az út végigjárásához négyszer kell jobbra és háromszor kell le mennünk, a lépések minden egyes permutációjával egy lehetséges "kiolvasási-úthoz" jutunk.

-- Andris - 2006.09.24.

• • másképp: vegyük észre, hogy a 7 választásból ki kell választanunk, hogy melyik "lefele lépés" vagy kiválaszthatjuk, hogy melyik "jobbra lépés" /indifferens/. Ismétlés nélküli kombináció:

-- ZubanGergo - 2006.10.05.

• Hány 6-ra végződő hatjegyű szám van?
  • Megoldás:
  • ugyan annyi van, mint öt jegyű szám:

-- ZubanGergo - 2006.10.05. (az eredeti kérdés ötjegyűt írt, de valszeg csak elírás)-- orbit - 2006.10.16.

• Hányféleképpen lehet 8 bástyát felrakni a sakktáblára úgy, hogy azok ne üssék egymást?
  • Megoldás:

8!, hisz mindegyik egy - egy sávot elvesz a táblából -- ZubanGergo - 2006.10.05.

• Hányféleképpen választhatunk ki három 1 és 30 közötti természetes számot úgy, hogy ezek összege páros legyen?
  • Megoldás:
  • 2 eset van: 2 páratlan + 1 páros ; 3 páros
  • 1. : 15 db páratlanból 2 * 15 db párosból 1
  • 2. : 15 db párosból 3

-- ZubanGergo - 2006.10.05. (eredetileg 14 volt beírva, de hát 1től 30ig 30 db szám van...) -- orbit - 2006.10.16.

• Hányféleképpen lehet a 32 magyar kártyából 10-et kivenni úgy, hogy a 4 ász köztük legyen?
  • Megoldás:
  • ha a négy ászt kivettük még maradt 28 lapunk, amiből már csak 6-ot kell kiválasztani:

-- ZubanGergo - 2006.10.05.

• Hányféleképpen lehet eljutni az origóból a (2,3,5) pontba, úgy, hogy csak egységnyi hosszú jobbra, fel és előre lépések lehetségesek?
• Megoldás:
  • a megoldás hasonló az SZA RULEZ feladathoz /feljebb/ , csak 3D -ben: JJFFFHHHHH J=jobbra(x) F=fel(y) H=hátra(z) a fent említett mindkét megoldás célravezet:

-- ZubanGergo - 2006.10.05.

• Hány olyan sorrendje van az 1, 2, … n számoknak, amelyekben a páros és páratlan számok felváltva követik egymást?
  • Megoldás:
  • ha n páros, akkor a páros és páratlan felét (n/2)! féle képp lehet sorba rakni egyenként, tehát:
  • ha n páratlan, akkor a páros számokból eggyel kevesebb van, mint páratlanokból:

-- ZubanGergo - 2006.10.05.

• Hányféleképpen tölthető ki egy lottószelvény? Hány 5, 4 és 3 találatos kitöltés van?
  • Megoldás:
  • lehetséges kitöltések:

-- ZubanGergo - 2006.10.05.

• Egy 12 fős társaságot egy szálloda két háromágyas és három kétágyas szobájában kell elszállásolni. Hány különböző szobabeosztás lehetséges, ha az azonos számú ágyat tartalmazó szobákat nem különböztetjük meg egymástól?
  • Megoldás:
  • A 12 főt sorba állítjuk, az első három főt az első háromágyasba küldjük, a második hármat a második háromágyasba tehetjük, stb.
  • Így 12! szobabeosztást találtunk, de ezek közül nagyon sok azonos megoldásnak számít: érdektelen a két db háromágyas sorrendje (2!), a három darab kétágyas sorrendje (3!), és a szobákon belül az emberek sorrendje ( 3! * 3! * 2! * 2! * 2! -- itt a faktoriálisok egy-egy szobának felelnek meg). Tehát a 12!-t el kell osztani ezekkel a számokkal. A végeredmény:

-- SzaMa - 2006.09.24. ábra: emberek x x x x x x x x x x x x szobán belüli sorrend 3! 3! 2! 2! 2! szobák sorrendje 2! 3! -- ZubanGergo - 2006.10.05.

• Tizenöt vívóból hányféleképpen alkothatunk három (nem feltétlenül diszjunkt) négyfős csapatot?
  • Megoldás:

ha akár ugyanaz a négy fő is lehet mind a 3 csapat. -- ZubanGergo - 2006.10.05.

• Hányféleképp osztható ki 100 hallgatónak 57 különböző könyv és 69 egyforma alma, ha egy hallgató akárhány (esetleg 0) könyvet és akárhány (esetleg 0) almát is kaphat?
  • Megoldás:
• Hányféleképp lehet kiosztani 4 ember között egyenlően egy 52 lapos francia-kártya csomag összes lapját, úgy, hogy mindenki kapjon ászt és királyt is?
• Az {1,2,…100} számokat hányféleképpen lehet három 20-elemű, két 15 elemű és egy 10-elemű halmazra szétosztani? (Mindegyik pontosan 1-be kerül bele)
  • Megoldás:

A táborozós modell alapján: -- ZubanGergo - 2006.10.05

Gráfok alapfogalmai, Fák

• Van-e olyan (legalább kétpontú) gráf, melyben minden pont foka különböző?
  • Megoldás:
  • Egyszerű gráfban nincs mivel ott minden él két pont fokszámát növeli. Összetett gráfban lehet, mivel abban lehet hurokél, ill. párhuzamos él.

-- Karacs Gábor - 2006.10.05.

• Van-e olyan egyszerű graf, amelyben a pontok foka rendre
  • 1, 2, 2, 3, 3, 3;
  • 1, 1, 2, 2, 3, 4, 4;
  • 5, 5, 5, 6, 6, 6, 7, 7, 7;
  • 1, 2, 2, 3, 4, 4, 5, 6, 6;
  • 1, 1, 3, 3, 3, 3, 5, 6, 8, 9;
  • 2, 3, 3, 4, 5, 6, 7 ?
• Igazoljuk, hogy tetszőleges gráfban a páratlan fokú pontok száma páros.
• Milyen komponensekből állhat egy gráf, ha minden pontjának a foka legfeljebb 2?
• Bizonyítsuk be, hogy minden fában van olyan pont, amit az összes leghosszabb út tartalmaz.
• Tartalmazhat-e egy Kn (n ≥ 4) feszített részgráfként 4 hosszú kört?
• Egy negyedfokú reguláris összefüggő gráfból töröljük egy fa éleit. Bizonyítsuk be, hogy a maradék legalább két kört tartalmaz.
• Legyen v egy egyszerű G gráfban egy olyan pont, melyre d(v)≥2. Bizonyítsd be, hogy ha a G-v gráf 2-szeresen összefüggő, akkor G is 2-szeresen összefüggő. (A G-v gráf a G gráfból a v pont és az összes v-re illeszkedő él elhagyásával keletkezik.)
• Melyik az a legnagyobb k szám, melyre az alábbi gráf k-szorosan összefüggő?

Gráf

• Hány különböző minimális súlyú feszítőfája van az alábbi, számozott pontú fának?

Gráf

• • Megoldás:

Mindegyik rombuszból féle képpen választhatunk ki minimális súlyú feszítőfát, tehát összesen ${6 \choose 3}*{6 \choose 3}*{6 \choose 3}$ féle minimális súlyú feszítőfája van a gráfnak. -- Karacs Gábor - 2006.10.09.

• Hány különböző olyan fa adható meg a 1,2,..n pontokon úgy, hogy az 1-es pont foka pontosan 2 legyen?
  • Megoldás: A fákat legegyszerűbben a Prüfer-kódjukkal tudjuk leírni, így a feladat megoldásánál is tegyük ezt. Tudjuk, hogy a Prüfer-kód (n-2) hosszú, valamint hogy minden csúcs egyel kevesebbszer szerepel a kódban, mint amennyi a fokszáma. Emiatt az 1-es pont egyszer szerepel a Prüfer kódban.
• Hány olyan n-2 hosszú számsor létezik, amiben pontosan 1db 1-es fordul elő. Előszőr kiválasztjuk, hogy hol legyen az 1-es: ${n-2 \choose 1}$ . Cayley miatt n ponton $n^{n+2}$ különböző fa adható meg, de a miénkben az 1-es csak 1x fordul elő, ezért ez $(n-1)^{n-3}$-ra redukálódik (n-1, mert az 1-est már nem választhatjuk, és n-3, mert már csak n-3 hosszú helyre kell számokat választani), tehát a végeredmény: ${n-2 \choose 1}*(n-1)^{n-3}$

-- Viszkei György - 2007.10.14.

• Rajzolja fel az összes olyan páronként nem izomorf egyszerű, összefüggő 5 pontú gráfot, amelyben pontosan egy kör van és a maximális fokszáma legfeljebb 3.
• Bizonyítsd be, hogy ha egy egyszerű G gráfban minden olyan X (része V(G)-nek) ponthalmazra, melyre |X| ≥ 2 teljesül igaz, hogy az X által feszített részgráfnak legalább |X|/2 éle van, akkor a gráf teljes!

Euler-kör, Hamilton-kör és hasonlók

• Milyen n esetén tartalmaz a teljes n-pontú gráf Euler körsétát illetve sétát?
  • Megoldás:
  • Teljes gráf: olyan egyszerű gráf, melynek tetszőleges két pontja szomszédos.
  • Tétel: egy összefüggő G gráfban akkor és csak akkor van Euler-kör, ha G minden pontjának foka páros.
  • Tétel: egy összefüggő G gráfban akkor és csak akkor van Euler-út, ha G páratlan fokú pontjainak száma 0 vagy 2.
  • Tehát a körhöz minden fokszámnak párosnak kell lenni, vagyis a csúcsok száma páratlan.
  • Az út esetében nem lehet páratlan fokú csúcs, csak páros, mert páratlanból max. 2 lehetne, de mivel ez egy teljes gráf, ezért az összes csúcs vagy páros, vagy páratlan fokszámú. Így az Euler-útra is ugyan azt a feltételt adhatjuk: n legyen páratlan.

-- Viszkei György - 2007.10.14.

• Milyen x és y értékekre tartalmaz Euler körsétát illetve sétát az x × y méretű „kockás” papír, aminek (x + 1) × (y + 1) pontja van?
• Bizonyítsuk be, hogy a Petersen gráfban nincsen Hamilton-kör!
• Legalább hány éle van egy olyan hat pontú gráfnak, melynek van Hamilton-köre?
  • Megoldás:
  • Képzeljünk el egy szabályos hatszöget, ennek csúcsai legyenek a G gráfunk pontjai, oldalai pedig az élek. Könnyen látható, hogy ebben a 6 élű gráfban van Hamilton-kör, és az is triviális, hogy 5 éllel nem tudtunk volna visszajutni a kiindulópontba.

-- Viszkei György - 2007.10.14.

• Bizonyítsuk be, hogy tetszőleges összefüggő gráf élei bejárhatók úgy, hogy minden élen pontosan kétszer megyünk át!
• Képzeljünk el egy képzőművészeti kiállítást. A látogatók szeretik a saját lelkiviláguk szerint élvezni a tárlat anyagát, azaz annyira elmerülnek az esztétikai élmények kavalkádjában, hogy útjelző táblák figyelemmel követésére már nem képesek. Annyi azért persze még tőlük is elvárható, hogy mindig olyan folyosón haladnak tovább, amerre addig még nem jártak és ha egy adott pillanatban látnak ilyen folyosót, akkor azok egyikén tovább is haladnak. Feladat: határozzuk meg, milyen lehet egy ilyen kiállítócsarnok, ha azt szeretnénk, hogy az összes látogató a saját korlátoltsága ellenére végignézhesse a kiállítást!
• Keressünk olyan 8 pontú gráfot, hogy se ő, se a komplementere ne legyen síkba rajzolható!
• Keressük meg az összes 6 csúcsú nem síkgráfot!
• Legyen G=(V,E) az a gráf, melyre V={1,2,…,100}, és a és b pont között pontosan akkor fut él, ha a-b osztható 4-gyel. Van-e G gráfnak Euler körsétája?
  • Megoldás: (Megjegyzés: Fleiner Tamás hivatalos megoldását másoltam be ide, nekem első körben kijött, hogy van benne Euler körséta, és ezt ő a megoldásban is feltüntette, helytelen következtetésként, tehát vigyázni kell.)
  • "Vegyük észre, hogy két pontot akkor köt össze él, ha 4-gyel osztva azonos maradékot adnak, azaz a G gráf 4db 25 méretű teljes gráfból áll: az egyik teljes gráf csúcsai az 1,5,9,...97, a másiké 2,6,10,...98, a harmadiké 3,7,11,...99, a negyediké 4,8,12,...100 számok lesznek. Mivel G nem összefüggő, és minden komponensének van éle, ezért G-nek bizonyosan nincs Euler-köre.

Rossz megoldás: Ha valaki kiszámolja, hogy minden pont foka 24, ami páros, és ebből helytelenül arra következtet, hogy van Euler-kör, kapjon 4 pontot."

• Tétel: egy összefüggő G gráfban akkor és csak akkor van Euler-kör, ha G minden pontjának foka páros. Innentől tehát ezt kell bizonyítanunk.
  • Képzeljük el ezeket a számokat 4-es csoportokként, valahogy így: 1,2,3,4|5,6,7,89,10,11,12 ... 1-től 100-ig 25db 4-gyel osztható szám van, ami 25 csoportnak felel meg(mert minden csoportban csak 1db 4-gyel osztható szám van). Kiindulásként nézzük meg, hogy az 1-es hány számmal van összekötve. Mivel 25db 4-gyel osztható számunk van, ezért minden ennél a 25 számnál 1-gyel nagyobb számmal össze van kötve, ami 25 számot jelentene, de 101-gyel nem lehet összekötve, mert csak 100-ig vannak számaink. Tehát összesen 24 számmal van összekötve, ami páros, tehát idáig jók vagyunk. Vegyük észre, hogy az 1-es mindegyik csoport első számával van összekötve, tehát az össz. 25 csoportunkból a maradék 24 csoport első számával(egyébként az előző okoskodással is pont ezt kaptuk). Vegyük észre továbbá, hogy ez a többi számra is igaz: minden csoport k. eleme össze van kötve a többi csoport k. elemével, így minden csúcsunk fokszáma 24, ami páros, tehát van a gráfban Euler körséta. Mi a hiba? Nem foglalkoztunk kellő körültekintéssel a definícióval, mely szerint a gráfnak összefüggőnek kell lennie. A hivatalos megoldás alapján látható, hogy a gráf több komponensből áll, így nem lehet benne Euler-kör.

-- Viszkei György - 2007.10.14.

• 10 házaspár mindegyik tagjára igaz, hogy a maradék 9 házaspár mindegyikének legalább egyik tagját ismeri. (Az ismeretség kölcsönös.) Bizonyítsuk be, hogy az említett 20 személy leültethető egy 20 személyes, kör alakú asztalhoz úgy, hogy mindenki ismerje a két mellette ülő személy mindegyikét!
  • Megoldás:
  • Képzeljük el a személyeket és kapcsolatokat egy gráfként. A feladat megoldható, ha létezik a gráfban Hamilton-kör. 10 házaspár összesen 20 embert jelent. Mivel mindenki ismer a másik 9 házaspárból valakit és ismeri saját házastársát, ezért összesen 10 személyt ismer. Dirac tétele kimondja, hogy ha G egy egyszerû, legalább 3 pontú gráf, amelynek minden pontjának legalább |V(G)/2 a foka, akkor G tartalmaz Hamilton-kört. Ebben a gráfban az összes feltétel teljesül, tehát bebizonyítottuk, hogy tartalmaz Hamilton-kört, és pont erre volt szükségünk.

-- Viszkei György - 2007.10.10.

• Az alábbi három gráf mindegyikéről döntse el, hogy Van-e benne Hamilton-kör? Teljesül-e rá Ore feltétele?

Gráfok

• • Megoldás:
  • Először nézzük Ore tételét: Ha az n pontú G gráfban minden olyan x,y V(G) pontpárra, amelyre {x,y} E(G) teljesül az is, hogy d(x) + d(y) n, akkor a gráfban van Hamilton-kör.
  • Első gráf: nem lehet benne Hamilton-kör, mert ha elhagyjuk a középső pontot, 2 komponensre esik szét, márpedig van egy tételünk, ami kimondja, hogy ha a G gráfban létezik k olyan pont, amelyeket elhagyva a gráf több, mint k komponensre esik, akkor nem létezik a gráfban Hamilton-kör. Ore feltétele nem teljesül, mert ha teljesülne, lenne benne Hamilton-kör, az előbb pedig bebizonyítottuk, hogy nincs.

-- Viszkei György - 2007.10.10.

• • Második gráf: van benne Hamilton-kör. Bizonyításképp mutatunk egyet. Elindulunk a legbaloldalibb csúcsból és lépünk fel,le,fel,fel,le,fel majd vissza a kiinduló pontba. Ore feltétel nem teljesül, mert bár tudunk mutatni két olyan nem szomszédos csúcsot, amire igaz, hogy d(x) + d(y) n (pl. középső és valamelyik szélső), de nagyon fontos, hogy a feltételnek az összes nem szomszédos pontpárra teljesülnie kell, ez pedig pl. a két felső csúcs esetén már nem igaz, mert fokszámösszegük 6, ami kisebb 7-nél.
  • Harmadik gráf: a második gráf ennek a feszítő részgráfja, E' E, és a másodikban volt Hamilton-kör, akkor ebben is van(mivel a másodikban volt, és ez annyiban különbözik a másodiktól, hogy több él van benne, így még könnyebb találni). Ore feltétel teljesül, mert az összes nem szomszédos csúcsra igaz, hogy fokszámösszegük a csúcsok számánál.

-- Viszkei György - 2007.10.14.

• Legfeljebb hány élt húzhatunk be az ábrán látható gráf irányítatlan változatába az egyszerűség megtartásával úgy, hogy a keletkező gráf síkbarajzolható legyen?

Gráf

• Legyen G egy összefüggő gráf, amiben minden pont foka páros. Igaz-e, hogy ha elhagyjuk G-ből egy körének éleit, akkor a maradékban biztosan van Euler körséta?
• Bizonyítsd be, hogy ha egy legalább két komponensből álló egyszerű n pontú gráfban minden pont foka legalább n/3, akkor a gráfban van egy legalább n/3 hosszú kör!

Dualitás és Pert módszer

• Döntsük el, hogy az alábbi gráf síkba rajzolható-e! Ha igen, rajzoljuk le egyenes szakaszokkal, élkereszteződés nélkül, és adjuk meg a duálisát is! Ha nem, bizonyítsuk!

Gráf

• Határozzuk meg az összes olyan egyszerű, összefüggő 3-reguláris gráfot, mely izomorf a duálisával!
• Egy irányított, (az irányítástól eltekintve) összefüggő, n pontú gráf körmátrixának két sora van. Hány éle van?
• Hány csúcsa lehet annak a fának, amelyben csak kétféle fokszám szerepel, ezek közül az egyik a 4, és a pontoknak pontosan a negyedrésze negyedfokú?
• Legyen G a következő 2n pontú gráf: {v1,…,vn} és {vn+1,…v2n} is egy-egy n hosszú kört alkot. Ezen kívül pedig minden i-re {vi,vi+n} E(G). Igaz-e, hogy G bármely élét elhagyva a maradék gráfban van Hamilton-kör?
• Az alábbi PERT feladatokban határozzuk meg a feladatok elvégzéséhez szükséges összes időt! Mik a kritikus tevékenységek? (x és p paraméterek!)

Gráf1 Gráf2 Gráf3

• Tegyük fel, hogy egy egyszerű G gráf előáll k db egyszerű, síkba rajzolható gráf éldiszjunkt uniójaként. (Azaz az éleit k csoportra lehet osztani úgy, hogy az egy csoportban lévő élek síkba rajzolható gráfot alkossanak.)Bizonyítsd be, hogy ha n a pontok száma, e az élek száma, akkor $k\geq {\frac {e}{3n-6}}$
• Síkba rajzolható-e az alábbi gráf?

Gráf

• Egy egyszerű, hat pontból álló, összefüggő gráfban van 1, 2, 3, 4 és 5 fokú pont is. Mennyi lehet a hatodik pont foka?

Bejárások, Útkeresés

• Egy 15 pontú gráf mélységi bejárása során számozzuk a csúcsokat a bejárási sorrend, azaz mélységi számuk alapján. Közben felírjuk a bejárás befejezési számait is és az alábbi sorrendet kapjuk: 4, 6, 5, 7, 3, 2, 8, 1, 11, 12, 14, 13, 10, 15, 9 Rajzold fel a mélységi gráfot!

• Az egyszeri qpázó meg szeretné látogatni a Szimpatikus Egyetemet (hogy üdvözölhesse őket), ám útja során csak szénsavmentes üdítőital beszerzésére alkalmas helyeken keresztül mehet. Keressük meg a leggyorsabb utat, hogy időben visszaindulhasson a SKEBUra!

Ábra

• • Hogyan oldanád meg a feladatot, ha plusz kitétel, hogy minden vendéglátó-ipari egységben 5 percet tölt a delikvens? Hogyan oldanád meg a feladatot, ha az plusz kitétel, hogy a qpázónak egy vendéglátó-ipari egység meglátogatása (ami tegyük fel 0 percet vesz igénybe) megér annyit, hogy 3 percet késsen a SKEBUról? És ha 5 percet is megér?
• Hány olyan 10 betűből álló (nem feltétlenül értelmes) szó van, amelyben 4 különböző magánhangzó van? (A mássalhangzók lehetnek egyformák is. A magyar abc-ben 14 magánhangzó és 21 mássalhangzó van.)
• Egy n pontú fában jelölje B azon pontok halmazát, amelyek foka legalább 2 (nem levelek). Bizonyítsuk be, hogy $\sum _{v\in B}d(v)=n-2+|B|$
• Legalább hány élet kell elhagyni a K6 gráfból ahhoz, hogy síkba rajzolható gráfot kapjunk?
• Egy 20 tagú társaságban mindenki ugyanannyi embert ismer a többiek közül. Bizonyítsd be, hogy le tudnak ülni egy kör-alakú asztal mellé vagy úgy, hogy mindenki mindkét szomszédját ismeri, vagy úgy, hogy senki se ismeri egyik szomszédját sem!
• Egy egyszerű, síkba-rajzolható gráfban a minimális fokszám 5. Mutasd meg, hogy ekkor legalább 12 darab ötödfokú pont van!
• Rajzoltam egy 10 csúcsú fát, de elveszítettem. Rajzold le a duálisát!
• Bizonyítsd be, hogy tetszőleges két n csúcsú fa gyengén izomorf!
• Hány olyan fa van az 1-től 15-ig címkézett pontokon, melyben az 1-es számú csúcs foka 7?
• Egy vállalat szeretné megjutalmazni 20 dolgozóját. Van 8 jegye egy világkörüli hajóútra, 7 jegye a foci VB-re és 5 jegye az állatkertbe. Hányféleképpen oszthatja ki ezeket?

-- SzaMa - 2006.10.10.