Diskussion:Wald (Graphentheorie)

Grad eines Binärbaum

>Den Spezialfall eines Baumes, bei dem jeder Knoten vom Grad höchstens drei ist, nennt man Binärbaum. nicht Grad max. zwei? --Head 11:52, 23. Jun 2003 (CEST)

Nein, Grad 3! Ein Vorgänger und zwei Nachfolger! --Coma 14:01, 23. Jun 2003 (CEST)

Definition der Wurzel eines Baums in der Graphentheorie

Kann man etwas über die Wurzel eines Baums hier reinschreiben? Hab den Begriff in der Graphentheorie noch nie gehört, aber gehört ja irgendwie schon zum Thema. Bei Binärer Heap weiß ich nicht, wohin ich den Begriff Wurzel verlinken soll. --Head 11:52, 23. Jun 2003 (CEST)

Ja. Bei schlichten Graphen gibt es aber eigentlich keine ausgezeichnete Wurzel (nur bei gerichteten Graphen). Dies liegt daran, dass jeder Knoten als Wurzel fungieren kann. Man muss die Wurzel also explizit definieren. --Coma 14:01, 23. Jun 2003 (CEST)

Ich habe nun die Definition um den gerichteten Baum und den Wurzelbaum erweitert.--131.159.74.3 14:54, 28. Jun 2004 (CEST)

Definition in Wälder und Bäume in der Graphentheorie

Die folgende Diskussion habe ich von Benutzer Diskussion:Koethnig hierher kopiert. Ich hoffe hier beteiligen sich mehr Menschen an der Diskussion:--Anonym 20:24, 1. Dez 2004 (CET)

Um jetzt nicht einfach wieder meine eingefügten Verlinkungen herzustellen, möchte ich doch eine Erklärung. Out-Tree oder auch In-Tree ist in dem Artikel Wälder und Bäume in der Graphentheorie nicht erklärt, sie sind nicht unbedingt jedem geläufig und es gibt bereits Artikel dazu. Warum sollte man diese also nicht verlinken? --Anonym 19:16, 25. Nov 2004 (CET)

Hmm, vielleicht solltest du den Abschnitt "Gewurzelte Bäume" mal lesen... --Coma 23:53, 25. Nov 2004 (CET)

Meine schroffen Worte von gestern waren nicht so gemeint - ich wollte keinen Edit-War androhen, auch wenn's für mich jetzt so klingt, sorry!

Aber genau in diesen Abschnitt "Gewurzelte Bäume" habe ich doch die Links eingefügt, da diese Begriff Out-Tree und In-Tree zur Definition des gewurzelter Baum bzw. Wurzelbaum verwendet werden und nicht definiert. Oder liest Du in diesen Zeilen, daß In-/Out-Tree dort definiert wird? --Anonym 11:49, 26. Nov 2004 (CET)

also ich wollte auch keinen edit-war anfangen, aber mal ganz ehrlich, dort steht genau dass, was dazu zu sagen ist, und das ist genau die definition... vielleicht wäre es besser, wenn du versuchst zu erkären, was du dort nicht verstehtst, oder was dort missverständlich ist... --Coma 02:58, 28. Nov 2004 (CET)

Ich versuch's mal: Es geht ja um den Absatz:

• Ein gewurzelter Baum -- auch Wurzelbaum genannt -- ist ein gerichteter Graph mit einem ausgezeichneten Knoten, der so genannten Wurzel, für die gilt, dass im Falle von Out-Trees jeder Knoten durch genau einen gerichteten Pfad von diesem aus erreichbar ist oder dass im Falle von In-Trees dieser von jedem Knoten aus durch genau einen gerichteten Pfad erreichbar ist.

Wenn ich diesen mal ein bischen zerlegen darf, wird vielleicht die Struktur und damit der Inhalt deutlicher:

• Ein gewurzelter Baum' -- auch Wurzelbaum genannt -- ist ein gerichteter Graph mit einem ausgezeichneten Knoten, der so genannten Wurzel, für die gilt,

