Algoritmus
Összecsukhatóság
A szerkezet akkor és csak akkor nem csukható össze vonallá, ha van benne páratlan sok élt tartalmazó kör. Ha ilyen van, akkor van egy (vagy több) legrövidebb páratlan kör is. Egy legrövidebb páratlan kör egy pontja legyen P, a tőle legtávolabbi él végpontjai Q és R.
Ekkor a gráfbeli legrövidebb út P-ből Q-ba és P-ből R-be a kör mentén halad és egyenlő hosszú. (Ha lenne rövidebb út, akkor kellene lennie húrnak [több gráfélből is állhat] a körben, az viszont egy páros és egy páratlan körre bontaná, vagyis találnánk rövidebb kört.)
Olyan P-t és Q-t és R-et keresünk tehát, amire
$d[P,R] = d[P,Q]$ és van él R és Q között.
(Itt
$d[i,j]$ a
Floyd-Warshall algoritmussal kiszámolható távolságfüggvény a gráfon.)
Legrövidebb összecsukott helyzet
Minden pontra megnézzük, milyen hosszú a fellógatott szerkezet. Ha az i pontra lógatjuk a játékot, a hossz: $\max_{j}d(i,j)$. Az összes i közül az a jó, ahol az előbbi érték minimális.
Kódok
Főoldal
>
Szakkörök
>
BDG Szakkör
>
2008/2009
>
8. óra - Floyd-Warshall algoritmus
>
Szerkezetek
>
Megoldás
