Mennyi a leghosszabb út amit meg lehet tenni, hogyha kétszer ugyanazon a szakaszon nem mehetünk, de az utak keresztezhetik egymást?

"NxN-es táblára?"

Az előző hsz alapján NxN-re is megoldható a feladat.

Eule-tételből tudjuk, hogy "egy gráfban akkor és csak akkor van Euler-vonal, ha összefüggõ, továbbá páratlan fokú csúcsainak száma 0 vagy 2. "

Minden belső pont fokszáma 4-es.

A külső pontoknál 3-3 él találkozik, itt törölni kell annyi élt, hogy csak két páratlan maradjon.

Páros N-re ez 4*N/2 = 2N él törlésekor van hurok, 2N-2 törlésekor van vonal.

Ha a két szemközti sarkot kell összekötni, akkor 2N-t kell törölni.

Páratlan esetén bonyolultabb a helyzet. Azt még nem számoltam ki.

@10:

Valóban nem voltam pontos. Egészen pontosan legalább annyi él kell, ami fedi a rossz csúcsokat. Ez jelen esetben 8, mert a rossz csúcsok két, 7 elemű komponenst alkotnak, azaz nincs él, melynek egyik végpontja egyik, másik a másik 7-es csoportban van. Így mindkét komponens fedéséhez kell legalább 4 él, tehát a 14 csúcshoz legalább 8.

Egyébként lehet konstrualni olyan gráfot, ahol csak két rossz csúcs van, de tetszőlegesen sok élet kell törölni a javításához.