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

Mégis mire kell?

Mert általános gráfra ez NP-nehéz...

Nekem 34-re van kostrukcióm, ki tud jobbat?

Én pedig meg tudom mutatni, hogy 38 hosszú már nem lehet.

A 35, 36, 37-ről kéne nyilatkozni, és készen lennénk.

Azt a 34-et megnézném, szerintem 32 a max.

A sarokból csak egy irányba tudunk kimenni. Ha elindulunk egy irányba, akkor ott elágazáshoz érünk, ahol megint csak egy irányba tudunk menni. Tehát a sarok mellett 2-2 mezőt veszítünk.

Ezen kívül a két másik saroknál is van 3-3 út találkozik ott is veszítünk összesen 4 élt mindenképp.

összesen 40 él van, és 8-at mindenképp ki kell hagyni, így max 32.őt lehet bejárni. Ilyen bejárást találtam is.

[link]

Igen.

Nem olvastam elég figyelmesen a feladatot, hogy az is feltétel, hogy honnan indulunk és hova érkezünk.

Kicsit egyszerűbb bizonyítás: A sarok melletti csúcsokat nevezzük Vesztő Csúcsoknak. Mivel 3 élük van, ezért bármilyen sétában mindegyik vesztő csúcsnak kimarad legalább 1 éle, ez legalább 8 kimaradó él. QED

Az én válaszomban 2-nél többet úgy értem el, hogy akárhonnan indulhattam, és a sétám vesztő csúcsból indult és végződött.

Az Euler-tulajdonság alapján fogalmazzuk át a kérdést:

Legalább hány élet kell törölnünk a gráfból, hogy A kezdő- és végpont fokszáma páratlan, minden más csúcs fokszáma páros legyen?

Kezdetben 14 rossz fokszámú csúcs van, tehát ebből 7 lenne a minimum, azonban mivel a 14 csúcs két 7-es csoportban van, amik között nincs él, így legalább 8 élet kell törölnünk.

Összesen 40 él volt, tehát a maradék gráf 32 élt, tartalmaz. Fél-Euler tulajdnoságú a két kijelölt pontra, tehát 32 a leghosszabb út.

> Kezdetben 14 rossz fokszámú csúcs van, tehát ebből 7 lenne a minimum, azonban mivel a 14 csúcs két 7-es csoportban van, amik között nincs él, így legalább 8 élet kell törölnünk.

Ezt nem értem. Tudnád bővebben?