5
In einem gerichteten azyklischen Graphen mit n Vertices, wie groß ist die maximale Anzahl an gerichteten Kanten?Wie viele Kanten kann es in einer DAG geben?
A
Antwort
13
Nehmen Sie N Knoten/Knoten an und untersuchen wir, wie Sie eine DAG mit maximalen Kanten erstellen. Betrachten Sie einen gegebenen Knoten, sagen wir N1. Die maximale Anzahl von Knoten, auf die er in diesem frühen Stadium zeigen kann, oder Kanten, ist N-1. Wählen wir einen zweiten Knoten N2: er kann auf alle Knoten außer sich selbst und N1 zeigen - das sind N-2 zusätzliche Kanten. Fortfahren für verbleibende Knoten, jeder kann auf eine Kante weniger als der vorhergehende Knoten zeigen. Der letzte Knoten kann auf 0 andere Knoten zeigen.
Summe aller Kanten: (N-1) + (N-2) + .. + 1 + 0 == (N-1) (N)/2
+0
Vielen Dank für Ihre Antwort. – user1559262
+0
Hmm, [dies] (http://stackoverflow.com/questions/5058406/what-ist-the-maximum-number-of-edges-in-a-directed-graph-with-n-nodes) scheint zu streiten mit der Antwort. –
+5
@RealzSlaw Der Unterschied ist, dass eine DAG "azyklisch" ist; Der Beitrag, auf den Sie verweisen, behandelt im Allgemeinen gerichtete Graphen. –
Verwandte Themen
- 1. Wie viele Clustered-Indizes kann es in einer Tabelle geben?
- 2. Visualisierung einer DAG
- 3. Wie kann es eine Race Condition geben?
- 4. Dijkstra-Algorithmus vs entspannende Kanten in topologisch sortierten Graphen für DAG
- 5. Wie kann ich eine DAG in zufälliger Zeit starten?
- 6. Wie kann ich eine Grafik Knoten feste Position in graphviz geben und wie kann ich die Kanten nicht überlappt machen?
- 7. Wie kann es kein Arbeitsverzeichnis in git bare geben?
- 8. Wie konvertiert man ein Diagramm, das nicht DAG ist, in ein Diagramm, das DAG ist?
- 9. Geben Sie viele Zahlen mit raw_input()
- 10. Wie viele Tupel gibt es in einer Verbindung?
- 11. Wie viele Einträge gibt es in einer invertierten Seitentabelle?
- 12. Scheduling AirfFlow DAG Job
- 13. Was sind Leim- und Kettenabhängigkeiten in einer LLVM DAG?
- 14. Wie kann ich garantieren, dass eine DAG nach dem Einfügen eines Knotens azyklisch bleibt?
- 15. Wie viele Positionen gibt es?
- 16. Wie viele Einheiten sollte es in jeder Generation eines genetischen Algorithmus geben?
- 17. Ausführen von DAG wie Operationen in Scala Future
- 18. Wie kann ich viele Anfragen an Server in einer Zeit
- 19. AirFlow dag id Zugriff in Teilaufgaben
- 20. Wie viele Datensätze kann ich maximal in einer EntityCollection speichern?
- 21. Wie viele Zeitzonen gibt es?
- 22. Gibt es eine Java-Bibliothek zum Planen abhängiger Runnables (in einer Abhängigkeits-DAG angegeben)?
- 23. Wie kann ich alle Kanten in Monogame anzeigen?
- 24. Warum sind Kanten in einer Relay/GraphQL-Verbindung erforderlich?
- 25. Wie kann ich mehrere Funktionen in Form eines DAG zur Laufzeit kombinieren
- 26. Wie kann ich von einer Django-Vorlage auf die Eigenschaften einer Viele-zu-Viele-Tabelle zugreifen?
- 27. Entfernen abgerundete Kanten einer benutzerdefinierten Seekbar?
- 28. Wie kann ich in PyQT Knoten und Kanten zeichnen?
- 29. Wie kann ich viele URLs asynchron aus einer Liste aufrufen
- 30. Python: Kanten von Kanten erkennen und in ein Quadrat zuschneiden?
Diese Frage ist vom Thema für Stack-Überlauf . Sie könnten versuchen, http://math.stackexchange.com/ Mathe Fragen auf allen Ebenen zu begrüßen. –
Ganz zu schweigen davon, das hört sich nach einem Hausaufgabenproblem an. Und ich nahm den Köder: -/ –
Es ist auch ein Duplikat von [Wie kann ich die maximale Anzahl der Kanten beweisen?] (Http://math.stackexchange.com/questions/61579/how-can-i-prove- die maximale Anzahl der Kanten) –