Hf. 1: Egyszerű páros gráf fokszámsorozata.
Hf. 2: Tournament ki-fokszámsorozata.
Hf. 3: Ha egy G irányított gráfban a leghosszabb út m, akkor kiszínezhető
m+1 színnel.
Hf. 4: G irányított, és minden irányítatlan C körére megy
mindkét irányban legalább |C|/k él. Ekkor G k-színezhető (ha k>1).
Hf. 5: Ha mindenki 4 másikat ismer, akkor le lehet őket ültetni
néhány kerek asztalhoz, hogy mindenki ismerje a szomszédait. (1 asztalhoz
legalább 3 ember.)
Hf. 6: G irányított, van egy legalább 3 kifokú csúcsa. Ekkor az
Euler-séták száma páros.
Hf. 7: G öf, sík, Euler. Lerajzolható a ceruza felemelése nélkül, hogy
eddigi vonalat nem keresztezünk (csúcsban sem!).
Hf. 8: A Froebenius tétel és az irányítós lemma ekvivalenciája.
Euler tétel és variációi (körökre, sétákra bontás stb.).
G eöf, irányított, Euler (azaz minden csúcs kifoka=befoka).
T egy s gyökerű feszítő be-fenyő.
Algoritmus: elindulunk s-ből, minden csúcsból egy tetsz. olyan élen megyünk
tovább, amelyen még nem jártunk, egyetlen további szabállyal: v-ből csak akkor
mehetünk a fenyő-élen, ha más minden más v-ből induló élen jártunk. Így pont
egy Euler-sétát járunk be.
Kőnig élszínezős tétele.
Hf. 9:Definiáljuk a G(k,n) gráfokat: csúcsai a k hosszú vektorok,
melyeknek
minden koordinátája egész 1-től n-ig.
Az (a1,a2,...,ak) csúcsból irányított él megy
minden b-re a
(a2,...,ak,b) csúcsba.
i) Ekkor G(k,n) Euler.
ii) Ekkor G(k,n) Hamilton.
Hf. 10: G irányított. Ekkor az Euler séták száma osztható
a (delta(v)-1)! számok szorzatával.
Hf. 11: G 3-reguláris.
Akkor és csak akkor van ,,jó'' irányítása, ha páros.
Jó irányítás: minden befok maximum 2, és két szomszédos csúcs befoka
mindig különböző.
Hf. 12: a) Egy nxn-es latin négyzet felső k sora jól ki van töltve
(azaz semelyik szám nem szerepel kétszer se egy sorban, se egy oszlopban).
Ekkor ez befejezhető.
b) Most a bal felső kxl-es téglalap van jól kitöltve.
Ez mikor befejezhető?
c) M nemnegatív egész nxn-es mátrix, minden sorösszeg és oszlopösszeg n.
Ekkor be lehet írni minden (i,j) mezőbe M(i,j) db 1 és n közötti egész számot
úgy, hogy minden sorban is és minden oszlopban is minden szám szerepeljen.
Szorgalmi Hf:
direkt biz. arra, hogy irányított Eulerben x gyökerű befenyők
száma = y gyökerű befenyők száma.
Kőnig élszínezős tétele indukciós bizonyítással.
(Labirintus-bejárás). G öf gráf, elindulunk egy csúcsból és van egy
krétánk. Ha egy csúcsba először jövünk be, rajzolunk az él végére egy
be-nyilat. Ha egy élen kimegyünk, rajzolunk rá egy ki-nyilat. Csak olyan élen
megyünk ki, amelyiken nincs ki-nyíl, és a be-nyíllal jelzetten csak akkor, ha
már nincs más választás.
Ekkor, ha elakadtunk, akkor már G minden élén
jártunk.
T-kötés létezése.
Hf. 13: G élei fel vannak partícionálva az
E1..Ek osztályokra. Ekkor
van G-nek olyan sima irányítása
(sima: mindenhol a kifok max. eggyel tér el a befoktól), amely minden
Gi
gráfon (az Ei-beli élek gráfján) sima irányítást indukál.
Hint: (ha használod, be is kell bizonyítani!
G Euler, minden csúcsban a kimenő élek párokba vannak
osztva. Van olyan Euler irányítás, hogy minden v
csúcsnál minden pár "jól" megy,
azaz egyik v felé, másik nem.
Hf. 14: G öf multigráf n csúcson és m éllel.
Ekkor maximum 2^{m-n+1}-1 kör van benne.
Hf. 15: Mikor lehet egy öf gráf éleire a +1 és -1 számokat írni úgy, hogy
minden csúcsban a kimenő élekre írt számok összegének abszolút értéke
legfeljebb 1 legyen?
Hf. 16: a) A hokiban (sokszor)
a rendes időben megnyert meccsért a győztesnek 3, a
vesztesnek 0 pont jár, míg a hosszabbításban megnyert meccsért a győztesnek 2, a
vesztesnek 1 pont jár. Adott számsorozat mikor lehet egy hoki-körmérkőzés
pont-eredménye?
b) Ulti-körmérkőzés: n versenyző, mind az "n alatt a 3" hármas játszik
egy partit, minden partiban az egyetlen győztes 1 pontot kap.
Mikor lehetnek adott számok egy ulti-körmérkőzés pontszámai?
Hf. 17: Egy G vegyes gráfnak mikor van
Euler irányítása?
OPEN PROBLEM: Mikor lehet d_1...d_n egy foci körmérkőzés végeredménye?
G öf, T\subseteq V. Mikor van G-nek olyan irányítása, melyben egy csúcs befoka pontosan akkor páratlan, ha T-ben van? (T-páratlan irányítás)
OPEN PROBLEM: Adjunk szükséges és elégséges feltételt arra, hogy egy
gráfnak mikor van T-páratlan eöf irányítása?
Fülfelbontások.
Blokkfelbontás.
Hf. 18: G 2 öf, x tetszőleges csúcs.
Ekkor van legalább 2 olyan y szomszédja,
hogy G-x-y öf. (Másképpen: G/xy 2 öf.)
Hf. 19: G 2 él-öf -> létezik erősen öf sima (=közel-Euler) irányítás.
Hf. 20: G 2 öf, s és t csúcsok. Biz. be, hogy meg lehet úgy aciklikusan
irányítani, hogy
minden él rajta legyen irányított s->t úton.
Hf. 21: a)
Ha G 2 él-öf, e és f elvágó élpár, f és g elvágó élpár, akkor e és
g is elvágó élpár.
b) Ha G 2 él-öf, e~f ha e=f, vagy elvágó élpár. Mi jellemzi egy adott e él
ekviv. osztályát?
Hf. 22: G 2 öf, T csúcshalmaz, 0<k<|T|, akkor van V=X\cup Y
partíció, hogy G[X] és G[Y] öf és |X\cap T|=k.
Beadandó feladatok, 1. kör, Határidő: IV. 6. 14 óra 00 perc Minden egyes feladatot külön lapon kell beadni (de beküldve lehet egy pdf-ben, csak minden megoldás új oldalon kezdődjön).
Megjegyzés: ha nincs másként jelölve, egy beadott feladat két házinak megfelelő, azaz 2 pontot ér. Nagyon szép megoldásért és általánosításért plusz pont jár.
Hf-ek megbesz.
Froebenius --> Hall --> Ore.
Gallai identitások.
Tutte tétele, hiány, gát, faktor-kritkus gráfok def.
Def: Egy X gát erős, ha G-X minden páratlan komponense faktor-kritikus.
Hf. 23: G öf. gráf. Mikor van olyan aciklikus irányítás,
amelyben pont 1 forrás és pont 1 nyelő van?
Hf. 24: Biz.be, hogy 2 \nu(G) = n - def(G),
ahol \nu(G) a legnagyobb párosítás mérete.
Hf. 25: X tetsz. csúcshalmaz. Mikor van X-et fedő párosítás?
(Mindkét feladathoz csak a Tutte-tétel használható!)
Hf. 26: G 3-reguláris, 2 él-öf.
Petersen: Ekkor van benne teljes párosítás.
Minden gáthoz létezik őt tartalmazó erős gát.
Tutte igaz q'-vel is, ami a faktor-kritikus komponenseket
számolja.
F faktor-kritikus acsa, ha blokkjai azok.
Faktor-kritikusak páros gráfban, Tutte-ból Froebenius.
Ha B az A erős gátat tartalmazó gát, akkor B-be csak G-A páros
komponensei metszhetnek bele.
Hf. 27: F öf gráf faktor-kritikus acsa, ha üres halmaz az egyetlen
gát.
Hf. 28: G öf. Legyen A az összes erős gát metszete, D a G-A páratlan
komponenseinek uniója, C pedig a G-A páros
komponenseinek uniója.
Bizonyíts be minél többet ezekről a halmazokról.
Hf. 29: G öf 2d-reguláris gráf. Ekkor élhalmaza
partícionálható 2 darab d-regulárisra akkor és csak akkor, ha nd
páros. Valamint élhalmaza mindig partícionálható d darab 2-regulárisra.
Hf. 30: G sík, Hamilton. Ekkor országai
négyszínezhetőek. (Természetesen a négyszíntétel nem használható!)
Hf. 31: G síkgráf, minden ország hatszög (a végtelen is).
Következik-e ebből, hogy G-ben van teljes párosítás?
Beadandók közül 3., 5., 8. (vázlatosan), 9. és 12. megbeszélése.
Maradt beadandó: 4., 6., 7., 10. és 13.
Hf. 32: Ha egy síkbarajzolt gráf külső országa ötszög, az összes többi
háromszög, akkor nem lehet Euler.
Hf. 33: Egyszerű 4-reguláris síkgráfban mikor létezik csúcsoknál
váltakozó kétszínezése az éleknek?
Hf. 34: G sík, erősen öf. ir. gráf. Biz.be, hogy van jobb és bal
irányítású ország.
Hf. 35: A síkon van néhány egyenes úgy, hogy egy ponton csak max 2 megy
át. Egy síkgráf csúcsai a metszéspontok, két ilyen szomszédos, ha van
köztük más csúcsot nem tartalmazó szakasz.
Biz.be, hogy ez a gráf 3-színezhető.
Első körből újra beadható: a 4., 6., 7., 10. és 13.
Újak:
Hf. 36: Egy háromszögelt síkgráf acsa 3-színezhető, ha Euler.
Hf. 37: Milyen n értékekre létezik n csúcsú öszefüggő egyszerű
4-reguláris síkgráf?
Mennyi a kromatikus száma Kn élgráfjának, ennek komplementerének, illetve mennyi a kromatikus száma az ide-oda irányított teljes gráf élgráfjának?