• dass im Falle von Out-Trees jeder Knoten durch genau einen gerichteten Pfad von diesem aus erreichbar ist oder
• dass im Falle von In-Trees dieser von jedem Knoten aus durch genau einen gerichteten Pfad erreichbar ist.

Die Definition von gewurzelter Baum wird also in 2 Fälle aufgeteilt. Die Fälle unterscheiden sich dadurch, daß der gerichtete Graph entweder ein Out-Tree oder ein In-Tree ist. Diese Begriffe werden aber in diesem Absatz nicht erklärt, sondern zur Definition von gewurzelter Baum verwendet. Sie werden aber in ihren eigenen Artikeln - die ich verlinkt hatte - definiert. Warum sollte man diese also nicht verlinken? Sind die Artikel Out-Tree und In-Tree überflüssig und sollten besser als rederict auf Wälder und Bäume in der Graphentheorie#Gewurzelte Bäume zeigen? Ich verstehe nicht, warum Dich diese Links stören; für mich fehlen sie! --Anonym 12:10, 1. Dez 2004 (CET)

OK, ich versuchs nochmal! Gewurzelte Bäume können entweder In-Trees oder Out-Trees sein, soweit kannst du mir offensichtlich folgen. Das alleine definiert schon die gewurzelten Bäume. Nat. muss man jetzt noch wissen, was In- bzw. Out-Trees sind. Und genau das steht oben! ...im Falle von Out-Trees... definiert dann Out-Trees und ...im Falle von In-Trees... definiert In-Trees. Der Satz davor gilt für Beide, also allg. für Wurzelbäume... Glaubst du mir jetzt, dass das eine Definition ist? Was weiß man über In- und Out-Trees danach nicht? --Coma 13:50, 1. Dez 2004 (CET)

Sorry, dazu fällt mir nichts mehr ein, daher versuche ich unter Diskussion:Wälder und Bäume in der Graphentheorie die Meinungen anderer dazu zu bekommen. Vielleicht noch ein anderer Ansatz: Sollte man nicht eigentlich möglichst viele Seiten untereinander verlinken? --Anonym 20:22, 1. Dez 2004 (CET)

Geht es jetzt bloß noch darum die eigene Änderung zu rechtfertigen oder gehts es darum den Artikel sinnvoll zu verbessern? Auch der neue Grund für die Verlinkung muss leider fehlschlagen, weil unter den dann verlinkten Artikeln nicht mehr steht als unter diesem hier. Es sind haargenau die selben Infos zu In- bzw. Out-Trees mit fast komplett dem selben Text. Der Inhalt der Artikel ist somit nur eine Teilmenge der hier gegebenen Informationen. Welchen Sinn macht da eine Verlinkung? --Coma 23:28, 1. Dez 2004 (CET)

Nein, es geht nicht um die eigene Änderung zu rechtfertigen sondern um den Artikel.Mit Deinen letzten Ausführungen hast Du die Artikel In- bzw. Out-Trees für überflüssig erklärt. Wie ich bei meiner letzten Antwort schon gesagt habe, fehlen mir einfach die Worte. Meine obige Zerlegung des Absatzes zeigt deutlich, daß diese umstrittenen Begriffe zur Definition von gewurzelter Baum verwendet werden und nicht selber definiert werden. Man könnte natürlich beides definieren:

• Ein gewurzelter Baum' -- auch Wurzelbaum genannt -- ist ein gerichteter Graph mit einem ausgezeichneten Knoten, der so genannten Wurzel, für die gilt,

• dass im Falle von Out-Trees, d. h. jeder Knoten ist durch genau einen gerichteten Pfad von dem ausgezeichneten Knoten erreichbar, jeder Knoten durch genau einen gerichteten Pfad von diesem aus erreichbar ist oder
• dass im Falle von In-Trees, d. h. von jedem Knoten aus ist der ausgezeichnete Knoten durch genau einen gerichteten Pfad erreichbar, dieser von jedem Knoten aus durch genau einen gerichteten Pfad erreichbar ist.

Das macht allerdings die Definition kaputt und sieht schon fast lächerlich aus. Vorschlag: Belassen wir es so wie es jetzt ist, bis eine dritte Person unseren 'Streit' schlichtet. --Anonym 19:40, 2. Dez 2004 (CET)

