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:

  1. u-ból pontosan akkor érhető el v D'-ben, ha elérhető D-ben,
  2. 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

Korábbi hallgatók