Hauptübersicht

Klasse Graph

Klasse Graph: Graph (im Sinne der Graphentheorie)
Ein Graph besteht aus Knoten und Kanten. Eine Kante (Klasse Edge) verbindet zwei Knoten.
Kanten können auch mit einem Gewicht versehen werden.

Obwohl zur Graphendefinition keine geometrischen Informationen gehören, kann mathGUIde die Positionen von im Graphenfenster angeordneten Knoten speichern.

Übersicht:

Konstruktor

Graph ()

Klassenmethoden (statische Methoden)

MethodeBedeutung
complete (n, r=130, margin=20)Vollständiger Graph der Ordnung n angeordnet auf einem Kreis mit Radius r.
completeBipartite (n1, n2)Vollständiger bipartiter Graph mit den Partitionsgrößen n1 und n2.
example1 ()
fromShortRepr (s)Erzeugt den Graphen aus der Kurzdarstellung s
petersen (r=150, margin=20)Der Peterson-Graph

Operatoren

OperatorBedeutung
str(x)

Objektmethoden

MethodeBedeutung
addEdges (*edges)
addNodes (*nodes)
adjacent (node1, node2)Gibt an, ob node1 und node2 in G adjazent sind (bool).
adjacentNodes (node)Gibt eine sortierte Liste aller zu node adjazenten Knoten von G zurück.
cancelHighlight ()Setzt alle hervorgehobenen Kanten in den Normalzustand zurück.
complement ()Gibt den Graphen mit den gleichen Knoten wie G zurück, in dem sich zwischen zwei Knoten genau dann eine Kante befindet, wenn G dort keine Kante hat.
componentsCount ()Anzahl der Zusammenhangskomponenten des Graphen G
connectedNodes (node)Gibt eine Liste aller mit node durch einen Kantenzug verbundenen Knoten in G zurück (einschließlich node).
copy ()unabhängige Kopie von G
degree (node)Gibt den Grad des Knotens node (Anzahl der adjazenten Knoten) in G zurück
display (n=0)Zeigt den Graphen G im n-ten Graphen-Fenster an.
edge (node1, node2)Die Verbindungskante zwischen den zwei Knoten
highlightMinimalSpanTree (trace=False)Hebt einen minimalen aufspannenden Baum hervor (mit dem Kruskal-Algorithmus).
highlightShortestPath (startNode, goalNode)Hebt einen kürzesten Pfad von startNode nach goalNode hervor (mit dem Dijkstra-Algorithmus).
incidentEdges (node)
isConnected ()Gibt als Wahrheitswert zurück, ob der Graph G zusammenhängend ist
isTree ()Gibt als Wahrheitswert zurück, ob der Graph G ein Baum ist
isomorphic (H)Entscheidet, ob G und H isomorphe Graphen sind.
order ()Ordnung (Anzahl der Knoten) des Graphen G.
reduceToHighlightedEdges ()Entfernt alle nicht hervorgehobenen Kanten aus dem Graphen G.
shortRepr ()Kurzdarstellung des Graphen G (als String)

Konstruktor

Graph

Konstruktor

Aufruf: Graph()


Klassenmethoden (statische Methoden)

complete

Graph.complete(n, r=130, margin=20)

Aufruf: Graph.complete(n, r=130, margin=20)

Beschreibung:
Vollständiger Graph der Ordnung n angeordnet auf einem Kreis mit Radius r.


completeBipartite

Graph.completeBipartite(n1,n2)

Aufruf: Graph.completeBipartite(n1, n2)

Beschreibung:
Vollständiger bipartiter Graph mit den Partitionsgrößen n1 und n2.


example1

Graph.example1()

Aufruf: Graph.example1()


fromShortRepr

Graph.fromShortRepr(s)

Aufruf: Graph.fromShortRepr(s)

Beschreibung:
Erzeugt den Graphen aus der Kurzdarstellung s


petersen

Graph.completeBipartite()

Aufruf: Graph.petersen(r=150, margin=20)

Beschreibung:
Der Peterson-Graph
Er dient als Beispiel oder Gegenbeispiel für viele Probleme der Graphentheorie.


Operatoren

str(x)