Nein, die Artikel zu In- und Out-Trees sind deswegen nicht überflüssig, weil sie nur jeweils eine Teilmenge dieses Artikels enthalten. Jemand der sich nicht für In-Trees interessiert, braucht dies bei Out-Trees nicht zu lesen. Wenn in irgend einem Artikel von Out-Trees die Rede ist, kann man dort ganz schnell nachschlagen was es ist. Wenn man diesen Artikel lesen müsste, würde man evtl. eine Menge unnützer Informationen bekommen. Dein Beispiel ist in der Tat lächerlich und deshalb steht es ja auch so nicht im Artikel drin. Versuche doch bitte noch eimal zu präzisieren, warum du dort keine Definition von In- und Out-Trees siehst bzw. wo das nun eigentlich das Problem ist (für den Fall das es eingentlich darum gar nicht geht?). --Coma 23:25, 2. Dez 2004 (CET)

Baum (Graphentheorie) und dieser Artikel

Baum (Graphentheorie) und dieser Artikel haben dieselbe Einleitung... Diesen Artikel als Übersichtsartikel anzulegen bedeutet ihn drastisch auf das wesentliche einzudampfen, bevor man dann in den Artikeln Wald und Baum auf die Details eingehen kann. Bevor alles revidiert wird und die Mühe vergebens ist, stehe ich mit der Auffassung allein da? --Bolliver 12:34, 18. Feb 2005 (CET)

Baum (Graphentheorie) soll nur die verschiedenen Varianten definieren. Hier soll man zusätzliche Infos dazu bekommen. Aber auch ich habe Probleme mit dem Ganzen. Historisch gab es diesen Artikel zuerst, dieser ging damals aber nicht auf gerichtete Bäume ein. Später habe ich mich in Form der zugehörigen Datenstruktur auch mit gerichteten Bäumen beschäftigt und die Einleitung davon hierher kopiert, weil sie allgemeiner war. Baum (Datenstruktur) wurde dann zu Baum (Graphentheorie), weil die Datenstruktur letztlich nichts anderes ist. Der ganze Bereich ist momentan etwas konfus. Vielleicht sollten diese ganzen Definitions-Artikel irgendwie durch das Glossar Graphentheorie ersetzt werden... --Coma 16:59, 18. Feb 2005 (CET)

Innerer Knoten als Redirect?

Hi, ich habe gerade in einem eigenen Artikel (Rot-Schwarz-Baum) den Begriff innerer Knoten verlinken wollen, und habe festgestellt dass dies ein Redirect auf diese Seite ist. Wenn ich auf der Suche nach einer einer Erklärung was ein innerer Knoten ist wäre, würde mir diese Seite hier jedoch nicht sehr viel helfen. Daher wollte ich anregen mal darüber nachzudenken ob wir hier nicht eventuell was zu Knoten in Bäumen allgemein aufnehmen wollen, oder ob wir den Redirect umbiegen sollten. Denn so wie es momentan ist freue ich mich dass ich einen blauen Link folgen kann, finde am anderen Ende aber nichts was in irgendeinem Bezug zu dem Link über den ich hierher gekommen bin hat. Regnaron 5. Jul 2005 19:39 (CEST)

Das liegt daran, dass noch niemand diesen Artikel angelegt hat und eigentlich ist es auch nicht erwünscht, da man dort nicht viel sinnvolles sagen kann, was an anderer Stelle besser aufgehoben wäre. Deshalb sollte eine kurze Definition in den Artikel Glossar Graphentheorie und der Redirect dorthin umgebogen werden. Analog mit all den anderen unzähligen Definitionen der Graphentheorie. Da es bisher noch niemand gemacht hat existiert halt die Notlösung einen Redirekt auf den Übersichtsartikel zu legen, wo der Begriff irgendwo erklärt wird (was für den Suchenden aber, wie du schon richtigerweise angemerkt hast, nicht befriedigend ist). Also nochmal kurz: Innerer Knoten auf Glossar Graphentheorie#innerer Knoten umleiten und dort eine kurze Definition angeben. --Coma 5. Jul 2005 20:49 (CEST)

