Rruga e Eulerit

Në teorinë e grafeve, një rrugë e Eulerit në një graf është rruga e cila secilën nyje të grafit e viziton vetëm një herë. Cikël i Eulerit është rruga e Eulerit e cila mbaron në të njëjtën nyje prej ku ka filluar. Këtë lloj grafesh e studioj Leonhard Euler kur e zgjidhi problemin e famshëm të shtatë urave të Königsbergut në vitin 1736. Matematikisht problemi i shtatë urave formulohet si më poshtë:

Grafi i urave të Königsbergut. Ky graf nuk është Eulerian.

Ç'do nyje e këtij grafi është e shkallës çift, pra ai është një graf Eulerian . Duke ndjekur degët sipas rendit alfabetik fitojmë një rrugë të mbyllur ose cikël të Eulerit.

Është dhënë grafi në të djathtë, A është e mundur të konstruktohet rrugë ose cikël e cila fillon dhe mbaron në të njejtën nyje dhe secilën prej nyjeve tjera e viziton vetëm një herë?

Euleri vërejti se kusht i nevojshëm që një graf të ketë rrugë ose cikël të Eulerit është që ç'do nyje e tij të jetë e shkallës çift me fjalë tjera nga ç'do nyje del një numër çift degësh; Kjo do të thotë se grafi i Königsbergut nuk është Eulerian.

Referimet

• Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128-140.
• Hierholzer, C., "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechnung zu umfahren", Mathematische Annalen 6 (1873), 30-32.
• Lucas, E., Récréations Mathématiques IV, Paris, 1921.
• Fleury, "Deux problemes de geometrie de situation", Journal de mathematiques elementaires (1883), 257-261.

External links

• Discussion of early mentions of Fleury's algorithm
• McKay & Robinson