Irányított gráfok minimális reprezentációja
| Témavezető: | Bérczi Kristóf |
| ELTE TTK, Operációkutatási Tsz. | |
| email: | kristof.berczi@ttk.elte.hu |
Projekt leírás
Egy D=(V,A) irányított gráf r-reprezentációján egy olyan D'=(V,A') irányított gráfot értünk, melyre a következő feltételek teljesülnek bármely két u,v pont esetén:
- u-ból pontosan akkor érhető el v D'-ben, ha elérhető D-ben,
- ha u-ból elérhető v D-ben, akkor D'-ben elérhető legfeljebb r lépésben.
A hallgató feladata erősen összefüggő gráfok r-reprezentációinak vizsgálata