Ah, danke für den Link. Kannte die Seite noch gar nicht. Dann werde ich mal ein paar Definitionen eintragen, und sehen ob ich nicht den ein oder anderen Link umbiegen kann. Danke Regnaron 5. Jul 2005 22:33 (CEST)

Nehmts mir bitte nicht uebel, aber das ist doch Unsinn. Die Wikipedia ist eine Enzyclopädie und kein Glossar. Oder wollen wir wirklich demnächst bei jedem Lemma erstmal auf ein Glossar verweisen?? Damit kann man jetzt garnichts mehr anfgangen. Wenn man Innerer Knoten nicht als eigensstaendigen Artikel haben moechte (und hier stimme ich zu), dann gehoert das Redirect auf Baum (Graphentheorie) und dort gehoert eine korrekte Definition eines Inneren Knoten hin.

Gruss -- sparti 6. Jul 2005 00:37 (CEST)

Vielleicht noch zur Verdeutlichung: Stellt Euch mal vor Ihr seid Schüler udn wollt wissen, was ein Innerer Knoten ist und dann findet Ihr das: Innerer_Knoten. Also ich wuerde meinen Rechner Ausschalten und lieber in die Bibliothek fahren. -- sparti 6. Jul 2005 00:39 (CEST)

Hi, sicherlich würden Baumbegriffe im Artikel über Bäume nicht deplatziert sein, aber wo genau ist der Unterschied ob ich es in einem Gloassarartikel definiere oder in einem "richtigen" Artikel? Der Inhalt wäre doch derselbe? Nur dass man beim Baum Artikel halt erst einmal suchen muss und nach und nach die Infos über die ganzen Definitionen findet, während man im Glossar direkt nachschlagen kann. Regnaron 6. Jul 2005 08:21 (CEST)

Also, ich sehe es genau andersherum. Wenn ich nach Inneren Knoten suche und bekomme ein herzlich abstraktes Glossar, wo auch noch eine Menge Zeug erklaert wird, das garnichts damit zu tun hat, dann faengt fuer mich die Suche erst richtig an. Wozu hat die Wikipedia denn eine Suchfunktion, wenn ich dann doch wieder nur eine lange Liste bekomme, in der ich dann doch wierum nur weitergeleitet werde?

Habe ich hingegen ein Redirect auf Baum und dort eine anschauliche und gut strukturierte Ubersicht, ueber Knoten und deren Beziehungen, dann brauche ich kein Glossar mehr. Noch eine These: Wenn ich nicht weiss, was ein Innerer Knoten ist, dann weiss ich auch nicht, was ein Blatt und eine Wurzel ist. Also muss ich eh, den ganzen Artikel lesen um alles zu verstehen. Ich gebe aber zu, dass der Baum Artikel heute nicht dafuer geeignet ist, da er sich ausschlichlich an den fachlich versierten Leser richtet und den Laien hoffnungslos ueberfordert. Das ist aber nicht Zweck einer Enzyklopaedie. Was wir brauchen ist ein anschaulicher Artikel, der dann auf auf die weiterfuehrenden Themen (gerichtet/ungerichtet/Graph, etc) verweist. Gruss -- sparti 6. Jul 2005 09:33 (CEST)

