Co ma Euler do patchworku?

Dawno temu, w pierwszej połowie XVIII wieku Leonard Euler przechadzał się ulicami Królewca (znanego obecnie jako Kaliningrad) i zastanawiał się, czy możne przejść po wszystkich mostach na rzece Pregole tak, by po każdym przejść tylko raz (rysunek pożyczyłam z Wikipedii):



Pomyślał i pokazał, że się nie da. I nie tylko odpowiedział na to konkretne pytanie, ale ogólnie, dla każdego przypadku. Narysujmy ścieżki[1] przechodzące przez mosty. Po jednej ścieżce przechodzącej przez każdy, oczywiście łączących się ze sobą na lądzie/wyspach, by mieć jeden długi spacer. Otrzymaliśmy rysunek składający się z linii, łączących się ze sobą na końcach. Na czerwono zaznaczyłam możliwą trasę przejścia, na zielono - miejsce spotkań poszczególnych ścieżek.



Taki rysunek nazywamy grafem. Ważne są te połączenia (fachowo mówi się o węzłach lub wierzchołkach). Euler pokazał, że jeśli w każdym takim łączeniu spotyka się parzysta liczba ścieżek, to można zrobić taki spacer, że po każdej ścieżce przejdziemy tylko raz. Co więcej, możemy zacząć spacer w dowolnym miejscu. Graf taki nazywany eulerowskim.

Jeszcze chwila...

Jeśli w dwóch (i tylko w dwóch, nie więcej[2]) punktach styka się nieparzysta liczba ścieżek, to również możemy przejść po wszystkich po razie, ale musimy zacząć w tych dwóch konkretnych punktach. Graf taki nazywamy półeulerowskim.

W przykładzie powyżej w trzech miejscach styka się po 3 ścieżki, a jednym 5, czyli nie można przejść tak, by po każdym moście iść tylko raz.

Już kończę...

Kto nie wierzy, niech weźmie kartkę i ołówek i porysuje różne figury i wygibasy i zobaczy, że to zawsze działa (w końcu jest to bardzo poważne twierdzenie matematyczne). Na przykład takie proste grafy. Jeden jest półeulerowski, drugi - ani taki, ani eulerowski (sprawdzenie, który jest który zostawiam wam). Czyli jedną kopertę można narysować nie odrywając ołówka od kartki, drugą - nie.



Ale jak to się ma do patchworku? Przeglądam sobie czasami gotowe schematy do pikowania i widzę, że niektóre wymagają co i rusz zaczynania od nowej nitki. Bo jeśli nie od nowej nitki, to musiałabym po tej samej linii przejechać 2 lub więcej razy. To też ładnie nie wygląda. Każda nowa nitka to kłopot, więcej pracy z chowaniem końców, ryzyko, że z czasem nitki i tak powychodzą. O wiele wygodniej jest mieć taki wzór, w którym liczbę wolnych nitek ograniczymy jak tylko się da (najlepiej 1 początek i 1 koniec). Widzicie już związek?

Żeby wzór do pikowania dało się wyszyć jedną nicią, musi on być grafem eulerowskim lub półeulerowskim.

Przykłady. Grafem eulerowskim jest



Możemy zacząć pikowanie w dowolnym miejscu i bez przerywania narysować cały wzór.

Grafem półeulerowskim jest



Żeby zrobić cały wzór za jednym razem, musimy zacząć i skończyć w czułkach.

Tego wzoru natomiast nijak nie da się wypikować nie zaczynając wielokrotnie od nowej nici albo szyjąc dwa razy po tej samej linii.



Wszystkie powyższe szablony można kupić w sklepie Craftfabric, a Eulerze i teorii grafów poczytać choćby na Wikipedii.

[1] Używam nieco innych słów niż w poważnej teorii grafów, żeby było łatwiej zrozumieć, słowa ścieżka i spacer znaczą tam coś innego. Mam nadzieję, że matematycy mi wybaczą.
[2] Nie ma takiego grafu, w którym tylko w jednym punkcie styka się nieparzysta liczba odcinków. Dla chętnych: dlaczego tak jest? :)