Diskussion:Spannbaum

Was ich wirklich HASSE

Ich hasse es wirklich wenn in einer Enzyklopädie, die für (formulieren wir es freundlich) unbedarft Nutzer gedacht ist mathematische Formel OHNE jegliche Erklärung angegeben sind. Diese Abschnitte sind für jeden nicht mathematische Gebildeten User Black-Boxes die ebensogut entfallen könnten, da hier kein Mehrwert gebildet sondern ausschließlich für verwirrung gesorgt wird. (nicht signierter Beitrag von 194.25.15.217 (Diskussion) 13:40, 26. Feb. 2008)

Begriff Spannbaum oder Aufspannender Baum

Sollte es nicht Spannbaum und nicht spannender Baum heißen? Zum einen kenne ich nur den Begriff Spannbaum, zum anderen wäre das Gegenteil von einem spannenden Baum sonst ein langweiliger Baum :-) Stern 17:22, 16. Mär 2004 (CET)

Ich kenne es fast nur so, und minimaler Spannbaum klingt ungewohnt. Aber ich glaube man kann beides sagen. --Coma 23:39, 16. Mär 2004 (CET)

Spannend halte ich für einen falschen Freund Stern !? 10:30, 9. Dez 2004 (CET)

Nein, spannend steht hier kurz für aufspannend. --Coma 14:43, 9. Dez 2004 (CET)

In dem Artikel heisst es, ein "Gerüst" ist ein aufspannender Wald. AFAIK ist aber "Gerüst" der ursprüngliche deutsche Begriff für Spannbaum, da früher Gerüst mangels eines besseren Begriffs im Englischen als "spanning tree" übersetzt wurde, was es als "spannender Baum" wieder ins Deutsche geschafft hat. Quelle: Siehe Kruskals bekannte Veröffentlichung von 1956 ("On the shortest spanning subtree and the traveling salesman problem"). (nicht signierter Beitrag von T-fisch (Diskussion | Beiträge) 21:33, 9. Aug. 2005)

Ich möchte mich meinem anonymen Vorredner anschließen. Das ganze sollte mal auf die richtigen Fachausdrücke geändert werden. Ich habe noch nie einen Graphentheoretiker von "spannenden Bäumen" reden gehört. Außer wenn sie eben auf genau diesen Übersetzungsfehler hingewiesen haben. Der "schlichte Graph" ist übrigens auch so ein Fall. -- MlaWU 21:45, 1. Dez 2005 (CET)

Bei den Begriffen Spannbaum und "spannender Baum" handelt es sich meiner Meinung nach um Anglizismen. Ich werde am Wochenende mal etwas nachforschen und dann eine Korrektur vornehmen. -- Dirk 12:54, 3. Apr. 2007 (CEST)

In der Tat findet man in der deutschen Literatur häufig den Begriff Spannbaum für "aufspannender Baum", so z.B. in Diestel, Graphentheorie: http://www.emis.de/monographs/Diestel/de/GraphentheorieII.pdf

Welches die ursprüngliche deutsche Bezeichnung ist, konnte ich nicht so einfach klären. Ich halte Spannbaum aber für eine schlechte Begriffsbildung, weil sie nicht nur mehrdeutig ist, sondern sogar semantisch in die falsche Richtung führt: Ein Spannbaum ist schließlich nicht spannend, sondern aufspannend oder meinetwegen auch erzeugend. Da man beide Begriffe in der Literatur findet, schlage ich vor, zumindest in Wikipedia die sinnstiftendere zu benutzen.

Bevor ich nun einfach die Seite hier ändere, bitte ich Euch um Meinungen dazu. -- Dirk 13:37, 5. Apr. 2007 (CEST)

Eben weil beide Begriffe in der Literatur verwendet, sollte zumindest erwähnt werden, dass ein aufspannender Baum auch als Spannbaum bezeichnet wird. 82.207.193.26 09:47, 22. Jun. 2007 (CEST)

Ich bin dafür, den "spannenden Baum" endlich als lustige Fehlübersetzung aus dem Artikel zu verbannen. --oreg 21:10, 6. Apr. 2008 (CEST)

Ich habe den Begriff jetzt im Artikel zumindest mal als falschen Freund gekennzeichnet. --Oreg (Diskussion) 00:30, 13. Jul. 2012 (CEST)

Parser Fehler?

Da hat es wohl ein (temporäres?) Problem mit den Formeln. (nicht signierter Beitrag von 84.58.196.147 (Diskussion) 10:48, 14. Feb. 2006)

Definition von V und E

Eine Effizenz von V*log(V)+E ist ja klasse aber was is V und was ist E ??? -- A1000 14:09, 9. Feb. 2009 (CET)

V ist im Normalfall die Menge der Knoten, E jene der Kanten (nach Englisch: Vertices / Edges) -- 188.62.169.39 13:50, 26. Mai 2010 (CEST)

Das ist eine berechtigte Frage. Ich habe eine Definition eingefügt. --Oreg 11:40, 2. Mai 2011 (CEST)

Inkonsistente Laufzeitkomplexität

Auf der Seite von Prims Algorithmus steht, dass mittels AF-Heaps eine Laufzeit in O(|E|+|V|) möglich ist, auf dieser Seite aber, dass |V|log|V| + |E| optimal seien. Was stimmt denn nun, bzw. weiss jemand eine Quelle, welche das Sortierargument bestätigt? -- 188.62.169.39 13:50, 26. Mai 2010 (CEST)