So einfach ist es in diesem Bereich aber leider nicht. Es gibt typischerweise zwei Arten von Nutzern im Bereich Graphentheorie. Leute die schon Erfahrung damit haben und solche die es nicht haben. Aufgrund der zahlreichen Definitionen die es in diesem Gebiet gibt, kann auch ein erfahrener Nutzer nicht jede Definition kennen und würde dann gerne mal in einem Glossar nachschlagen, wo er sofort alle nötigen Infos bekommte. Gibt es nur einen Redirekt auf Baum (Graphentheorie) bedeutet es für diese Nutzer sich durch riesige Artikel durchzukämpfen, um die Definition zu bekommmen. Wenn man 3 mal einen solchen Redirekt geliefert bekommen hat, sucht man sich andere Quellen und verzichtet auf Wikipedia. Zumal für den Gelegenheitsnutzer überhaupt nicht ersichtlich wird, dass der Artikel, auf den weitergeleitet wird die gesuchte Information (irgendwo) enthält. Nutzer, die mit Graphentheorie wenig vertraut sind, finden zunächst den kurzen Eintrag im Glossar und sollen bei weiteren Unklarheiten dort auf die Übersichtsartikel verwiesen werden, wo sie sich erstmal die nötigen Grundlagen aneignen können. Sicher brauchen wir nicht für alles ein Glossar, aber im Bereich Graphentheorie ist es einfach sinnvoll. 1000 Artikel (und soviele Begriffe gibt es in dem Bereich garantiert) auf max. 20 Übersichtsartikel weiterleiten zu lassen ist einfach nicht die richtige Lösung. Umgekehrt ist es noch sinnloser 1000 Artikel mit Informationen verfetten zu lassen, die der Nutzer selten braucht. --Coma 6. Jul 2005 11:44 (CEST)

Ich hab ausdruecklich geschrieben, dass ich nichts gegen ein Glossar habe. Aber Du mutest dem Anfgaenger zu, dass er sich durchklickt und dem erfahren Leser nicht und das passt eben nicht in eine Enzyclopaedie. Und dass man die Definition leicht findet ist immer noch eine Frage der Struktur, die bei dem jetzigen Baum Artikel wirklich schlecht ist. Vielleicht sollten wir die Zeit lieber investieren, diesen sauber zu strukturieren, ich denke dann ergibt sich die Diskusison von allein. Jedenfalls ist einem Anfaenger das Glossar nicht zumutbar.

Gruss -- sparti 6. Jul 2005 12:03 (CEST)

Das Glossar ist ja auch garnicht für den Anfänger! Der bekommt (soll das mal bekommen) im Glossar zu jedem Begriff auch einen Link auf den passen Übersichtsartikel, in dem alle zusammengehörenden Begriffe stehen, damit er sich gerade nicht durchklicken muss. Das Glossar ist für den erfahreneren Leser (und in der Regel verirren nur die sich in tiefere Gebiete der Graphentheorie). Ein Glossar kann sich für den Anfänger garnicht eignen, weil die Begriffe und Definitionen in der Graphentheorie aufeinander aufbauen. Das ist eben nicht wie in der Biologie oder anderen "Wissenschaften", wo man (fast) jeden Begriff für sich alleine erkären kann. Ich wüsste im übrigen nicht, wie man den Baum Artikel besser strukturieren kann?! Man könnte höchstens mehr "schwafeln" und mehr Bilder anbringen, damit der Laie mehr versteht. Aber die Struktur selber ist richtig. Obwohl der Inhalt des Baum-Artikels, wie schon andernorts gesagt, durch den Übersichtsartikel Wälder und Bäume in der Graphentheorie eigentlich abgedeckt ist (jedenfalls meiner Erinnerung nach) und eher eingestampft und ins Glossar verschoben werden kann oder dies irgenwann getan werden sollte. --Coma 6. Jul 2005 13:22 (CEST)

So, sehe gerade, dass fälschlicherweise Wälder und Bäume in der Graphentheorie eingestampft wurde... Naja, dann wirds eben wieder noch komplizierter... --Coma 6. Jul 2005 13:24 (CEST)

Definition

Hier schein mir einiges im Argen zu sein! Ich müsste mich sehr täuchen, aber ein Wald und ein azyklischer Graph sind doch nicht das selbe Ding! Aus dem ersten Satz den ersten beiden Sätzen des Artikels könnte man folgern, das jeder zusammenhängende azyklischer Graph ein Baum ist, das widerspricht jeder mir bekannten Definition! Habe ich ein Brett vor dem Kopf? Gruss -- 188.46.139.119 11:27, 6. Feb. 2010 (CET)

Keine ahnung wie ihr das definiert habt, aber ich kenne das zumindest als eine äquivalente Charakterisierung. --goiken 11:33, 6. Feb. 2010 (CET)

