Vorlesung 24.01.2020 Inhaltsverzeichnis Graﬁk: Farben und ... · TypeError: unsupported operand parent(s) for /: 'Integer Ring' and '' Wir wollen eine entsprechende

Vorlesung 24.01.2020

InhaltsverzeichnisGrafik: Farben und HSV-Koordinaten1. Fehlerbehandlung: Exceptions2. Abstrakte Algebra: Gruppen3. Kombinatorik: Graphen4.

Grafik: Farben und HSV-KoordinatenDie Farbe von Graphen kann mit der Option color festgelegt werden.

p = plot(x^2,0,1, color='red')p

Vorlesung 24.01.2020 -- Sage

1 of 25

Wenn man viele verschiedene Farben benötigt, ist es besser, eine Parametrisierung des Farbenraumszu verwenden. Entweder, indem die drei Farbkanäle direkt angegeben werden,

plot(x^2, x, -1, 1, rgbcolor = [0.5,0.7,0.1])


2 of 25

oder intuitiver anhand anhand des Farbtons in HSV-Koordinaten (engl. hue-saturation-value). Alledrei Koordinaten verlaufen in sage im Intervall [0..1]. Der hue-Wert legt die Wellenlänge fest undmit s=v=1 erhält man reine Grundfarben:

p = Graphics()for x in srange(0,1,0.001): p = p+line([(x,0),(x,1)], hue = x)p


3 of 25

Verringerung der Sättigung entspricht dem Zumischen von weißer Farbe:

p = Graphics()for x in srange(0,1,0.001): p = p+line([(x,0),(x,1)], rgbcolor = hue(x,s=0.5))p


4 of 25

In dieser Variante wird der hue-Wert direkt in RGB-Koordinaten umgewandelt.

hue(0.6)

(0.0, 0.40000000000000036, 1.0)

def colorcircle(r, n=360,sat=1, val=1): p =Graphics() for k in range(n): p += point([r*cos(k*pi/180),r*sin(k*pi/180)],color=hue(k/n,s=sat)) return p

colorcircle(1).show(aspect_ratio=1)


5 of 25

disk=Graphics()for t in srange(0,1,0.02): disk += colorcircle(t,sat=t)disk.show(aspect_ratio=1)


6 of 25

Der Parameter value variiert die Helligkeit und entspricht dem Zumischen von schwarzer Farbe.

p = Graphics()for x in srange(0,1,0.001): p = p+line([(x,0),(x,1)], rgbcolor = hue(x,v=0.5))p

Fehlerbehandlung: ExceptionsWir nehmen verschiedene Fehlermeldungen unter die Lupe.

Ein NameError tritt immer bei undefinierten Variablen auf.

y

Traceback (click to the left of this block for traceback)


7 of 25

...NameError: name 'y' is not defined

Ein ValueError besagt, daß zwar ein Objekt des richtigen Typs übergeben wurde, das aber einenungeeigneten Wert hat.

factorial(-1)

Traceback (click to the left of this block for traceback)...ValueError: factorial only defined for non-negative integers

1/0

Traceback (click to the left of this block for traceback)...ZeroDivisionError: rational division by zero

1/[1,2]

Traceback (click to the left of this block for traceback)...TypeError: unsupported operand parent(s) for /: 'Integer Ring' and'<type 'list'>'

Wir wollen eine entsprechende Fehlermeldung in die folgende Funktion einbauen (Catalanzahlen).

def cat(n): if n == 0: return 1 res = cat(n-1) for k in range(n-1): res += cat(k)*cat(n-1-k) return res

cat(5)

42

Die Funktion ist nicht gegen unendliche Rekursion gesichert.

cat(-1)

WARNING: Output truncated! full_output.txt

Traceback (click to the left of this block for traceback)...RuntimeError: maximum recursion depth exceeded in cmp

full_output.txt


8 of 25

Eine Möglichkeit ist, einen String mit der entsprechenden Fehlermeldung zurückzugeben.

def cat(n): if n < 0: return "n nicht positiv" if n == 0: return 1 res = cat(n-1) for k in range(n-1): res += cat(k)*cat(n-1-k) return res

cat(-1)

'n nicht positiv'

Besser ist es aber, eine richtige Fehlermeldung zu erzeugen, d.h., eine sogenannte "Exception".Dabei wird nicht einfach abgebrochen, sondern eine "Ausnahmesituation" erzeugt und gleichzeitigübermittelt, um welche Art von "Ausnahmesituation" es sich handelt. Die entsprechende Anweisungraise ist Teil der Programmiersprache python. In unserem Fall soll es analog zum factorial-Beispieloben ein ValueError sein.

