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

Ez az oldal A számítástudomány alapjai 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.

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?