Lösung Aufgabe 15

[Anonymous]

Mit der Knoteninvariante „3-Färbungszahl“ lassen sich Knoten unterscheiden: Ist sie
verschieden, so sind die Knoten sicher auch verschieden.
Hier ein Lösungsvorschlag:
https://www.dropbox.com/s/xt7tygn8rl9iuvv/15_magische_B%C3%A4nder_Knotenth
eorie.JPG?dl=0

[Anonymous]

Bei der Aufgabe musste ich meine rudimentären Kenntnisse zur Knotentheorie auffrischen. Das führte mich ebenso auf die 3-Farben-Regel. Der einzige Knoten, der sich den Färbungsregeln mit 3 Farben färben lässt, ist Knoten Nr. 4. Damit ist dieser der einzige, der äquivalent zum Doughnut-Geschenkband sein kann.

[Anonymous]

Ah, ich habe die Knoten einfach langsam auf dem Papier auseinandergedröselt, sie invariante gibt natürlich gleich eine sehr hübsche Lösung! Ich hatte noch überlegt, ob es irgendeine algebraische Darstellung der Kreuzungspunkte gibt, vermute immernoch, dass das geht, aber kenne mich auf dem Gebiet nicht aus.

[Anonymous]

Ich hatte mir dieses Jahr vorgenommen, jede Aufgabe mit einem Python-Script zu lösen. Aufgabe 15 war mein Endgegner. Für jemanden, der vorher noch nie von Knotentheorie gehört hat, war das ein echter Höllenritt…

import copy
import random

