Hogy lehet megállapítani egy alakzatról, hogy egy vonallal megrajzolható-e egyáltalán (toll felemelése nélkül)?

Először is, összefüggőnek kell lennie (nyilván ez egy triviális feltétel), illetve ha nem összefüggő, akkor csak különálló pontok vannak az alakzat körül (amikhez nem tartoznak élek). Ha ez megvan, akkor két esetben;

-minden pontba pontosan páros sok vonal fut, ekkor a kiinduló pont és a végpont ugyanaz lesz

-pontosan két olyan pont van, amibe páratlan sok él fut, ekkor az egyik páratlanos lesz a kezdőpont, a végpont pedig a másik.

Bizonyított, hogy ha ezek a körülmények fennálnak, akkor létezik az első esetben zárt, a második esetben nyílt Euler-vonal.

Bővebben:

[link]

Ahogy #1 írta, akkor rajzolható meg egy alakzat a toll felemelése nélkül úgy, hogy minden vonalon csak egyszer halad át a toll, ha pontosan 2 vagy 0 olyan kereszteződés van, amibe páratlan számú vonal fut bele.

Hogy miért? (Inkább hétköznapi fogalmakkal írom le, elnézést, ha valakinek nem tetszene, hogy nem gráfról, élekről, csúcsokról, meg fokszámokról és hasonlókról fogok beszélni.)

Ha egy csomópontot nézünk, ha oda egy vonalon befut a tollad hegye, akkor egy másik vonalon el is kell hagynia. Ha egy harmadik vonalon újra befut a tollad hegye, akkor egy negyediken kell távoznia. Ha egy csomópontban páratlan vonal találkozik, akkor a bejövő és kimenő vonalak nem lesznek párokba oszthatóak. Csak akkor lehet egy vonallal megrajzolni, ha vagy ilyen csomóponttól indult el a tollad (és akkor nem kell ide visszaérkeznie), vagy ilyen csomópontban fejeződik be a rajzolásod (és akkor a bejövő vonalhoz nem kell tartoznia egy kimenő vonalnak is).

Ha két olyan csomópont van, amiben páratlan számú vonal találkozik, akkor azt csak úgy lehet megrajzolni, ha az egyik ilyen csomópontnál teszed le a tollat és a másiknál emeled fel a megrajzolás végén. Ha minden csomópontban páros számú vonal fut össze, akkor bármelyik csomóponttól kezdheted a rajzolást, ha megrajzoltad az alakzatot, a tollad oda fog befutni, ahol letetted.

(Az is belátható, hogy nem létezik olyan alakzat, amiben páratlan számú olyan csúcs van, amiben páratlan számú vonal fut össze. Ugye egy két csúcs között vonalnak két vége van, tehát a vonalvégek száma páros kell, hogy legyen, így az olyan csúcsok számának is párosnak kell lennie, amiben páratlan számú vonal fut össze. Tehát egy alakzatban mindig páros számú olyan csúcs lesz, amiben páratlan számú vonal fut össze. Ha 0 vagy 2 ilyen csúcs van, akkor az alakzat megrajzolható egy vonallal. Ha több, akkor minimum annyi vonallal lehet megrajzolni, mint az ilyen csúcsok számának a fele. Pl. ha 10 olyan csúcs van, amiben páratlan vonal fut össze, azt minimum 5 vonallal lehet csak megrajzolni.)

2*Sü, amit írtál, az igaz, csak ebből nem következik, hogy mindig megrajzolható. Csak azt láttad be, hogy szükséges, hogy minden csomóponthoz páros sok (ki/be)lépési lehetőség tartozzon, vagy legfeljebb 2-nek lehet páratlan, de ebből nem derül ki, hogy ténylegesen meg is rajzoható (tehát hogy elégséges feltétel is lenne).

Triviális ellenpélda, hogyha a gráf nem összefüggő. Ott is mindenki fokszáma lehet páros, mégsem megrajzolható. Ugyanez a helyet előfordulhat(na) összefüggő gráfok esetén is.

Vagy másként; te annak a bizonyítását írtad le, hogy ha az összefüggő (vagy legfeljebb izolált pontokat tartalmazó) gráfban létezik zárt/nyílt Euler vonal, akkor minden csúcs fokszáma páros/pontosan két csúcs fokszáma páratlan. De a fordítottja is kellene, hogy szükséges és elégséges feltétel lehessen a tétel.

> Triviális ellenpélda, hogyha a gráf nem összefüggő.