def cat(n): if n < 0: raise ValueError,"n nicht positiv" if n == 0: return 1 res = cat(n-1) for k in range(n-1): res += cat(k)*cat(n-1-k) return res

cat(-1)

Traceback (click to the left of this block for traceback)...ValueError: n nicht positiv

Exceptions haben den Vorteil, daß das Programm beim Auftreten eines Fehlers nicht einfachabbricht, sondern man die Möglichkeit hat, für die Ausnahmesituation vorzusorgen. Man kannausprobieren, ob eine aufgerufene Funktion fehlerlos abläuft, und danach entsprechend der Art desFehlers vorgehen. Die kritische Funktion wird mit try ausprobiert, und dann die verschiedenenFehler mit except aufgefangen.

def dog(n): # wenn n <0, dann cat(-n) try: print "trying" return cat(n) print "succeeded" except ValueError:


9 of 25

print "failed" return cat(-n)

dog(1)

trying1

dog(-1)

tryingfailed1

Die Anweisung print "succeeded" wird nie erreicht.Man kann auch verschiedene Exceptions nacheinander abfragen. Bei der Division haben wir zweiArten von Exceptions gesehen.

1/0

Traceback (click to the left of this block for traceback)...ZeroDivisionError: rational division by zero

1/[1,2]

Traceback (click to the left of this block for traceback)...TypeError: unsupported operand parent(s) for /: 'Integer Ring' and'<type 'list'>'

Während Division durch eine Liste keinen Sinn ergibt, könnte man Division durch 0 als unendlichinterpretieren:

def div(n,m): try: return n/m except ZeroDivisionError: return oo except TypeError: print "geht nicht"

div(1,0)

+Infinity

div(1,[1,2])

geht nicht

Abstrakte Algebra: Gruppensage kennt außer den bisher behandelten Polynomen und Körpern noch viele andere algebraische


10 of 25

Strukturen. Als typisches Beispiel betrachten wir die Gruppe der Permutationen der Ordnung 5.

S5 = SymmetricGroup(5)S5

Symmetric group of order 5! as a permutation group

Elemente können direkt aus einer Liste erzeugt werden. Intern wird die Permutation sofort in einProdukt von Zyklen zerlegt.

p1=S5 ( [2,1,4,5,3])p1

(1,2)(3,4,5)

Allerdings muß die Ordnung übereinstimmen.

p1=S5 ( [6,2,1,4,5,3])p1

Traceback (click to the left of this block for traceback)...ValueError: Invalid permutation vector: [6, 2, 1, 4, 5, 3]

Die Permutation kann auch direkt als Zyklus eingegeben werden.

p2= S5( (2,3))p2

(2,3)

Dann stehen alle Gruppenoperationen zur Verfügung.

p1*p2

(1,3,4,5,2)

p2*p1

(1,2,4,5,3)

p1^-1

(1,2)(3,5,4)

Analog zur linearen Hülle in der linearen Algebra ist die von einer Familie erzeugte Untergruppedefiniert als die kleinste Gruppe, die die besagte Familie enthält.

G = S5.subgroup([p1,p2])G

Subgroup of (Symmetric group of order 5! as a permutation group)generated by [(2,3), (1,2)(3,4,5)]

Die Liste der Elemente.


11 of 25

len(G.list())

120

Die Verknüpfungstafel. Die Zeilen und Spalten sind entsprechend der obigen Liste duchnumeriert.

G.cayley_table()

Es können verschiedene Eigenschaften der Untergruppe abgefragt werden.

G.is_abelian()

False

Wieviele abelsche Untergruppen hat S5? Zunächst eine Liste aller Untergruppen.

S5ss = S5.subgroups()len(S5ss)

156

Aus dieser Liste wählen wir die abelschen aus.

SS5ab =[G for G in S5ss if G.is_abelian()]len(SS5ab)

87

Kombinatorik: Graphensage kennt viele Objekte aus der diskreten Mathematik, wir betrachten als stellvertretendes Beispielendliche Graphen. Wir beginnen mit einem leeren Graphen:

g = Graph()

An den Graphen können nach und nach Knoten und Kanten angehängt werden. Dabei wird keineKopie angelegt, sondern der Graph selbst verändert.

g.add_vertex(0)g


12 of 25

Ein Graph kann mit .show() oder .plot() angezeigt werden.

g.show()


