Ermittlung von Eulertouren mit Excel-VBA
Was ist eine Eulertour und an welche Voraussetzungen ist sie gebunden?
Eine Eulertour ist ein Weg durch einen Graphen, bei dem jede Kante (Verbindungslinie) genau einmal befahren wird und der an dem Knoten endet, bei dem er beginnt.
Nicht bei jedem Graph ist eine solche Tour möglich. Eine wichtige Voraussetzung für die Möglichkeit einer Eulertour ist, dass alle Knoten einen geradzahligen Grad haben müssen. Der Grad eines Knotens ist die Anzahl der Verbindungslinien, die sich dort treffen.
Wenn diese Voraussetzung gegeben ist, gibt es nicht nur eine mögliche Eulertour, sondern mehrere, manchmal sogar sehr viele. Insbesondere kann jeder Knoten Ausgangspunkt für eine solche Tour sein.
Betrachten wir den unten stehenden Graphen. Jeder der zehn Knoten hat als Grad eine gerade Zahl. Manche der Knoten, wie z.B. die Knoten 10 und 6, besitzen den Grad 2, andere, wie die Knoten 7, 8 und 5, haben den Grad 4. Eulertouren sollten also möglich sein.
Eine dieser Touren ergibt sich, wenn wir gleich den obersten Knoten, also die Nummer 10, als Startpunkt nehmen und in der unten angegebenen Reihenfolge durchlaufen. Natürlich könnten wir genau so gut den umgekehrten Weg nehmen.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
→ |
7 |
→ |
4 |
→ |
1 |
→ |
3 |
→ |
2 |
→ |
5 |
→ |
3 |
→ |
4 |
→ |
6 |
→ |
7 |
→ |
8 |
→ |
5 |
→ |
9 |
→ |
8 |
→ |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wie finden wir Eulertouren? – der Hierholzer-Algorithmus
Zur Ermittlung der Tour verwenden wir eine Variante des Algorithmus von Hierholzer, dessen Grobablauf im Folgenden umrissen wird.
Wir wollen davon ausgehen, dass die Knoten mit 1 beginnend durchnummeriert sind. Damit wir eine Tour ermitteln können, brauchen wir folgende Informationen:
- Welche Knoten sind miteinander verbunden? Diese Information könnte z.B. in Form einer Tabelle vorliegen (s. unten).
- An welchem Knoten soll die Tour starten und enden?
Ergebnis des Algorithmus ist eine Liste, in der die Knoten in der Reihenfolge aufgeführt sind, wie sie in der Tour angelaufen werden („Tourliste“). Ein und derselbe Knoten kann darin mehrmals vorkommen. Der Endknoten ist immer identisch mit dem Startknoten.
Die Ermittlung der Tour erfolgt in fünf Schritten, von denen die Schritte 2 bis 5 bei Bedarf wiederholt ausgeführt werden. Beim ersten Durchlauf der Schritte 2 bis 5 wird eine Tour gefunden, die gewöhnlich nicht alle Verbindungen umfasst, also nur eine Subtour ist. In jedem der folgenden Durchläufe wird dann diese Tour jeweils um eine weitere Subtour erweitert, bis am Ende alle Verbindungen einbezogen sind.
(1) Wir setzen den Startknoten der Tour als ersten Knoten in die Tourliste
(2) Wir bestimmen den Startknoten der nächsten Subtour. Beim allerersten Durchlauf ist dies der Startknoten der gesamten Tour. Ansonsten suchen wir den Startknoten der Subtour, indem wir die Knoten der bereits zusammengestellten Tour durchgehen und den ersten nehmen, von dem noch unbegangene Verbindungen abgehen.
(3) Ausgehend vom Startknoten der Subtour verfolgen wir bislang unbegangene Verbindungen, bis wir wieder am Startknoten angelangt sind. Gibt es mehrere mögliche Verbindungen, so wählen wir die zu dem Knoten mit der niedrigsten Nummer. Die beschrittene Folge von Verbindungen bildet die Subtour.
(4) Wir fügen die Subtour hinter ihrem Startknoten in die bereits gebildete Tour ein.
(5) Wenn noch Knoten vorhanden sind, von denen unbegangene Verbindungen abgehen, so machen wir bei (2) weiter, ansonsten ist die Ermittlung der Tour beendet.
In den folgenden Beispielen ist die Bildung der Tour jeweils durch eine Graphik veranschaulicht. Darunter zeigt eine Zeilenfolge, wie sich die Tourliste von Durchlauf zu Durchlauf der Schritte 2
- 5 verändert.
Beispiel 1: Startknoten 3
Für ein erstes Beispiel nehmen wir an, der Benutzer habe als Startknoten für die Tour den Knoten 3 vorgegeben (s. Graphik unten).
Im ersten Schritt wird Knoten 3 als Startknoten in die Tourliste aufgenommen. Danach folgt die wiederholte Ausführung der Schritte 2 bis 5. Es wird sich zeigen, dass in diesem Fall diese Schrittfolge dreimal durchlaufen werden muss.
1. Durchlauf der Schritte 2 - 5
Schritt 2: Knoten 3 wird als Startknoten der Subtour identifiziert.
Schritt 3:Es werden die Knoten 1, 4 und schließlich wieder 3 angelaufen. Diese bilden die Subtour.
Schritt 4: Die Subtour wird hinter ihrem Startknoten (Knoten 3) in die Tourliste eingefügt (rote Pfeile).
Schritt 5: Da noch nicht begangene Verbindungen vorhanden sind, ist ein weiterer Durchlauf nötig.
2. Durchlauf der Schritte 2 -5
Schritt 2: Es wird nun nach dem Startknoten für die nächste Subtour gesucht. Hierzu werden die Knoten aus der bis dahin zusammengestellten Tour inspiziert. Bereits der erste Knoten (Nr. 3) erweist sich als geeigneter Startknoten, denn es gehen von ihm noch nicht benutzte Verbindungen aus.
Schritt 3: Es werden die Knoten 2, 5 und schließlich 3 angelaufen. Sie bilden die Subtour.
Schritt 4: Die Subtour wird in die Gesamttour eingefügt. Da der Startknoten der Subtour der erste Knoten der bis dahin vorhandenen Gesamttour (Nr. 3) ist, erfolgt das Einfügen hinter diesem Knoten (blaue Pfeile).
Schritt 5: Da noch nicht begangene Verbindungen vorhanden sind, ist ein weiterer Durchlauf nötig.
3. Durchlauf der Schritte 2 - 5
Schritt 2: als Startknoten der nächsten Subtour wird Knoten 5 ermittelt
Schritt 3: Die Knoten der Subtour sind 8, 7, 4, 6, 7, 10, 8, 9 und schließlich 5.
Schritt 4: Die Subtour wird hinter dem Knoten 5 in die Tourliste eingefügt (gelbe Pfeile).
Schritt 5: Es sind alle Verbindungen begangen worden, so dass die Tour komplett ist.
Beispiel 2: Startknoten 5
Wir wollen nun annehmen, dass Knoten 5 als Startknoten vorgegeben ist. Wie das folgende Bild und die darunter stehende Zeilendarstellung zeigen, sind in diesem Fall nur zwei Durchläufe der Schrittfolge 2 bis 5 notwendig, um die Eulertour zu finden.
Beispiel 3: Startknoten 10
Wenn Knoten 10 als Startknoten bestimmt wird, ist sogar nur ein Durchlauf der Schrittfolge nötig, wie die folgende Graphik und die darunter stehende Zeilendarstellung zeigen.
Eine VBA-Klasse zur Ermittlung von Eulertouren
Die nun folgende Klasse Eulertour kann zur Ermittlung von Eulertouren benutzt werden. Sie erstellt jedoch keine Graphiken, sondern liefert lediglich ein Array, das die anzulaufenden Knoten in der Reihenfolge der Tour enthält.
Die Klasse enthält drei mit Public deklarierte Funktionen, alle anderen Funktionen leisten nur Zuträgerdienste für diese drei Funktionen. Die öffentlichen Funktionen sind:
- Funktion isEulerian. Diese Funktion prüft, ob die als Parameter empfangene Adjazentmatrix m einen eulerschen Graphen repräsentiert, also einen, in dem Eulertouren möglich
sind.
- Funktion setGraph. Diese Funktion vom Typ Boolean liefert ein True, wenn der Graph, der von der übergebenen Adjazenzmatrix c repräsentiert wird, eulersch ist, sonst False. Um dies festzustellen, bemüht die Funktion die bereits erwähnte Funktion isEulerian. Der eigentliche Zweck der Funktion ist aber, die Adjazenzmatrix in die Instanzenvariable a zu überführen.
- Funktion tour. Dies ist die Kernfunktion der Klasse. Sie liefert die Tour in Form eines eindimensionalen Arrays. Die Funktion liefert nur dann ein sinnvolles Ergebnis, wenn vorher die Funktion setGraph ausgeführt wurde, weil diese die als Basisinformation notwendige Adjazenzmatrix installiert.
Innerhalb der Klasse repräsentiert die Instanzenvariable a den Graphen. Es handelt sich um ein zweidimensionales Integer-Array, welches die Adjazenzmatrix enthält. Für den Graphen aus den obigen Beispielen hätte die Adjazenzmatrix folgenden Aufbau:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
2 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
3 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
4 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
5 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
6 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
7 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
8 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
|
9 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
10 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
Steht in der Zelle, wo sich Zeile i mit Spalte j schneidet, eine 1, so gibt es eine Verbindung zwischen den Knoten i und j. Steht dort eine Null, so gibt es keine Verbindung. Die Matrix ist symmetrisch. Gibt es eine Verbindung zwischen den Knoten i und j, so gibt es natürlich auch eine Verbindung zwischen j und i.
Hier ist der Code der Klasse:
'Class Eulertour
'calculates Euler tours for an eulerian graph
'using a variation of the Hierholzer method
Option Explicit
Private a() As Integer 'adjacency matrix of the graph
Private t() As Integer 'node sequence of the tour
Private numNodes As Integer 'number of nodes
'accepts the adjacency matrix of the graph, checks whether it is
'eulerian and, if so, stores it in a; calculates numNodes
'--------------------------------------------------------------------------------------------
Public Function setGraph(ByRef c() As Integer) As Boolean
If isEulerian(c) Then
a = c
numNodes = UBound(c, 1)
setGraph = True
Else
setGraph = False
End If
End Function
'checks whether the graph given by adjacency matrix m is eulerian
'-----------------------------------------------------------------------------------------------
Public Function isEulerian(ByRef m() As Integer) As Boolean
isEulerian = True
Dim i As Integer, j As Integer, d As Integer
If UBound(m, 1) < 3 Then
isEulerian = False
Else
For i = 1 To UBound(m, 1)
d = 0
For j = 1 To UBound(m, 2)
d = d + m(i, j)
Next j
If d = 0 Or d Mod 2 <> 0 Then
isEulerian = False
Exit Function
End If
Next i
End If
End Function
'calculates the current degree of a node
'--------------------------------------------------------
Private Function numCons(ByVal node As Integer) As Integer
Dim i As Integer
numCons = 0
For i = 1 To numNodes
numCons = numCons + a(node, i)
Next i
End Function
'checks if there are still edges in the graph,
'i.e. edges which have not been deactivated
'--------------------------------------------------------------
Private Function edgesAvailable() As Boolean
Dim i As Integer, j As Integer, sum As Integer
edgesAvailable = False
sum = 0
For i = 1 To numNodes
For j = 1 To numNodes
sum = sum + a(i, j)
Next j
Next i
edgesAvailable = sum > 0
End Function
'composes an Euler tour starting from sNode
'----------------------------------------------------------------
Public Function tour(ByVal sNode As Integer) As Integer()
Dim i As Integer
Dim wpos As Integer 'position in t where next subtour will start
Dim s() As Integer 'subtour nodes without start node
Erase t
ReDim t(1 To 1)
t(1) = sNode
wpos = 1
s = subtour(t(1))
embed s, wpos
Do While edgesAvailable
wpos = searchWpos()
s = subtour(t(wpos))
embed s, wpos
Loop
tour = t
End Function
'creates a subtour, starting and ending at node from; the result
'array does not contain start node (= from)
'-----------------------------------------------------------------------------------------
Private Function subtour(ByVal from As Integer) As Integer()
Dim st() As Integer, num As Integer, nodeFree As Boolean
Dim nxt As Integer, curr As Integer
num = 0
nodeFree = True
curr = from
Do While nodeFree
nxt = nxtnode(curr)
If nxt = -1 Then
ReDim st(-1 To -1)
Exit Do
End If
If nxt = from Then nodeFree = False 'returned to start
num = num + 1
ReDim Preserve st(1 To num)
st(num) = nxt
a(curr, nxt) = 0 'deactivate edge
a(nxt, curr) = 0
curr = nxt
Loop
subtour = st
End Function
'searches a node which is reachable from node from;
'gives -1 if there is no such node
'---------------------------------------------------------------------------
Private Function nxtnode(ByVal from As Integer) As Integer
Dim i As Integer
nxtnode = -1
For i = 1 To numNodes
If a(from, i) = 1 Then
nxtnode = i
Exit For
End If
Next i
End Function
'search starting node for the next subround
'-----------------------------------------------------------
Private Function searchWpos() As Integer
Dim i As Integer
For i = 1 To UBound(t) - 1
If numCons(t(i)) > 0 Then
searchWpos = i
Exit Function
End If
Next i
searchWpos = -1
End Function
'embeds subtour s into tour array t after position behindPos
'--------------------------------------------------------------------------------------
Private Sub embed(ByRef s() As Integer, ByVal behindPos As Integer)
Dim oldlength As Integer
Dim i As Integer
oldlength = UBound(t)
ReDim Preserve t(1 To oldlength + UBound(s))
'make way for the subtour
For i = oldlength To behindPos + 1 Step -1
t(i + UBound(s)) = t(i)
Next i
'inserting nodes of subtour
For i = 1 To UBound(s)
t(i + behindPos) = s(i)
Next i
End Sub