Matroidelmélet és műszaki alkalmazásai

1)      A matroidelmélet szempontjából legfontosabb lineáris algebrai és gráfelméleti ismeretek felelevenítése, ezeken keresztül a matroidok fogalmának a bevezetése. A mohó algoritmus matroidokra. A matroidok alternatív jellemzése a mohó algoritmus jóságának a segítségével.

2)      Matroidelméleti alapfogalmak: alaphalmaz, független részhalmazok, összefüggő részhalmazok, bázisok, körök, rangfüggvény. A grafikus, a lineáris és az uniform matroidok osztályának bevezetése, ezen osztályok viszonya (a bizonyítások egy része csak később).

3)      Matroidok jellemzése bázisaival, a duális matroid fogalma. Grafikus és kografikus matroidok. A síkbarajzolhatóság matroidelméleti jelentése (első rész). Duális matroid rangfüggvénye.

4)      Matroidok jellemzése a rangfüggvényével. Az elhagyás és összehúzás műveletek bevezetése, minorképzés, jelentésük grafikus, lineáris és uniform matroidok esetén. A síkbarajzolhatóság matroidelméleti jelentése (második rész), Kuratowski és Wagner tétele.

5)      Matroidok reprezentálhatósága. A szükséges testelméleti tételek. A Fano- és anti-Fano matroidok. Bináris, reguláris és grafikus matroidok jellemzése tiltott minorokkal (bizonyítás csak a feltételek szükségességére). Matroidok direkt összege. A Vámos-Higgs matroid.

6)      Matroidok uniója. A matroid partíciós probléma. Polinom rendű algoritmus a probléma megoldására tetszőleges számú matroid esetén.

 7)      A matroid metszet probléma. Polinom rendű algoritmus a probléma megoldására 2 matroid esetén, a 2-nél nagyobb számú matroidra vonatkozó eset NP-nehéz volta.

8)      A matroidelméleti algoritmusok adatstruktúrája, az orákulum fogalma. A nevezetes matroidelméleti orákulumok egymáshoz való viszonya.

9)      A k-polimatroid rangfüggvény fogalma, a k-polimatroid matching probléma nehézsége. Lovász tétele a k=2 eset polinom-idejű megoldhatóságáról bizonyos, a műszaki alkalmazások szempontjából fontos speciális esetben.

10)  Villamosságtani alkalmazások (első rész): A hálózatanalízis alapfeladata, Kirchhoff klasszikus eredményei, a „topológiai” formulák.

11)  Villamosságtani alkalmazások (második rész): Kirchhoff eredményeinek általánosítása ideális transzformátorokat és/vagy girátorokat tartalmazó hálózatokra. Az egyértelmű megoldhatóság szükséges feltétele lineáris n-kapukat tartalmazó hálózatokra. A dualitás-elv és kiterjesztései.

12)  Statikai alkalmazások (első rész): Rúdszerkezetek fogalma, a merevségi mátrix, az infinitezimális merevség fogalma. Maxwell tételei, Laman tétele, a Lovász-Yemini tétel.

13)  Statikai alkalmazások (második rész): Rúdszerkezetek minimális számú csuklóval való lefogása. „Tensegrity”-szerkezetek. Átlós rúddal vagy kábellel kimerevített síkbeli négyzetrácsok merevsége.

14)  Tartalék idő. Ismétlés, összefoglalás, a tanult anyagrészek rendszerezett áttekintése.