Értelmezés kérdése. Ugyanis a kérdező nem gráfról, hanem egy nem éppen matematikai szempontból egzakt fogalomról, „alakzatról” beszélt. Ha egy gráf nem összefüggő, akkor eléggé magától értődő, hogy nem rajzolható meg egy vonallal. De az ilyen gráfot tekinthetem kettő, vagy több alakzatnak és nem egynek. Vagy ha úgy tetszik, én abból indultam ki, hogy alakzat alatt a kérdező valójában egy összefüggő gráfot ért.

(A továbbiakban is alakzat alatt összefüggő, nem irányított, véges gráfot fogok érteni.)

> Ugyanez a helyet előfordulhat(na) összefüggő gráfok esetén is.

Annak a belátása, hogy nem csak szükséges, de elégséges feltétele is az alakzat egy vonallal való megrajzolásának, hogy csak 0 vagy 2 csúcs van, amibe páratlan vonal fut össze, az már kissé komplikáltabb, de ez is belátható. Legyen akkor kerek a történet, és lássuk is ezt be.

Ha 2 csúcsban találkozik páratlan számú vonal, akkor csináljunk egy utat, ami az egyikből indul, bejárja az alakzat néhány csúcsát, majd elérkezik a másik ilyen csúcshoz. Ha 0 csúcsban találkozik páratlan számú vonal, akkor járjunk be egy kört. A szemléltetés kedvéért legyen ez a mi 1.0-ás főútvonalunk.

Ha érintettünk minden vonalat, akkor készen is vagyunk. Ha nem, akkor biztos, hogy lesz olyan csúcs, amin átment a főútvonalunk, de futnak be még ebbe a csúcsba „mellékutak” is. Ha nem így lenne, nem lenne zárt az alakzatunk. Az is biztos, hogy innentől minden csúcsba páros számú mellékút fog összefutni. Oké, szemeljünk ki egy ilyen csúcsot, és csak mellékútvonalakat érintve induljunk el rajta. Előbb-utóbb biztos, hogy vissza fogunk jutni a kiinduló pontra. Hiszen bármelyik csúcshoz is érünk, abba páros számú mellékút fog összefutni, ha bejöttünk egy mellékúton, távozni is tudunk egyen. Egy esetben nem tudunk tovább haladni, ha a mellékútvonalunk kiinduló pontjába értünk vissza, és onnan már nem vezet ki több mellékút. Így ez a mellékútvonalunk egy kör lesz.

Oké, most induljunk el az 1.0-ás főútvonalon, és mikor ahhoz a csúcshoz érünk, ahonnan a mellékkörünk elindult, menjünk végig ezen a mellékkörön, majd visszatérve folytassuk az utat az 1.0-ás főútvonalunkon. Legyen ez a mi 2.0-ás főútvonalunk, ami az 1.0-ás főútvonalnak a mellékkörrel való kiegészítése.

Ha érintettünk minden vonalat, akkor készen vagyunk, ha nem, akkor az előzőekhez hasonlóan biztos, hogy lesz olyan csúcs, amin átmegy a 2.0-ás főútvonalunk, de vezetnek ki ebből a csúcsból mellékutak is. Megint ha ez nem igaz, akkor az alakzatunk nem lenne zárt. Ugyanígy tudunk csinálni egy újabb mellékkört, amit ugyanúgy hozzá tudunk csapni a főútvonalhoz.

Mivel minden ilyen lépésben újabb vonalak kapcsolódnak a főútvonalhoz, előbb-utóbb elfogynak azok a vonalak, amiket nem érintettünk.

Tehát nem csak szükséges, de elégséges feltétele is az egy vonallal való megrajzolhatóságnak, hogy az alakzatban pontosan 0 vagy 2 olyan csúcs legyen, amiben páratlan számú vonal fut össze.

Szép, szemléletes levezetés, és nem akarok kötekedni, de a

"Ha 0 csúcsban találkozik páratlan számú vonal, akkor járjunk be egy kört."

kellene egy kicsit konkretizálni. Mert az ember még hirtelen azt gondolja, hogy Hamilton-körre gondolsz; kör alatt olyan élsorozatot kell érteni, melyben bármely csúcsból bármely csúcsba el lehet jutni csak az élsorozat éleit használva, viszont ez a kör nem feltétlenül tartalmazza az összes csúcsot (bár optimálisan kell, hogy tartalmazza, mert akkor van esély arra, hogy minden élt bejártunk), de egy csúcshoz akár 2-nél több él is tartozhat.