Schau dir mal das Bild rechts (aus dem englischen Artikel zu "Directed acyclic graph"). Das ist ein zusammenhängender, azyklischer Graph, oder? Aber es ist doch kein Baum! Der zweite Satz dieses Artikels impliziert aber genau das!

An example of a directed acyclic graph

Gruss, -- 188.46.139.119 11:54, 6. Feb. 2010 (CET)

Stimmt. bei gerichteten geht das nicht gut.--goiken 11:56, 6. Feb. 2010 (CET)

Also Diestel (Seite 27) kennt die als kreisfrei ungerichtet.--goiken 12:01, 6. Feb. 2010 (CET),

Stimmt, bei ungerichteten gehts! Es gibt aber doch sicher auch gerichtete Wälder (das wäre dann m.A. nach eine Menge aus disjkunkten gerichteten Bäumen). Der Artikel geht auf diese nicht ein, obwohl er auf den Unterschied zwischen gerichteten und ungerichteten Bäume eingeht! (nicht signierter Beitrag von 188.46.139.119 (Diskussion | Beiträge) 12:09, 6. Feb. 2010 (CET))

Ich glaub wir hatten damals gerichtete wälder/bäume aud ungerichtete zugrundeliegende zurückgeführt. Also zum testen die orientierung vergessen und schauen, obs ein baum ist.--goiken 12:13, 6. Feb. 2010 (CET)

Ich hab die Eineitung jetzt geändert! Tatsächlich ist "azyklischer Graph" immer die Übersetzung für "acyclic directed graph (dag)" - was eben ganz was anderes als ein (gerichteter) Baum/Wald ist. Für kreisfreie ungerichtete Graphen wird immer der Begriff Baum (falls auch zusammenhängend - was ja der Normalfall ist, auf den fast alles zurückgeführt wird) oder eben Wald benutzt - "kreisfreier Graph" braucht man als Begriff dann nicht mehr, wenn man die Dinger einmal Wald oder Baum genannt hat. Graf Alge (Diskussion) 01:27, 19. Okt. 2015 (CEST)

Hier ist auf jeden Fall einiges im Argen.

Zur Einleitung: Stand heute steht da wieder, dass azyklische Graphen Wälder sind, und das ist falsch. Ein Wald ist ein Graph, dessen Zusammenhangskomponenten Bäume sind. Das ist in ungerichteten Graphen äquivalent zur Kreisfreiheit, in gerichteten Graphen eben nicht. Der Übergang zum Wurzelbaum ist relativ erratisch, solange man nicht sauber zwischen gerichteten und ungerichteten Graphen unterscheidet.

Bei "Algorithmen auf Wäldern" ist die Kernaussage wackelig, und das Beispiel schlecht: Heapsort nutzt als Datenstruktur typischerweise keinen Baum, sondern ein Array. Und der Vergleich mit InsertionSort ist schwach, denn es gibt ja auch andere, nicht graphentheoretisch inspirierte Sortieralgorithmen, die so schnell sind wie HeapSort (z.B. Mergesort).

In "Sonderrolle" steht, dass Ergebnis einer Breiten- oder Tiefensuche sein ein spannender Baum. Das stimmt nur für zusammenhängende Graphen. Man bekommt entweder einen nicht-spannenden Baum oder einen Wald, je nachdem, ob man die Suche mehrfach startet.

In "Aussagen" steht über einen Wald "Eine Bipartition bekommt man, indem man die Knoten bezüglich ihrer Distanz modulo 2 zu einem beliebig, fest gewählten Knoten zusammenfasst." Das geht in einem Baum, aber da ein Wald nicht im zwangsläufig zusammenhängt, muss man die Bäume einzeln färben, weil im allgemeinen gar nicht alle Knoten eine Distanz zu einem beliebigen, fest gewählten Knoten haben. --62.216.210.0 09:47, 18. Mär. 2022 (CET)

Wald, nur ungerichtet?

Die Definition enthielt bisher nur ungerichtete Graphen. Dies steht im Widerspruch zur jetzt angegebenen Definition nach Diestel und zur Ausführung weiter unten bzgl topologischer Sortierung. --DixMartin (Diskussion) 22:31, 30. Jan. 2020 (CET)