Grafen in Sage: Euleriaanse grafen en circuits
Sage heeft heel wat mogelijkheden voor het werken met grafen. Je kan een graaf met $n$ toppen maken via de functie Graph, en er dan bogen aan toevoegen. In deze functie kan je ook meer informatie meegeven, zoals de adjacentiematrix of een dictionary met lijsten die voor elke top de buren geeft.
G0 = Graph(5)
G0.add_edge([0,1])
G0.add_edge([1,3])
G0.add_edges([[3,4],[4,1],[1,2],[0,2]])
|
|
Je kan ook heel wat standaardgrafen automatisch laten genereren in Sage: het object graphs heeft hiervoor allerlei functies.
P = graphs.PetersenGraph()
K = graphs.CompleteGraph(5)
K43 = graphs.CompleteBipartiteGraph(4,3)
O = graphs.OctahedralGraph()
O
|
Oplossing 1
Hieronder vind je drie mogelijkheden voor het implementeren van is_euleriaans. Deze zijn uiteraard niet de enige mogelijkheden.
def is_euleriaans(G):
# overloop alle toppen van G
# vanaf dat er een top is met een oneven aantal buren, is de graaf niet Euleriaans
# anders is de graaf wel Euleriaans
for i in G.vertices():
if len(G.neighbors(i))%2 != 0:
return False
# controleer als laatste ook nog of G samenhangend is
return G.is_connected()
|
|
def is_euleriaans_2(G):
# G.degree() geeft de rij van graden van G
# overloop deze rij, vanaf dat er een oneven getal in deze rij staat is de graaf niet Euleriaans
# anders is de graaf wel Euleriaans
for i in G.vertices():
if len(G.neighbors(i))%2 != 0:
return False
# controleer als laatste ook nog of G samenhangend is
return G.is_connected()
|
|
def is_euleriaans_3(G):
# een zeer korte versie van het voorgaande:
# tel de rest modulo 2 van alle graden bij elkaar op
# als deze som nul is, waren alle graden even, anders was er minstens een oneven graad
return sum([i%2 for i in G.degree()]) == 0 and G.is_connected()
|
|
Ter controle moet je functie de volgende resultaten geven:
for g in [G0,K,O]:
print g,"is euleriaans. Mijn functie geeft",is_euleriaans(g)
for g in [P,K43]:
print g,"is niet euleriaans. Mijn functie geeft",is_euleriaans(g)
Graph on 5 vertices is euleriaans. Mijn functie geeft True Complete graph is euleriaans. Mijn functie geeft True Octahedron is euleriaans. Mijn functie geeft True Petersen graph is niet euleriaans. Mijn functie geeft False Complete bipartite graph is niet euleriaans. Mijn functie geeft False Graph on 5 vertices is euleriaans. Mijn functie geeft True Complete graph is euleriaans. Mijn functie geeft True Octahedron is euleriaans. Mijn functie geeft True Petersen graph is niet euleriaans. Mijn functie geeft False Complete bipartite graph is niet euleriaans. Mijn functie geeft False |
Opdracht 2
Het bewijs van stelling 3.2.3 geeft een methode om van een Euleriaanse graaf een Euleriaans circuit te bepalen, het algoritme van Fleury. Hieronder vind je een implementatie van fleury.
# we maken eerst een hulpfunctie die een circuit maakt in een graaf, vertrekkende bij een gegeven top
# merk op dat deze functie de bogen van het circuit verwijdert uit de graaf
def maak_circuit(G,v):
# start het spoor in de top
C = [v]
while G.neighbors(C[-1]): # zolang de laatste top van het spoor nog buren heeft, kunnen we verder
C.append(G.neighbors(C[-1])[0]) # voeg een buur van de laatste top toe aan het spoor
G.delete_edge(C[-2],C[-1]) # verwijder de corresponderende boog uit de graaf
return C
def fleury(G):
# indien G niet Euleriaans is, is er geen Euleriaans circuit
if not is_euleriaans(G):
return []
# indien G niet samenhangend is, is er geen Euleriaans circuit
if not G.is_connected():
return []
# we maken een kopie van G, zodat we hier bogen kunnen verwijderen zonder dat G verandert
H = G.copy()
# we maken een initieel circuit dat begint in de eerste top van de lijst toppen
C = maak_circuit(H,H.vertices()[0])
while H.size()>0: #zolang er bogen overblijven, moeten we ons circuit uitbreiden
# we zoeken binnen het circuit dat we tot dusver hebben, naar een top waar er nog een boog vertrekt
startindex = 0
while H.degree(C[startindex])==0:
startindex = startindex+1
# we maken een nieuw circuit dat begint in de top van het circuit waar er nog een boog vertrekt
C2 = maak_circuit(H,C[startindex])
# we voegen het gevonden nieuwe circuit toe op de juiste plaats van het oude circuit
C = C[:startindex] + C2 + C[startindex+1:]
return C
|
|
Om je functie te testen is geeft de volgende functie je een manier om het gevonden circuit interactief weer te geven.
def color_euleriaans_circuit(G,C):
R = rainbow(len(C))
def show_path(steps=slider([0..len(C)-1],default = len(C)-1, label="steps")):
coloring = {R[i]:[(C[i],C[i+1])] for i in range(0,steps)}
coloring[(0.7,0.7,0.7)] = [(C[i],C[i+1]) for i in range(steps,len(C)-1)]
G.show(save_pos=True, edge_colors=coloring)
return show_path
def label_euleriaans_circuit(G,C):
for i in range(0,len(C)-1):
G.set_edge_label(C[i],C[i+1],i+1)
G.show(save_pos=True, edge_labels=True)
|
|
Om je functie te testen is geven we je de volgende functies om het gevonden circuit interactief weer te geven.
_=interact(color_euleriaans_circuit(G0,fleury(G0)))
Click to the left again to hide and once more to show the dynamic interactive window |
|||||||||||||||||
label_euleriaans_circuit(G0,fleury(G0))
|
_=interact(color_euleriaans_circuit(O,fleury(O)))
Click to the left again to hide and once more to show the dynamic interactive window |
|||||||||||||||||
label_euleriaans_circuit(O,fleury(O))
|
G = graphs.ChvatalGraph()
_=interact(color_euleriaans_circuit(G,fleury(G)))
Click to the left again to hide and once more to show the dynamic interactive window |
|||||||||||||||||
label_euleriaans_circuit(G,fleury(G))
|
|
|