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