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.

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 [math]{6 \choose 3}*{6 \choose 3}*{6 \choose 3}[/math] 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: [math]{n-2 \choose 1}[/math] . Cayley miatt n ponton [math]n^{n+2}[/math] különböző fa adható meg, de a miénkben az 1-es csak 1x fordul elő, ezért ez [math](n-1)^{n-3}[/math]-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: [math]{n-2 \choose 1}*(n-1)^{n-3}[/math]

-- 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 [math]k\ge\frac{e}{3n-6}[/math]
• 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?