Gráfgyakorlat

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

2022 Tavasz

Gyakvezető: Király Zoltán

Szerda 14:00-15:30, TEAMS, majd 3.517


Csak a hallgatóimnak / Only for my students


Hirdetmények


1. óra (II. 9.)

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.

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.


2. óra (II. 16.)

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

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.


3. óra (II. 23.)

Hf-ek megbesz.

Mikor létezik pontos potenciál?

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.


4. óra (III. 2.)

Hf-ek megbesz.

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?


5. óra (III. 9.)

Hf-ek megbeszélése.
Hipergráf irányítós lemma.

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.

A feladatok


6. óra (III. 16.)

Blokk-felbontás végigbeszélése.

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.


7. óra (III. 23.)

Hf-ek megbesz.

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.


8. óra (III. 30.) 14:15-től!

Síkgráfok, dualitás, feszítőfák kapcsolata duális fesz.fáival, Euler-formula és 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.
Ötszíntétel (két bizonyítással).
Négyszíntétel, ha maxfok 5, de nem 5-reguláris.
Hibakeresés négyszíntételre adott rossz bizonyításban (Kempe, 1879).

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?


9. óra (IV. 6.)

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


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

Első körből újra beadható: a 4., 6., 7., 10. és 13.

Újak:

A feladatok.


10. óra (IV. 20.)

Hf-ek megbesz.
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).
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.
Egyszerű síkgráf csúcsait ki lehet úgy színezni két színnel, hogy egyik ország se legyen homogén.

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?


11. óra (IV. 27.)

Hf-ek megbesz.
Lista-színezések, Brooks tétel 3-összefüggőkre. Brooks egyszeresen összefüggőre.

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?


12. óra (V. 4.)

Beadandók közül 10., 13., 16., 17. (vázlatosan), 18. és 19. (vázlatosan) megbeszélése.


13. óra (V. 11. 14:00--16:00)

Zh
Pót-ZH: V. 25. 14:00