class Knot:
    def __init__(self,name,gauss):
        self.name = name
        self.gauss = gauss
        self.nodes = len(gauss)
        self.unknot = False
        self.nochange = 0
        self.lastprint = str(gauss)

    def clean_gauss(self):
        #This functions cleans the gauss code after every move
        found = [0]
        missing = []
        if not self.gauss:
            #check if knot is done
            self.unknot = True
            if self.lastprint != str(self.gauss):
                print(self.gauss)
                self.lastprint = str(self.gauss)
            return None
        for element in self.gauss:
            #check if elements are in numerical order (mainly for R2 and aesthetics)
            if abs(element) == found[-1] + 1:
                found.append(abs(element))
            elif abs(element) > found[-1] + 1:
                switch = [[],[]]
                for index, element_2 in enumerate(self.gauss):
                    if abs(element_2) == abs(element):
                        switch[0].append(index)
                    if abs(element_2) == found[-1] + 1:
                        switch[1].append(index)
                if switch[1]:
                    #Switch numbers that appear "too early" in the sequence with their later occuring counterparts.
                    #This doesn't mutate the knot in any way but "renames" the overlaps.
                    next_gauss = self.gauss[:]
                    if self.gauss[switch[0][0]] * self.gauss[switch[1][0]] > 0:
                        next_gauss[switch[0][0]] = self.gauss[switch[1][0]]
                        next_gauss[switch[0][1]] = self.gauss[switch[1][1]]
                        next_gauss[switch[1][0]] = self.gauss[switch[0][0]]
                        next_gauss[switch[1][1]] = self.gauss[switch[0][1]]
                    else:
                        next_gauss[switch[0][0]] = self.gauss[switch[1][1]]
                        next_gauss[switch[0][1]] = self.gauss[switch[1][0]]
                        next_gauss[switch[1][0]] = self.gauss[switch[0][1]]
                        next_gauss[switch[1][1]] = self.gauss[switch[0][0]]
                    self.gauss = next_gauss
                    #call function again in case more have to be switched
                    self.clean_gauss()
                else:
                    for i in range(found[-1] + 1,abs(element)):
                        missing.append(i)
                found.append(abs(element))
        missing.sort(reverse=True)
        for miss in missing:
            #fill gaps by (absolutely) decreasing all numbers that are bigger than the missing ones
            for index, element in enumerate(self.gauss):
                if abs(element) > miss:
                    if element > 0:
                        self.gauss[index] -= 1
                    if element < 0:
                        self.gauss[index] += 1
        if self.gauss[0] == -1:
            #make code prettier by always having +1 at the start
            new_gauss = [-x for x in self.gauss]
            self.gauss = new_gauss
        if self.lastprint != str(self.gauss):
            print(self.gauss)
            self.lastprint = str(self.gauss)

    def reidemeister_1(self):
        #remove two nodes (a, -a) that are adjacent and part of the same overlap. Easy!
        #can even handle more of these occurences at once
        candidates = []
        for index, element in enumerate(self.gauss):
            if element == -self.gauss[(index+1)%self.nodes]:
                candidates.append(index)
                candidates.append((index+1)%self.nodes)
        candidates = sorted(list(dict.fromkeys(candidates)), reverse=True)
        if candidates:
            self.nochange = 0
            print(str(len(candidates)//2) + ' x Reidemeister I on knot '+str(self.name)+ ' found!')
            for i in candidates:
                del self.gauss
                self.nodes -= 1
        else:
            self.nochange += 1
        self.clean_gauss()

    def reidemeister_2(self):
        #remove four nodes (a, b ... [-a, -b] xor [-b, -a])
        candidates = []
        for index, element in enumerate(self.gauss):
            possible_pair = []
            if element * self.gauss[(index+1)%self.nodes] > 0:
                possible_pair = [abs(element), abs(self.gauss[(index+1)%self.nodes])]
                possible_pair.sort()
            for index_partner, element_partner in enumerate(self.gauss):
                if possible_pair == sorted([abs(element_partner), abs(self.gauss[(index_partner+1)%self.nodes])]):
                    quad = set([index, (index+1)%self.nodes, index_partner, (index_partner+1)%self.nodes])
                    if len(quad) == 4:
                        candidates = sorted(list(dict.fromkeys(quad)), reverse=True)
        if candidates:
            self.nochange = 0
            print('Reidemeister II on knot '+str(self.name)+ ' found!')
            for i in candidates:
                del self.gauss
                self.nodes -= 1
        else:
            self.nochange += 1
        self.clean_gauss()

    def reidemeister_3(self):
        #performs triangle operation on six nodes (a, b ... [-a, c] xor [c, -a] ... [-b, -c] xor [-c , -b])
        #a, b stays in place. The rest gets moved around: -a becomes c becomes -b becomes -c becomes -a
        candidates = []
        if self.nodes > 7:
            #only do this for at least 8 nodes. R1 and R2 are better for 6, 4 or 2 nodes for obvious reasons
            for index, element in enumerate(self.gauss):
                #find a and b
                if element > 0 and self.gauss[(index+1)%self.nodes] > 0:
                    candidates.append([[index,(index+1)%self.nodes],[self.gauss.index(-element)],[self.gauss.index(-self.gauss[(index+1)%self.nodes])]])
                    if self.gauss[candidates[-1][1][0]-1] == -self.gauss[candidates[-1][2][0]-1]:
                        #both c and -c appear before -a and -b in the code
                        candidates[-1][1].append(candidates[-1][1][0]-1)
                        candidates[-1][2].append(candidates[-1][2][0]-1)
                    elif self.gauss[candidates[-1][1][0]-1] == -self.gauss[(candidates[-1][2][0]+1)%self.nodes]:
                        #c appears before -a and -c appears after -b in the code
                        candidates[-1][1].append(candidates[-1][1][0]-1)
                        candidates[-1][2].append((candidates[-1][2][0]+1)%self.nodes)
                    if self.gauss[(candidates[-1][1][0]+1)%self.nodes] == -self.gauss[candidates[-1][2][0]-1]:
                        #c appears after -a and -c appears before -b in the code
                        candidates[-1][1].append((candidates[-1][1][0]+1)%self.nodes)
                        candidates[-1][2].append(candidates[-1][2][0]-1)
                    elif self.gauss[(candidates[-1][1][0]+1)%self.nodes] == -self.gauss[(candidates[-1][2][0]+1)%self.nodes]:
                        #both c and -c appear after -a and -b in the code
                        candidates[-1][1].append((candidates[-1][1][0]+1)%self.nodes)
                        candidates[-1][2].append((candidates[-1][2][0]+1)%self.nodes)
                    if len(candidates[-1][1]) == 1:
                        #no c found
                        del candidates[-1]
                    elif len(candidates[-1][1]) == 3:
                        #two different c,-c pairs found, make copy of candidate and have both versions in the candidates
                        candidates.append(copy.deepcopy(candidates[-1]))
                        del candidates[-2][1][2]
                        del candidates[-2][2][2]
                        del candidates[-1][1][1]
                        del candidates[-1][2][1]
        if candidates:
            self.nochange = 0
            #Random choice as i cant be bothered to implement some kind of intelligence here
            chosen = random.choice(candidates)
            print('1 of ' + str(len(candidates)) + ' possible Reidemeister III on knot '+str(self.name)+ ' performed!')
            next_gauss = self.gauss[:]
            #c moves to where -a was
            next_gauss[chosen[1][0]] = self.gauss[chosen[1][1]]
            #-b moves to where c was
            next_gauss[chosen[1][1]] = self.gauss[chosen[2][0]]
            #-c moves to where -b was
            next_gauss[chosen[2][0]] = self.gauss[chosen[2][1]]
            #-a moves to where -c was
            next_gauss[chosen[2][1]] = self.gauss[chosen[1][0]]
            self.gauss = next_gauss
        else:
            self.nochange += 1
        self.clean_gauss()

#sadly not solvable (yet):
#1:[-1,2,-3,4,-5,3,-6,-7,-2,1,-8,9,-10,6,-4,5,7,8,-9,10]
#I use an equal version of knot 1 instead
#this needs R1 or R2 insertions at specific positions to be solvable by P algorithms

gauss_codes = {1:[-1,-2,3,-4,2,1,-5,6,-7,-3,4,5,-6,7],
               2:[-1,2,3,4,5,6,-7,-3,8,-5,-6,1,-2,7,-4,-8],
               3:[1,-2,-3,4,5,6,-7,8,-9,-10,11,12,13,7,-8,-13,-12,9,14,-5,2,-1,-6,-14,-15,3,-4,15,10,-11],
               4:[-1,-2,-3,-4,-5,6,2,7,8,-9,-10,11,12,-13,-7,14,9,-8,-14,3,-15,5,4,15,-6,1,13,10,-11,-12],
               5:[-1,-2,-3,-4,-5,-6,-7,3,-8,1,-9,7,-10,5,-11,9,2,8,4,10,6,11],
               6:[-1,-2,-3,4,-5,-6,2,1,-7,5,-4,3,6,7],
               7:[-1,2,3,-4,-2,-5,6,7,8,1,-7,-9,5,-3,4,-6,9,-8],
               8:[1,2,-3,-4,5,-6,7,3,-2,-8,6,9,4,-5,-9,-7,8,-1],
               9:[-1,2,-3,4,5,-6,-7,3,-2,1,8,9,-4,7,6,-5,-9,-8],
               10:[-1,-2,3,4,-4,-5,6,-7,8,1,2,-3,5,-6,-9,-8,7,9]}

result = {1:None,2:None,3:None,4:None,5:None,6:None,7:None,8:None,9:None,10:None}

for key, gauss_code in gauss_codes.items():
    knot = Knot(key,gauss_code)
    if sum(knot.gauss) != 0:
        raise ValueError
    print('Knot ' + str(knot.name) + ':')
    print(knot.gauss)
    while not knot.unknot and knot.nochange < 2:
        while not knot.unknot and knot.nochange < 2:
            #Exhaust R1 and R2 as they are much easier to perform and have no randomness
            knot.reidemeister_1()
            knot.reidemeister_2()
        knot.reidemeister_3()
    result[key] = knot.gauss
    print('\n')

print('Most simplified knots:')
for key, gauss_code in result.items():
    print(key, gauss_code)
input('')

[Anonymous]

Danke, das ist die computernotation, die ich gesucht aber nicht gefunden habe.

[Anonymous]

Ich habe mir dieses, wie jedes Jahr, vorgenommen alle Aufgaben mit Stift und Papier zu lösen.
Ich bin aber leider zweimal gescheitert (einmal an meiner nicht optimalen Strategie bei der Mützenaufgabe) und bei Aufgabe 23, da musste wir alle (leider) auf einen Rechner zurückgreifen.

[Anonymous]

Anonymous wrote:

Python-Script

Jetzt, wo ich ein paar suchbegriffe habe, habe ich folgende schöne Seite gefunden:
https://www1.cmc.edu/pages/faculty/VNelson/vknots.html
Insgesamt ist in allen Referenzen jeder Weg über eine Kreuzung mit 3 Informationen beschrieben: Nummer der Kreuzung, drunter oder drüber, Orientierung (+ oder -).
Im python-Script gibt es nur zwei, und durch Vergleichen scheinen die Vorzeichen vor den Zahlen nicht die Orientierung, sondern drüber/drunter anzugeben. Hab ich was übersehen, oder hat danjark einfach Glück gehabt, dass es trotzdem ging?

[Anonymous]

Hat eine von euch versucht, die zeichnerische Lösung als Abfolge von Reidemeister-Bewegungen zu formalisieren? Ich versuche das gerade an Knoten 3, den man ja ganz einfach auflöst, indem man den Strang, der von oben mittig nach rechts unten verläuft und bei allen vier Kreuzungen unten liegt, nach recht rausschiebt. Aber welche Reidemeister-Bewegungen sind das? Freue mich auf Erhellung.

[Anonymous]

Ich merke gerade, dass das Forum eventuell nicht der beste Ort ist, um Code zu posten. Trotz “Code”-Tags werden solche sachen wie “[” “i” “]” als BB-Code erkannt und nicht 1 zu 1 wiedergegeben.
In den Zeilen mit del self.gauss muss natürlich noch ein “i” in eckigen Klammern folgen. Dann läuft der Code auch und gibt für Knoten 3 folgendes aus:

Knot 3:
[1, -2, -3, 4, 5, 6, -7, 8, -9, -10, 11, 12, 13, 7, -8, -13, -12, 9, 14, -5, 2, -1, -6, -14, -15, 3, -4, 15, 10, -11]
Reidemeister II on knot 3 found!
[1, -2, -3, 4, 5, 6, -7, 8, -9, -10, 11, 7, -8, 9, 12, -5, 2, -1, -6, -12, -13, 3, -4, 13, 10, -11]
1 of 1 possible Reidemeister III on knot 3 performed!
[1, -2, -3, 4, 5, 6, -7, 8, -9, -10, 11, 7, -8, 9, -6, 12, 2, -1, -12, -5, -13, 3, -4, 13, 10, -11]
1 of 3 possible Reidemeister III on knot 3 performed!
[1, -2, 3, -4, -5, -6, 7, -8, 9, 10, -11, -7, 8, -9, 6, -1, -12, 12, 2, 5, 13, -3, 4, -13, -10, 11]
1 x Reidemeister I on knot 3 found!
[1, -2, 3, -4, -5, -6, 7, -8, 9, 10, -11, -7, 8, -9, 6, -1, 2, 5, 12, -3, 4, -12, -10, 11]
1 of 1 possible Reidemeister III on knot 3 performed!
[1, -2, 3, -4, -5, -6, 7, -8, 9, 10, -11, -7, 8, -9, 6, -1, 2, 12, 4, -3, -12, 5, -10, 11]
1 of 3 possible Reidemeister III on knot 3 performed!
[1, 2, -3, -4, -5, -6, 7, -8, 9, 10, -11, -7, 8, -9, 6, -1, 12, 3, 4, -12, -2, 5, -10, 11]
Reidemeister II on knot 3 found!
[1, 2, -3, -4, 5, -6, 7, 8, -9, -5, 6, -7, 4, -1, 10, -10, -2, 3, -8, 9]
1 x Reidemeister I on knot 3 found!
[1, 2, -3, -4, 5, -6, 7, 8, -9, -5, 6, -7, 4, -1, -2, 3, -8, 9]
Reidemeister II on knot 3 found!
[1, 2, -3, 4, -5, -6, 7, 3, -4, 5, -2, -1, 6, -7]
Reidemeister II on knot 3 found!
[1, -2, 3, 4, -5, -1, 2, -3, -4, 5]
Reidemeister II on knot 3 found!
[1, -2, -3, -1, 2, 3]
Reidemeister II on knot 3 found!
[1, -1]
1 x Reidemeister I on knot 3 found!
[]

Dein Vorschlag, Kosakenzipfelchen, zuerst den Strang, der hinter 4 Kreuzungen verläuft, nach rechts rauszuschieben, ist vielleicht für Menschen offensichtlich, aber ein Algorithmus tut sich damit sehr schwer. Der Algorithmus erkennt zuerst den R2 der zentralen Lasche und muss danach R3-Bewegungen durchführen, um neue Angriffspunkte zu finden.

Es zeigt sich, dass der Algorithmus tatsächlich Schritt für Schritt den Strang nach rechts bewegt, bis er schließlich die R2-Bewegung im siebten Schritt erkennt. Danach fällt der Knoten in sich zusammen.

Zu deiner Frage bezüglich der Orientierung: Ja, wenn man einen Knoten eindeutig von seinem Spiegelbild unterschieden will, reicht der einfache Gauss-Code nicht aus. Da es hier aber nur darum ging, den Unknot (“Kein-Knoten”) von der Kleeblattschlinge zu unterscheiden, ist das nicht nötig. 🙂

Achja: Manchmal dreht der Algorithmus den Knoten komplett um, z.B. nach Schritt 3. Das habe ich aus rein ästhetischen Gründen eingebaut, damit vorn immer eine +1 steht. Er tut das natürlich nur nach Bewegungen, die irgendwie die 1. Überschneidung betreffen.

[Anonymous]

Danke.
Inzwischen hat mein matlab-Code diese R3 auch gefunden (kaum sind alle Bugs behoben…. Leider bin ich in python noch nicht so fit, und ich wollte auch selber was fabrizieren) Aber ich habe lange gebraucht, diese Schritte zu sehen. Jetzt stehe ich ‘nur’ noch vor dem Problem bei knoten 1, wie du auch.

[Anonymous]

Ja, Knoten 1 ist definitiv am härtesten für Algorithmen zu lösen. Nach meinem Verständnis müssen an bestimmten Stellen R1 oder R2 “eingefügt” werden, also der Knoten muss zunächst verkompliziert werden, bevor er dann durch R3 lösbar ist. Das war mir dann doch etwas zu viel Aufwand 😉

[Anonymous]

Ja, das könnte funktionieren. Wenn’s am Wochenende regnet probiere ich es aus.

[Author]

Posts