graph-theory, Seitenzahl 1

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.

Antworten

Längster Pfad in einem bestimmten Grafiktyp

Ich weiß, dass das Problem mit dem längsten Pfad für ein allgemeines Diagramm NP-schwer ist. Ich betrachte jedoch eine bestimmte Art von Graphen, bestehend aus einem Zyklus plus einer zusätzlichen Kante, die auf jeden Eckpunkt des Zyklus einfä...

09.01.2013, 02:21

Antworten

Längste Kette, die arrangiert werden kann

Ich habe dieses Problem irgendwo in einem Wettbewerb gefunden und konnte noch keine Lösung finden. Ich habe die positiven ganzen Zahlen. Ich muss die längste Untermenge finden, die unter Je zwei Nachbarelemente trennt man ein anderes....

11.08.2015, 10:37

Antwort

Gibt es Online-Algorithmen für den Planaritätstest?

Ich weiß, dass Planaritätstest in O (v) durchgeführt werden kann (äquivalent zu O (e), seit planaren Graphen) habe O (v) Kanten) Zeit. Ich frage mich, ob es online in O (1) amortisierten Zeit getan werden kann, wenn jede Kante hinzugefügt w...

22.10.2009, 04:19

Antworten

Finde effizient jede Kombination von kleineren Bins zu größeren Bins

Nehmen wir an, ich habe 7 kleine Behälter, jeder Behälter hat die folgende Anzahl an Murmeln: %Vor% Ich weise diese kleinen Behälter zwei großen Behältern zu, die jeweils die folgende maximale Kapazität haben: %Vor% Ich möchte JEDE Kombi...

27.08.2015, 23:57

Antwort

Code Ausgabe auf Graph und einige Ansprüche auf lokalen Wettbewerb?

Ich stieß auf eine Frage wie folgt: Wir haben einen Code für den gewichteten, azyklischen Graph G(V, E) mit positiven und negativen Kanten. Wir ändern das Gewicht dieses Graphen mit folgendem Code, um eine G ohne negative Kante (G')...

06.05.2015, 09:54

Antworten

Liste der C ++ - Bibliotheken für die Graphentheorie [geschlossen]

Ich werde ein wissenschaftliches Projekt über Automaten- und Graphentheorie starten und suche nach einer Graphenbibliothek, die Funktionen wie folgt unterstützt: gerichtete / ungerichtete Graphen Graphisomorphismustest (d. h. ist graph g1...

16.04.2012, 09:06

Antwort

Algorithmus zum Erzeugen eines Zufallsnetzwerks

Was ist der beste Algorithmus zum Generieren eines zufälligen einfachen (nicht parallelen Kanten oder selbst-Schleifen) ungerichteten Graphen mit einer gegebenen Anzahl von Knoten, wobei jeder Knoten eine Anzahl von Kanten hat, die nicht kleiner...

24.06.2015, 19:00

Antworten

Was ist die Relaxationsbedingung in der Graphentheorie?

Ich versuche die Hauptbegriffe der Graphentheorie und der darin enthaltenen Algorithmen zu verstehen. Die meisten Algorithmen scheinen einen "Entspannungszustand" zu enthalten. Ich bin mir nicht sicher, was das ist. Könnte jemand mir das bitt...

07.04.2010, 13:28

Antworten

Berechnen Sie die minimale Anzahl von Swaps, um eine Sequenz zu sortieren

zuvor habe ich an der Sortierung einer ganzzahligen Sequenz ohne identische Zahlen gearbeitet (ohne Verlust der Allgemeinheit, angenommen, die Sequenz ist eine Permutation von 1,2,...,n ) in ihre natürliche aufsteigende Reihenfolge (d. h. 1,2...

01.03.2013, 07:00

Antworten

Wie kann ich das Konzept "Six Degrees of Separation" programmatisch nachweisen?

Ich habe eine Datenbank mit 20 Millionen Nutzern und Verbindungen zwischen diesen Leuten. Wie kann ich das Konzept des "Six grade of separation" -Konzepts am effizientesten in der Programmierung unter Beweis stellen? Link zum Artikel über S...

12.06.2009, 20:38