Ungerichteten Graphen

"Graphentheorie ein Teilgraph eines ungerichteten Graphen" Der Graph kann doch auch gerichtet sein!!!??? (nicht signierter Beitrag von 217.50.183.18 (Diskussion) 15:32, 27. Apr. 2011 (CEST))

Ich spreche mich auch dafür aus, zu der Notwendigkeit des Ungerichtet-Seins einen Satz einzufügen GitR (Diskussion) 02:50, 17. Jun. 2014 (CEST)

(auf)spannend

Hallo Oreg, um "auch aufspannender Baum" und "auch spannender Baum", mit einer dazwischengequetschten englischen Bezeichnung, zusammenzufassen, braucht man keine Diskussionsseite bemühen, und ich verstehe nicht, wie man das als keine offensichtliche Verbesserungen bezeichnen kann. Deine Revertierungen bringen nicht nur keine offensichtlichen Verbesserungen, sondern sogar offensichtliche Verschlechterungen. Bitte beachte: auch eine minimale Verbesserung an einem Artikel kann nicht einfach kommentarlos zurückgesetzt werden, das entspricht nicht dem gepflegten Umgang in der Wikipedia. Falls du dennnoch meinst, an meiner Änderung sei etwas falsch, dann erwähne das bitte hier oder in der Zusammenfassungszeile. Vielen Dank. --androl ☖☗ 14:53, 26. Mai 2011 (CEST)

Hallo Androl, zunächst mal ist es an dem, der den Artikel ändert, dies zu begründen -- spätestens wenn die Änderungen auf Widerstand stoßen. In dem Fall sollte man die Sache erst diskutieren (wie ich schon in der Zusammenfassungszeile schrieb) und sie nur wieder einfügen, wenn man sich geeinigt hat. Nach meiner Erfahrung ist das das übliche Vorgehen in der WP.

Zur Sache: Aus den obigen Diskussionen wird klar, dass die korrekte deutsche Bezeichnung eines spanning tree durchaus umstritten ist. Es hat sich ein Kompromiss herausgebildet, dass "spannender" Baum zwar eine fragwürdige Übersetzung ist, sie jedoch bis auf weiteres im Artikel erwähnt wird, da sie in der Literatur gelegentlich verwendet wird. Das sollte durch die Nachstellung mit "auch" deutlich gemacht werden.

Deine Änderung stellt dieses Verhältnis -- sicherlich ohne Absicht -- auf den Kopf. Die Klammerung von "auf" erweckt den Eindruck, dass die Variante ohne "auf", also "spannender Baum" die üblichere ist. Das ist es, womit ich nicht einverstanden bin. (Ich hätte versuchen sollen, das in der Zusammenfassungszeile zum Ausdruck zu bringen.)

Falls Du eine Idee hast, wie man das alles eleganter lösen kann, ohne die Aussage zu ändern, würde ich das unterstützen. Ich hoffe, Du verstehst jetzt, dass ich bis dahin den alten Zustand wiederherstelle.

Grüsse, --Oreg 21:32, 26. Mai 2011 (CEST)

Optimalität des Algorithmus' von Prim

Bis vor kurzem stand folgender Satz im Artikel:

„Es kann gezeigt werden, dass der Algorithmus von Prim optimal ist, da mit seiner Hilfe auch Zahlen sortiert werden können.“

Nun hat ein Edit den Satz entfernt mit der Begründung:

„Prims Algorithmus ist nicht optimal für das MST-Problem. Das Argument, dass mit Prim auch Zahlen sortiert werden können, zeigt lediglich, dass die Laufzeitanalyse scharf ist. Ein besserer Algorithmus von Chazelle (2000) ist bereits bei der Liter…“

Meinungen? Vielleicht will jemand den Algorithmus von Chazelle in den Artikel einarbeiten? --Oreg 15:04, 9. Jan. 2012 (CET)

Definition des Spannbaumes

Woher stammt die Definition des Spannbaumes? Ich finde sie schön, nur würde ich mich wohler fühlen, wenn dafür eine Quelle vorhanden wäre. Im Cormen und Sedgewick steht z.B. nicht (explizit) die Einschränkung, dass es ein ungerichteter Graph sein muss. (Obwohl nur ungerichtete Graphen dargestellt werden.) --Martin Thoma 20:23, 12. Jul. 2012 (CEST)

Hallo Martin, das ist ein guter Punkt. Die englische WP sagt dazu: "For directed graphs, the minimum spanning tree problem is called the Arborescence problem and can be solved in quadratic time using the Chu–Liu/Edmonds algorithm."[1] Ich habe mal einen Verweis in den Artikel eingebaut. --Oreg (Diskussion) 00:48, 13. Jul. 2012 (CEST)

Grafik der 16 Spannbäume

Meine Studierenden haben darauf hingewiesen, dass in Zeile 3 der erste und dritte Spannbaum identisch sind. Der dritte Spannbaum müsste gespiegelt werden, damit das Bild korrekt ist. (nicht signierter Beitrag von Thekrs (Diskussion | Beiträge) 09:17, 20. Mai 2021 (CEST))