Király Zoltán fog előadni.


Fokszámsorozatok realizációi
<br><br>
Az előadás kapcsolódni fog Miklós István múlt heti előadásához, de
anélkül is teljesen érthető lesz. Az előadás első felében
István által a végén felírt "Erős sejtés"-t bizonyítjuk,
ami két, azonos fokszámú gráf C_4-távolságáról szólt
(ez azt takarja, hogy minimum hány C_4-swappal lehet eljutni egyikből a
másikba).
Utána egy kicsit megnézzük ezt a problémát irányított gráfok esetén is.
(Ezek az eredmények Erdős Péterrel és Miklós Istvánnal közösek).
<br><br><br>
Az előadás második felében arról lesz szó, hogy egy adott n hosszú
fokszámsorozatnak mennyi idő alatt tudjuk felsorolni az összes
realizációját.
Lényegében azt fogjuk megmutatni, hogy ha a sorozatnak N realizációja van,
akkor fel tudjuk őket sorolni O(Nn^2) időben.
Ezalatt sorban ki is printeljük minden realizáció szomszédsági mátrixát,
szóval ezt nyilván nem is lehet gyorsabban.