graph-theory

Ein Graph ist eine mathematische Struktur, die eine Sammlung von Scheitelpunkten oder "Knoten" und eine Sammlung von Kanten enthält, die Paare von Scheitelpunkten verbinden. Graphen können ungerichtet oder gerichtet sein, Kanten können von einem Scheitelpunkt zum anderen gerichtet sein.
6
Antworten

Implementieren eines zufällig generierten Labyrinths mit Prims Algorithmus

Ich versuche ein zufällig generiertes Labyrinth mit dem Prim-Algorithmus zu implementieren. Ich möchte, dass mein Labyrinth so aussieht: aber die Labyrinthe, die ich aus meinem Programm erzeuge, sehen so aus: Ich bin gerade dabei,...
20.04.2015, 05:13
3
Antworten

Erstellen oder Suchen einer Vorschlagsfunktion für relevante Begriffe

Nach ein paar Worten möchte ich ein Dienstprogramm haben, das eine Vielzahl relevanter Begriffe, Sätze oder Konzepte zurückgibt. Ein Vorbehalt ist, dass es zu Beginn einen großen Termgraphen haben müsste, sonst wäre das Feature nicht sehr nützli...
21.02.2009, 01:56
4
Antworten

Gibt es schnellere Algorithmen als Dijkstra?

Gibt es einen gerichteten, verbundenen Graphen mit nur positiven Kantengewichten, gibt es schnellere Algorithmen, um den kürzesten Weg zwischen zwei Scheitelpunkten zu finden, als Dijkstra mit einem Fibonacci-Haufen? Wikipedia sagt, dass Dijk...
09.11.2009, 14:16
3
Antworten

Algorithmus zur Bestimmung, ob 2 Graphen isomorph sind

Disclaimer: Ich bin ein absoluter Neuling in der Graphentheorie und ich bin mir nicht sicher, ob das auf SO, Mathe SE, etc. gehört Wie kann ich, wenn zwei Adjazenzmatrizen A und B gegeben sind, feststellen, ob A und B isomorph sind? Zum Be...
06.10.2010, 19:58
4
Antworten

Algorithmen zur Identifizierung aller Zyklusbasen in einem ungerichteten Graphen

Ich habe ein ungerichtetes Diagramm mit Vertex V und Edge E . Ich suche nach einem Algorithmus, um alle Zyklusgrundlagen in diesem Diagramm zu identifizieren. Ich denke, Tarjans-Algorithmus ist ein guter Anfang. Aber die Referenz , di...
22.10.2009, 13:17
2
Antworten

Welche Bedeutung hat die Semi-Clustering-Formel in der Google Pregel-Arbeit?

Der Semi-Clustering-Algorithmus wird im Google Pregel-Dokument erwähnt. Der Score eines Semi-Clusters wird mit der folgenden Formel berechnet wo Ic ist die Summe der Gewichte aller inneren Kanten Bc ist die Summe der Gewichte aller...
02.07.2012, 12:42
3
Antworten

Wie man die Adjazenzmatrix mit MATLAB graphisch darstellt

Ich möchte ein Diagramm erstellen, das Verbindungen zwischen Knoten aus einer Adjazenzmatrix wie der folgenden zeigt. gplot scheint das beste Werkzeug dafür zu sein. Um es zu verwenden, muss ich jedoch die Koordinaten jedes Knotens über...
07.12.2014, 05:26
4
Antworten

Ermitteln aller kürzesten Pfade von jedem Knotenpaar in einem Diagramm

Ich habe etwa 70.000 Knoten und 250.000 Kanten, und der Graph ist nicht notwendigerweise verbunden. Offensichtlich ist die Verwendung eines effizienten Algorithmus entscheidend. Was empfehlen Sie? Als Nebenbemerkung würde ich mich darüber fre...
10.03.2010, 23:57
3
Antworten

Algorithmus zum Finden der kleinsten Sammlung von Komponenten

Ich suche nach einem Algorithmus, um das folgende Problem zu lösen. Ich habe eine Anzahl von Teilmengen (1-n) einer gegebenen Menge (a-h). Ich möchte die kleinste Sammlung von Teilmengen finden, die es mir ermöglichen, alle gegebenen Teilmengen...
07.01.2014, 20:43
2
Antworten

Algorithmus zum Lösen dieses verteilenden Perlenpuzzles?

Nehmen wir an, Sie haben einen Kreis (wie unten) mit N Punkten und Sie haben N Perlen in den Slots verteilt. Hier ist ein Beispiel: Jede Perle kann im Uhrzeigersinn für X Schlitze verschoben werden, was X ^ 2 Dollar kostet. Ihr...
21.02.2016, 01:29