13 of 25

Nicht vorhandene Knoten werden bei Bedarf automatisch erzeugt.

g.add_edge(1,2)g.add_edge(1,0)g.plot()


14 of 25

schon vorhandene Kanten oder Knoten werden nicht verdoppelt.

g.add_edge(1,2)g.add_edge(1,2)g.plot()


15 of 25

g.delete_edge(1,2)g.plot()


16 of 25

Die Bezeichnungen der Knoten können beliebige Objekte sein, allerdings müssen sie austechnischen Gründen unveränderbar (immutable) sein:

a = matrix([[x,1],[1,2]])g.add_edge(0,a)

Traceback (click to the left of this block for traceback)...TypeError: mutable matrices are unhashable

a.set_immutable()a[0,0] = 1

Traceback (click to the left of this block for traceback)...ValueError: matrix is immutable; please change a copy instead (i.e.,use copy(M) to change a copy of M).

a

[x 1]


17 of 25

[1 2]

g.add_edge(0,a)g.show()

Die Bilder können auch in verschiedenen Formaten exportiert werden.

Eine ganze Reihe vordefinierter Graphen ist in der Bibliothek graphs zugänglich.

p = graphs.PetersenGraph()g=p.show()

Es stehen viele Algorithmen zur Verfügung.

p.is_planar()

False

p.neighbors(1)


18 of 25

[0, 2, 6]

p.distance(1,4)

2

Eine Färbung eines Graphen ist eine Abbildung, die jedem Knoten eine Farbe zuordnet, und zwarso, daß benachbarte Knoten verschiedene Farben haben. Die chromatische Zahl ist diekleinstmögliche Anzahl von Farben, mit denen eine Färbung möglich ist.

p.chromatic_number()

3

Eine solche minimale Färbung kann explizit gefunden werden.

p.coloring()

[[1, 3, 5, 9], [0, 2, 6], [4, 7, 8]]

Um die Färbung zu zeichnen, kann man auch direkt Farbwerte erzeugen.

c=p.coloring(hex_colors=True)c

{'#0000ff': [4, 7, 8], '#00ff00': [1, 3, 5, 9], '#ff0000': [0, 2,6]}

Diese können der Methode .show() als Option übergeben werden.

p.show(vertex_colors=c)

Wir können die symmetrische Gruppe auf den Knoten des Graphen agieren lassen, d.h., die Knoten


19 of 25

anhand von Permutationen umzubenennen.

S10 = SymmetricGroup(10)

Wir vertauschen die inneren mit den äußeren Knoten. Dabei ist zu beachten, daß die Knoten anhandihrer Position in der Knotenliste identifiziert werden.

u=S10([6,7,8,9,10,1,2,3,4,5])u

(1,6)(2,7)(3,8)(4,9)(5,10)

da der Graph direkt verändert wird, legen wir zuerst Kopien an.

p1=p.copy()p2=p.copy()

p2.relabel(u)

p1.show()p2.show()


20 of 25

p1.is_isomorphic(p2)

True

Ein Baum ist ein Graph ohne Kreise. Im Gegensatz zu allgemeinen Graphen können Bäumerelativ einfach algorithmisch erzeugt werden, was in Form eines Generators implementiert ist.

t5=graphs.trees(5)t5

<sage.graphs.trees.TreeIterator object at 0x7f6c17be3618>

for t in t5: t.show()


21 of 25

Ein Beispiel eines platonischen Körpers.

g20 = graphs.IcosahedralGraph()g20.show()


22 of 25

g20.hamiltonian_cycle().show()

g20.eulerian_circuit()

False

Ein eulerscher Graph muss gerade Knotengrade haben, z.B. der K5


23 of 25

k5 = graphs.CompleteGraph(5)k5.show()

k5.eulerian_circuit()

[(0, 4, None), (4, 3, None), (3, 2, None), (2, 4, None), (4, 1, None), (1, 3, None), (3, 0, None), (0, 2, None), (2, 1, None), (1, 0, None)]

Um die Reihenfolge sichtbar zu machen, numerieren wir die Kanten anhand dieser Liste durch.

for e,i in zip(k5.eulerian_circuit(), (1..)): k5.set_edge_label(e[0],e[1],i)

k5.show(edge_labels=True)


24 of 25


25 of 25

Documents

Vorlesung 24.01.2020 Inhaltsverzeichnis Graﬁk: Farben und ... · TypeError: unsupported operand parent(s) for /: 'Integer Ring' and '' Wir wollen eine entsprechende