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:
Graph ()
Methode | Bedeutung |
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 |
Operator | Bedeutung |
str(x) |
Methode | Bedeutung |
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
Aufruf: Graph()
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.
Graph.completeBipartite(n1,n2)
Aufruf: Graph.completeBipartite(n1, n2)
Beschreibung:
Vollständiger bipartiter Graph mit den Partitionsgrößen n1 und n2.
Graph.example1()
Aufruf: Graph.example1()
Graph.fromShortRepr(s)
Aufruf: Graph.fromShortRepr(s)
Beschreibung:
Erzeugt den Graphen aus der Kurzdarstellung s
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.
Object representation as string
Aufruf: str(x)
Beschreibung:
Aufruf: self.addEdges(*edges)
Aufruf: self.addNodes(*nodes)
G.adjacentNodes(node1, node2)
Aufruf: self.adjacent(node1, node2)
Beschreibung:
Gibt an, ob node1 und node2 in G adjazent sind (bool).
G.adjacentNodes(node)
Aufruf: self.adjacentNodes(node)
Beschreibung:
Gibt eine sortierte Liste aller zu node adjazenten Knoten von G zurück.
G.cancelHighlight()
Aufruf: self.cancelHighlight()
Beschreibung:
Setzt alle hervorgehobenen Kanten in den Normalzustand zurück.
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.
G.componentsCount()
Aufruf: self.componentsCount()
Beschreibung:
Anzahl der Zusammenhangskomponenten des Graphen G
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).
G.copy()
Aufruf: self.copy()
Beschreibung:
unabhängige Kopie von G
G.degree(node)
Aufruf: self.degree(node)
Beschreibung:
Gibt den Grad des Knotens node (Anzahl der adjazenten Knoten) in G zurück
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.
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
.
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.
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.
Aufruf: self.incidentEdges(node)
G.isConnected()
Aufruf: self.isConnected()
Beschreibung:
Gibt als Wahrheitswert zurück, ob der Graph G zusammenhängend ist
G.isTree()
Aufruf: self.isTree()
Beschreibung:
Gibt als Wahrheitswert zurück, ob der Graph G ein Baum ist
G.isomorphic(H)
Aufruf: .isomorphic(H)
Beschreibung:
Entscheidet, ob G und H isomorphe Graphen sind.
G.order()
Aufruf: self.order()
Beschreibung:
Ordnung (Anzahl der Knoten) des Graphen G.
G.reduceToHighlightedEdges()
Aufruf: self.reduceToHighlightedEdges()
Beschreibung:
Entfernt alle nicht hervorgehobenen Kanten aus dem Graphen G.
Die Hervorhebung der verbleibenden Kanten wird zurückgenommen.
.shortRepr()
Aufruf: self.shortRepr()
Beschreibung:
Kurzdarstellung des Graphen G (als String)