Hf1: Egyszerű páros gráf fokszámsorozata.
Hf2: Tournament ki-fokszámsorozata.
Hf3: Ha egy G irányított gráfban a leghosszabb út m, akkor kiszínezhető
m+1 színnel.
Hf4: 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ő.
Hf5: 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.)
Hf6: G irányított, van egy legalább 3 kifokú csúcsa. Ekkor az
Euler-séták száma páros.
Hf7: G öf, sík, Euler. Lerajzolható a ceruza felemelése nélkül, hogy
eddigi vonalat nem keresztezünk (csúcsban sem!).
Hf8: A Froebenius tétel és az irányítós lemma ekvivalenciája.
Hf9: G irányított. Ekkor az Euler séták száma osztható
a (delta(v)-1)! számok szorzatával.
Hf10: Ha mindenki 5 másikat ismer, akkor akárhogy osztjuk őket két
egyforma csapatra, az egyik csapatban ugyanannyi ismeretség lesz, mint a
másikban.
Hf11: 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ő.
Hf12: 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.
Hf13: 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.
Beadandó feladatok, 1. kör, Határidő: IV. 6. 12 óra 15 perc Minden egyes feladatot külön lapon kell beadni!
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.
Beadandó 1: a) adott G páros gráf és minden csúcsnál az élek
preferencia-sorrendje. Egy él súlya: 1 + alul hányan előzik meg +
felül hányan előzik meg. Ekkor ha minden élre akkora színlista van írva,
mint a súlya, akkor van olyan jó élszínezés, ahol minden él a listájából kap
színt.
b) G páros, minden élre egy maxfok méretű színlista van írva.
Ekkor létezik jó lista-élszínezés.
Beadandó 2: G 2-öf, nem páros. Bármely x,y csúcsokra létezik x-ből y-ba páros hosszú út.
Beadandó 3: G öf. egyszerű.
a) Van V=X\cup Y partíció, hogy mind G[X]-ben, mind
G[Y]-ban minden fok páros.
b) Van V=X\cup Y partíció, hogy G[X]-ben minden fok páratlan,
G[Y]-ban minden fok páros.
c) G csúcsaiban 1-1 lámpa és nyomógomb van. Ha egy x-beli gombot megnyomunk,
akkor mind az x-beli, mind a szomszédaiban levő lámpák állapotot váltanak.
Kezdetben egyik lámpa sem ég. Bizonyítsd be, hogy néhány gomb megnyomásával
elérhető, hogy minden lámpa égjen.
Beadandó 4: a) Egy G elemi páros gráfnak van a következő
tulajdonságú fülfelbontása:
a kezdőkör páros;
és minden fül páratlan hosszú, különböző színosztálybelieket köt össze.
b) Az ilyen fülfelbontással rendelkező gráfok tényleg elemiek.
(Elemi: összefüggő legalább 3 csúcson, és
minden éle benne van teljes párosításban.)
Beadandó 6 (4 pontos): G irányított, az r csúcs kifoka nagyobb, mint a befoka. Bizonyítsuk be, hogy ekkor van a gráfban egy x csúcs, melynek befoka nagyobb, mint a kifoka, és az r-ből x-be vezető éldiszjunkt utak max száma szigorúan nagyobb, mint az x-ből r-be vezető éldiszjunkt utak max száma.
Beadandó 8 (4 pontos):
0 ≤ d1 ≤ ... ≤ dn
mikor lehet egy egyszerű gráf foksorozata?
Állítás: ha \sum di páros és minden 1 ≤ k ≤ n-1 esetén
\sumi=n-k+1n di ≤ k(k-1) +
\sumi=1n-k min(di,k).
Segítség: mikor van olyan egyszerű irányított gráf, melyben minden i-re a
vi csúcs befoka is és kifoka is di?
Beadandó 9: Ha G 2-öf és van benne teljes párosítás, akkor van
teljesen fedett csúcsa (azaz olyan, hogy az összes rá illeszkedő él
benne van egy-egy teljes párosításban).
Segítség: először lássuk be, hogy van G-ben két különböző teljes párosítás!
Beadandó 10: G öf. a) Mikor van G-ben csillag-faktor?
b) Mikor van G-ben út-faktor?
c) Mikor van G-ben legfeljebb k-ágú csillag-faktor (k>1 esetén)?
(Ahol pl. a legfeljebb k-ágú csillag-faktor olyan feszítő részgráf, amelynek
minden komponense K1,t valamilyen 1 ≤ t ≤ k -ra).
Beadandó 11: Egy öf G gráfban acsa van n értékű
(nem egyszerű) 2-matching, ha minden I
független csúcshalmazra |\Gamma(I)| ≥ |I|.
(2-matching: olyan 0-1-2 értékű függvény az éleken, hogy bármely
csúcsra igaz, hogy a belőle kimenő éleken az összeg legfeljebb 2.
A 2-matching értéke az élekre írt számok összege.)
Beadandó 12: Adjunk minél szebb jó karakterizációt a párosan szimmetrikus
irányított gráfokra!
(G párosan szimmetrikus, ha minden olyan uv éléhez, amely benne van páratlan
körben, szükségképpen vu is éle G-nek.)
Beadandó 13: a) Egy legalább két csúcsú
F faktor-kritikus gráfnak van a következő fülfelbontása:
F0, F1, .., Ft=F; &bbsp;
F0 egy szép kör, Fi+1-et úgy kapjuk Fi-ből,
hogy egy
nyílt vagy zárt páratlan hosszú fület ráragasztunk; továbbá minden
Fi
szép (F-ben) és faktor-kritikus.
(F egy H részgráfja szép, ha az F-V(H) gráfnak van teljes párosítása.)
b) Ha F még 2-öf is, akkor van a fenti fülfelbontás csupa nyílt füllel is.
Beadandó 14: Legyen G páros gráf. Egy I független csúcshalmaz hiánya
def(I)=|I|-|\Gamma(I)|. Egy I független csúcshalmaz szoros, ha hiánya
maximális (a függetlenek között).
Bizonyítsuk be, hogy szorosak metszete szoros.
Beadandó 15 (4 pontos): Erős gátak metszete erős gát.
(Egy X gát erős, ha G-X minden páratlan komponense faktor-kritikus.)
Beadandók közül 4,9,10,11. megbesz.
Maradt beadandó: 6,12,13,15.
Gallai identitások.
Tutte igaz q'-vel is, ami a faktor-kritikus komponenseket
számolja.
Nem beadandó HF:
F öf gráf faktor-kritikus acsa, ha üres halmaz az egyetlen gát.
Nem beadandó HF: F faktor-kritikus acsa, ha blokkjai azok.
Hf21: 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?
Hf22: 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.
Hf23: G öf. gráf. Mikor van olyan aciklikus irányítás,
amelyben pont 1 forrás és pont 1 nyelő van?
Ha B az A erős gátat tartalmazó gát, akkor B-be csak G-A páros komponensei metszhetnek bele.
Gallai-Edmonds struktúra.
Síkgráfok, dualitás, feszítőfák kapcsolata duális fesz.fáival,
Euler-formula.
Hf24 a) Biz.be, hogy 2 \nu(G) = n - def(G),
ahol \nu(G) a legnagyobb párosítás mérete.
24 b) X tetsz. csúcshalmaz. Mikor van X-et fedő párosítás?
(Mindkét részhez csak a Tutte-tétel használható!)
Első körből újra beadható: 6,12,13,15.
Újak:
Beadandó 5: a) Egy 3-reguláris 2 összefüggő gráfban mindig van
háromszögmentes 2-faktor.
b) Egy 3-reguláris 3 összefüggő gráfban mindig van olyan 2-faktor, amely
minden 3 elemű vágásból tartalmaz élet.
c) Egy 3-reguláris 3 összefüggő gráfban mindig van olyan háromszögmentes
2-faktor, amely minden 3 élű vágásból tartalmaz élet.
Beadandó 7: Egy multigráf kromatikus indexe mindig legfeljebb [(3/2)\Delta], ahol \Delta a max fok. Mutassunk minden \Delta-ra példát, hogy ez éles. (A bizonyításhoz az általánosított Vizing-tétel nem használható).
Beadandó 16: Egy hurokmentes síkgráf mindig 5-listaszínezhető.
Hint: Legyen C az óceánpart, u,v ennek két szomszédos pontja.
Ha minden nem óceánparti csúcsra 5 hosszú lista, u-re és v-re különböző
1 hosszú listák, a többi óceánparti csúcsra 3 hosszú lista van írva,
akkor a síkgráf lista-színezhető.
Beadandó 17: a) G egyszerű öf., páros sok éllel.
Ekkor az élhalmaza partícionálható
cseresznyékre (2 hosszú utakra).
b) G egyszerű 2-öf 3-reg. Ekkor az élhalmaza partícionálható
3 hosszú utakra.
Beadandó 18: col(G):= 1 + min { k : létezik olyan csúcssorrend, hogy
mindenkiből max k él megy nagyobb sorszámúhoz }
elf(G):= maxH\subseteq V minv\in H
degG[H](v), azaz maximalizáljuk a
H által feszített részgráf minfokát.
Biz. be, hogy: a) col(G)=elf(G)+1
b) \chi(G) ≤ col(G)
c) col(G)+col(\overline G) ≤ n+1
d) Ha A, B, C páronként éldiszjunkt gráfok az n elemű V-n, akkor
col(A)+col(B)+col(C) ≤ \lfloor 3/2 * (n+1) \rfloor, és ez minden n-re éles.
Beadandó 19 (4 pontos): G-ben akkor és csak akkor van 2-faktor, ha
qY(G-X-Y) + d(X,Y) ≤ 2|X| + \sumy\in Y (d(y)-2)
teljesül minden diszjunkt X,Y csúcshalmazra, ahol
qY(G-X-Y) a
G-X-Y gráf olyan komponenseinek számát jelöli, melyekből páratlan
sok él megy Y-ba.
Beadandó 20 (3 pontos):
Egy G öf gráfra tekintsük az alábbi tulajdonságokat:
1) Fametszet gráf, azaz van egy olyan T fa és a csúcsoknak
megfeleltethetünk
T részfáit úgy, hogy két csúcs acsa szomszédos, ha a nekik megfeleltetett
részfák metszők.
2) Létezik a csúcsoknak olyan sorrendje, hogy minden csúcsra az ő nagyobb
sorszámú szomszédai klikket feszítenek.
3) Minden legalább 4 hosszú körben van húr.
a) Bizonyítsuk be, hogy 1)==> 2)==> 3)==> 1 (minden implikációt
közvetlenül).
b) Minden ilyen gráfra, és a komplementerükre is, \chi(G)=\omega(G).
(Perfekt gráf tételek nélkül!)
Beadandó 21 (4 pontos): a) Mikor van egy gráfban feszített
csillag-faktor, azaz egy olyan részgráf, amely feszítő, és
minden komponense csillag (a K2
is csillag) és feszített részgráf.
b) Mikor van egy gráfban feszített legfeljebb
k-ágú csillag-faktor?
Ötszíntétel (két bizonyítással).
Hibakeresés négyszíntételre adott rossz bizonyításban.
Hf25: Egyszerű 4-reguláris síkgráfban mikor létezik csúcsoknál váltakozó
kétszínezése az éleknek?
Hf26: G sík, Hamilton. Ekkor országai négyszínezhetőek.
Hf27: G síkgráf, minden ország hatszög (a végtelen is).
Következik-e, hogy G-ben van teljes párosítás?
G 3-reguláris 2-öf sík. Lapjai négyszínezhetőek acsa, ha élei 3-színezhetők
(Tait, 1880).
Ha egy 2 élöf síkgráf lapjai mindig négyszínezhetők (ez a négyszíntétel),
akkor a lapok és a csúcsok egyszerre is (szomsz. csúcsok lehetnek azonos
színűek, de illeszkedő csúcs-lap pár nem).
Egy háromszögelt síkgráf acsa 3-színezhető, ha Euler.
G 3-reg 2-öf síkgráf. Lapjai 4-színezhetőek acsa, ha csúcsaira lehet +-1 -eket
írni, hogy minden lapon az összeg osztható 3-mal.
G egyszerű sík. Pontjait ki lehet színezni két színnel úgy, hogy ne legyen
egyszínű lap.
Hf28: G sík, erősen öf. ir. gráf. Biz.be, hogy van jobb és bal irányítású
ország.
Hf29: Milyen n értékekre létezik n csúcsú öszefüggő egyszerű
4-reguláris síkgráf?
Hf30: 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 3-színezhető.