Object representation as string

Aufruf: str(x)

Beschreibung:


Objektmethoden

addEdges

Aufruf: self.addEdges(*edges)


addNodes

Aufruf: self.addNodes(*nodes)


adjacent

G.adjacentNodes(node1, node2)

Aufruf: self.adjacent(node1, node2)

Beschreibung:
Gibt an, ob node1 und node2 in G adjazent sind (bool).


adjacentNodes

G.adjacentNodes(node)

Aufruf: self.adjacentNodes(node)

Beschreibung:
Gibt eine sortierte Liste aller zu node adjazenten Knoten von G zurück.


cancelHighlight

G.cancelHighlight()

Aufruf: self.cancelHighlight()

Beschreibung:
Setzt alle hervorgehobenen Kanten in den Normalzustand zurück.


complement

G.complement()

Aufruf: self.complement()

Beschreibung:
Gibt den Graphen mit den gleichen Knoten wie G zurück, in dem sich zwischen zwei Knoten genau dann eine Kante befindet, wenn G dort keine Kante hat.


componentsCount

G.componentsCount()

Aufruf: self.componentsCount()

Beschreibung:
Anzahl der Zusammenhangskomponenten des Graphen G


connectedNodes

G.componentsCount()

Aufruf: self.connectedNodes(node)

Beschreibung:
Gibt eine Liste aller mit node durch einen Kantenzug verbundenen Knoten in G zurück (einschließlich node).


copy

G.copy()

Aufruf: self.copy()

Beschreibung:
unabhängige Kopie von G


degree

G.degree(node)

Aufruf: self.degree(node)

Beschreibung:
Gibt den Grad des Knotens node (Anzahl der adjazenten Knoten) in G zurück


display

G.display(n=0)

Aufruf: self.display(n=0)

Beschreibung:
Zeigt den Graphen G im n-ten Graphen-Fenster an. Ist n = 0, wird der Graph im aktiven Graphen-Fenster angezeigt.


edge

G.edge(node1, node2)

Aufruf: self.edge(node1, node2)

Beschreibung:
Die Verbindungskante zwischen den zwei Knoten
Wenn node1 und node2 adjazent sind, wird die the Verbindungskante zurückgegeben, sonst None.


highlightMinimalSpanTree

G.minimalSpanTree(trace=False)

Aufruf: g.highlightMinimalSpanTree(trace=False)

Beschreibung:
Hebt einen minimalen aufspannenden Baum hervor (mit dem Kruskal-Algorithmus).
Wenn trace den Wert True hat, werden alle Schritte angezeigt.


highlightShortestPath

G.highlightShortestPath(startNode, goalNode)

Aufruf: self.highlightShortestPath(startNode, goalNode)

Beschreibung:
Hebt einen kürzesten Pfad von startNode nach goalNode hervor (mit dem Dijkstra-Algorithmus).
Die Länge des Pfades wird zurückgegeben (oder inf, falls keine Verbindung vorhanden).
Mit der Methode display können Sie die Hervorhebung sichtbar machen.


incidentEdges

Aufruf: self.incidentEdges(node)


isConnected

G.isConnected()

Aufruf: self.isConnected()

Beschreibung:
Gibt als Wahrheitswert zurück, ob der Graph G zusammenhängend ist


isTree

G.isTree()

Aufruf: self.isTree()

Beschreibung:
Gibt als Wahrheitswert zurück, ob der Graph G ein Baum ist


isomorphic

G.isomorphic(H)

Aufruf: .isomorphic(H)

Beschreibung:
Entscheidet, ob G und H isomorphe Graphen sind.


order

G.order()

Aufruf: self.order()

Beschreibung:
Ordnung (Anzahl der Knoten) des Graphen G.


reduceToHighlightedEdges

G.reduceToHighlightedEdges()

Aufruf: self.reduceToHighlightedEdges()

Beschreibung:
Entfernt alle nicht hervorgehobenen Kanten aus dem Graphen G.
Die Hervorhebung der verbleibenden Kanten wird zurückgenommen.


shortRepr

.shortRepr()

Aufruf: self.shortRepr()

Beschreibung:
Kurzdarstellung des Graphen G (als String)