Problem S. 156. (November 2021)

S. 156. Subscribers can reach the text of the problem after signing in. The text will be public from November 28, 2021.]

(10 pont)

Deadline expired on December 15, 2021.

Sorry, the solution is available only in Hungarian. Google translation

Sándor Péter megoldása alapján:

Egy \(\displaystyle N\) csúcsú fagráfnak \(\displaystyle N-1\) éle van, tehát a feladatban szereplő \(\displaystyle N\) élű gráfban \(\displaystyle 1\) extra él van. Ez pontosan egy kört hoz létre.

Ezt a kört megkeressük. A kör csúcsait elhagyva fagráfokat (erdőt) kapunk.

A \(\displaystyle K\) hosszú utak megkeresését két alesetre bontjuk:

1. Nem megy át a kör egy élén sem (vagyis egy előbb említett fából nem lép ki)
Minden, az adott részgráfbeli pontra megkeresem, hogy mennyi tőle "k" távolságra lévő pont van az adott részgráfban. (Így mindent kétszer számolok, emiatt az eredményt elosztom kettővel)

2. Tartalmazza a kör valamely élét. Ekkor úgy néz ki a \(\displaystyle K\) hosszú út, hogy: egy fából kiindul, átmegy a kör valamennyi élén, majd átmegy egy másik fába ahonnan már nem léphet ki (mivel az fagráf).
A kör minden pontjához hozzárendelek egy tömböt ami azt tartalmazza, hogy ha az adott pont mint a megfelelő részgráf gyökere, akkor tőle mely távolságra mennyi pontja van a fagráfnak. (Ezt egy egyszerű DFS-el megtehetjük). Miután ezek a tömbök fel vannak töltve, azt figyelembe véve, hogy mely részgráf milyen távolságra csatlakozik a körökhöz, és a kiszámolt tömbök megfelelő elemeinek összeszorzásával ki tudjuk számolni a \(\displaystyle K\) hosszú utakat.

Statistics:

4 students sent a solution.
10 points:	Sándor Péter, Tóth 057 Bálint, Veres Benedek Zoltán.
3 points:	1 student.

Problems in Information Technology of KöMaL, November 2021