Az otthoni gondolkodnivaló megbeszélése.
1.feladat:
G egyszerû gráfban minden csúcs foka legalább
d. Bizonyítsuk be, hogy van benne legalább d hosszú
út.
2. feladat:
Egy kertben 40 fa van 5-ször 8-as négyzethálóban
rendezve. Az elsõ sor fa elsõ fáján egy madára
ül. Ez a madár
Definíció: Irányított gráf és irányított út.
Definíció: Irányított értelemben vett (erõsen) összefüggõség.
3. feladat: G irányított gráf akkor és csak akkor erõsen összefüggõ, ha pontjai nem osztahatók fel két nem üres osztályba úgy, hogy a két osztály között haladó élek mind egyirányúak legyenek (ne legyen A-ból B-be tartó él vagy ne legyen B-bõl A-ba tartó él).
Defíníció: Tournament, a teljes gráf irányítása, azaz minden pontpár között pontosan egy irányított él halad.
4.feladat:
Bizonyítsuk be, hogy minden tournamentben van olyan út,
amely az összes csúcson áthalad.
Defíníció: Egy tournamentben egy csúcs (abszolút) gyõztes, ha minden rá illeszkedõ él kifelé halad belõle. Egy tournamentben egy csúcs pszeudo-gyõztes, ha minden más csúcshoz vezet belõle 2 vagy 2 hosszú irányított út.
5. feladat:
(i) Bizonyítsuk be, hogy ha van gyõztes egy tournamentben,
akkor pontosan egy van.
(ii) Bizonyítsuk be, hogy elõfordulhat, hogy nincs gyõztes
egy tournamentben.
(iii) Bizonyítsuk be, hogy elõfordulhat, hogy két
pszeudo-gyõztes is van egy tournmentben.
(iv) Bizonyítsuk be, hogy minden tournamentben van pszeudo-gyõztes.
6. feladat:
Bizonyítsuk be, hogy egy tournement akkor és csak akkor
erõsen összefüggõ, ha van benne olyan kör,
amley az összes csúcson áthalad.
Otthoni gondolkodnivaló: Mondhatunk-e többet a pszeudo-gyõztesek számáról. Bizotos van-e kettõ pszeudo-gyõztes egy (elég nagy) tournementben?
Zh: 55 perces dolgozat, elõreláthatólag négy feladattal az alábbi témákból.
Zh anyag: