Gráfgyakorlat

Gyakorlat IV-ed és V-öd éves matematikus és alkalmazott matematikus hallgatóknak

2018 Tavasz

Gyakvezető: Király Zoltán

Péntek 12:15-13:45, Déli 3.607


Csak a hallgatóimnak / Only for my students


Hirdetmények


1. óra (II. 16.)

Fa, multigráf, hurokmentes multigráf, hurokmentes összefüggő multigráf, páros multigráf, összefüggő páros multigráf fokszámsorozata.
Havel-Hakimi algoritmus jósága.
Irányított gráfban minden (irányított) kör páros. Következik-e ebből, ekkor két színnel színezhető? És ha erősen összefüggő?
Pontos potenciál létezése.

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ő.


2. óra (II. 23.)

Hf-ek megbesz.
Egyszerű irányítós lemma biz. Mikor létezik előírt befokú eöf irányítás?
G k-színezhető <=> van olyan aciklikus irányítása, hogy a leghosszabb út legfeljebb k-1 hosszú.
Mikor lehet a G eöf ir. gráf csúcsait két színnel kiszínezni úgy, hogy minden csúcsból menjen él ellentétes színűbe?
Euler tétel variációi.

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.


3. óra (III. 2.)

Hf-ek megbesz.
G eöf. irányított, 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.
(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.
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.
Froebenius --> Hall --> Ore
Kőnig élszínezős tétele.

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.


4. óra (III. 9.)

Hf-ek megbesz.
Dulmage-Mendelsohn.
Szorgalmi Hf: direkt biz. arra, hogy irányított Eulerben x gyökerű befenyők száma = y gyökerű befenyők száma.
T-kötés létezése.
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?
Szorgalmi Hf: G egyszerű, színezett-Euler. Egy max alternáló körséta-felbontásban (lehető legtöbb körséta) minden körséta legfeljebb (3/2)(n-1) hosszú.
Hint: Színezett Euler, max felbontásban minden alt. körsétán van egyedüli csúcs.
Fülfelbontások I. (2-élöf, eöf, 2-öf).
Hf14: G öf. multigráf n csúcson és m éllel. Ekkor maximum 2^{m-n+1}-1 kör van benne.
Hf15: 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?
Hf16: 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?
Hf17: Egy G vegyes gráfnak mikor van Euler irányítása?
Hf18: 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.)

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.)


5. óra (III. 23.

Hf-ek megbeszélése.
Meggondolandó: Irányítós lemma hipergráfokra.
2 öf blokkokra bontás.
Tutte tétele, gát, faktor-kritkus gráfok, erős gát def.
Gale-Shapley-tétel kimondva.
Nem beadandó HF: Gale-Shapley bizonyítása indukcióval.

Hf19: G 2 él-öf -> létezik erősen öf. sima (=közel-Euler) irányítás.
Hf20: 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.


6. óra (IV. 6.)

Hf-ek megbesz.

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?


7. óra (IV. 13.)

Hf-ek megbesz.
Faktor-kritikusak páros gráfban, Tutte-ból Froebenius.
Petersen 3-reguláris tétele.
Petersen 2k reguláris tétele.

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ó!)


Beadandó 2. kör. Határidő: Május 9. 14 óra 00 perc. Minden egyes feladatot külön lapon kell beadni!

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?


8. óra (IV. 20.)

Euler következményei.
Egy síkgráf országai mikor kétszínezhetőek?
4-reguláris síkgráf csúcsoknál váltakozó irányítása.
Háromszögelt ötszög nem lehet Euler.
Sperner-lemma, háromszögelt négyzet. (V=V1\cup V2,  a1,a3\in V1,  a2,a4\in V2. Ekkor valamelyik i-re G[Vi]-ben van ai --> ai+2 út.)

Ö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?


9. óra (IV. 27.)

HF-ek megbesz (25-27).

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ő.


10. óra (V. 4.)

Hf-ek megbesz.
Lista-színezések, Brooks tétel 3-összefüggőkre. Brooks egyszeresen összefüggőre.
Egy páros gráf, a komplementere, páros gráf élgráfja, és ennek komplementere is perfekt. (Természetesen a perfekt gráf tételek használata nélkül!)
Mennyi a kromatikus száma Kn élgráfjának, ennek komplementerének, illetve:
Szorgalmi Hf: mennyi a kromatikus száma az ide-oda irányított teljes gráf élgráfjának?


11. óra (pótóra) (V. 9. 14:00)

Beadandók közül 6, 12, 13, 5, 16, 17, 21 megbeszélése.


12. óra (V. 18.) 12:15--14:15

ZH
Pót-ZH: V. ?. ??:??