[DWII] Euleriaanse grafen

2986 days ago by Erik.Rijcken

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]]) G0.show(save_pos=True) 
       

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.show() 
       

Een Graph object heeft vele functies om allerlei informatie uit de graaf te halen. De meest eenvoudige functies geven je de lijst van toppen, de lijst van bogen, de buren van een gegeven top... Enkele voorbeelden:
print "De graaf G0 heeft orde",G0.order(),"en grootte",G0.size() print "De toppen van G0 zijn",G0.vertices() print "De bogen van G0 zijn",G0.edges(labels=False) print "De buren van top 1 in G0 zijn",G0.neighbors(1) print "Is G0 samenhangend?",G0.is_connected() 
        
De graaf G0 heeft orde 5 en grootte 6
De toppen van G0 zijn [0, 1, 2, 3, 4]
De bogen van G0 zijn [(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (3, 4)]
De buren van top 1 in G0 zijn [0, 2, 3, 4]
Is G0 samenhangend? True
De graaf G0 heeft orde 5 en grootte 6
De toppen van G0 zijn [0, 1, 2, 3, 4]
De bogen van G0 zijn [(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (3, 4)]
De buren van top 1 in G0 zijn [0, 2, 3, 4]
Is G0 samenhangend? True

Opdracht 1

Schrijf een functie is_euleriaans die bepaalt of een graaf Euleriaans is.
def is_euleriaans(G): #pas deze code aan zodat de output True is als en slechts als G een Euleriaanse graaf is. return True 
       

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 True
Complete bipartite graph is niet euleriaans. Mijn functie geeft True
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 True
Complete bipartite graph is niet euleriaans. Mijn functie geeft True

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. Schrijf een functie fleury die deze methode implementeert, en een lijst van toppen geeft in de volgorde waarin ze een Euleriaans circuit vormen.
def fleury(G): #pas deze code aan zodat de output een Euleriaans circuit van G geeft return [] 
       

Om je functie te testen is geven de volgende functies je twee manieren 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) 
       

Je gebruikt deze functies op een graaf G via de commando's interact(color_euleriaans_circuit(G,fleury(G))) en label_euleriaans_circuit(G,fleury(G)).

De gedefinieerde graaf G0 heeft bijvoorbeeld het Euleriaanse circuit [0,1,3,4,1,2,0], en dit wordt als volgt weergegeven:
_=interact(color_euleriaans_circuit(G0,[0,1,3,4,1,2,0])) 
       

Click to the left again to hide and once more to show the dynamic interactive window
label_euleriaans_circuit(G0,[0,1,3,4,1,2,0])