Diskussion:Baum (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 2 Jahren von YasinGiray in Abschnitt k-Bäume
Zur Navigation springen Zur Suche springen

wäre es nicht gut, diverse Implementierungen / Konverter anzugeben?!

Antwort: Ich verstehe nicht welche Seiten du meinst. Nenne mal ein Beispiel. In den meisten Programmierkursen wird den Leuten doch beigebracht wie man Bäume implementiert. (Und bitte lass überflüssige Ausrufezeichen in der Überschrift weg. So wichtig ist der Punkt dann auch nicht.) --Squizzz 11:32, 26. Aug 2005 (CEST)

In "Gewurzelte Bäume, Definition"

[Quelltext bearbeiten]

Könnte bitte jemand, der sich damit auskennt, den folgenden Satz korrigieren:

"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."

Entweder: "ausgezeichneter Knoten ..., für den gilt..."

oder: "... die Wurzel, für die gilt ... durch genau einen Pfad von dieser aus erreichbar ..."

Oder ist etwas vollkommen anderes gemeint?

-- Peter, 80.133.124.237 16:37, 25. Jan 2005 (CET)

den war richtig, danke für den Hinweis... --Coma 17:02, 25. Jan 2005 (CET)

--84.151.180.28 20:03, 31. Okt 2005 (CET) Wenn ich es inhaltlich richtig verstanden habe, könnte man diesen Satz durch eine Grafik wesentlich verständlicher machen. Also: mit Pfeilen nach unten also von der Wurzel weg (Out-Trees) und mit Pfeilen nach Oben zu der Wurzel hin (In-Trees).

Erster Satz

[Quelltext bearbeiten]

Dieser und viel andere ähnliche Artikeln beginnen mit "Ein XYZ ist in der Graphentheorie ein spezieller Graph. Das ist so sehr unbefriedigend wie "Ein PKW ist ein spezielles Fortbewegungsmittel". Es sollte in der Einleitung auch kurz angerissen werden, was das besondere an dieser art Graph ist, in welchem speziellen Fachgebiet er warum und wofür genutzt wird - eben wie bei PKW. -- RainerBi 08:21, 11. Mär 2005 (CET)

Wie der Satz schon sagt, ist das Fachgebiet die Graphentheorie! Das besondere steht in der Definition kurz nach dem Abschnitt! Genutzt wird er für alle mögliche und darum ist es nicht sinnvoll das in der Einleitung zu sagen. --Coma 20:42, 11. Mär 2005 (CET)

Ich bin sehr einverstanden it dem ersten Kommentar. Ich schlage daher eine entsprechende Änderung vor. Der Hinweis auf die Monohierarchie ist als Einleitung nicht hilfreich. (nicht signierter Beitrag von 138.190.32.7 (Diskussion) 09:54, 15. Jan. 2016 (CET))Beantworten

Ungerichtete Bäume, Definition

[Quelltext bearbeiten]

Stimmt denn Definition 5? Ich meine, wenn ich einen Graphen ABCDA habe und eine Kante BD hineinzeichne, entsteht ein Kreis ABDA, ohne dass ABCDA ein Baum wäre.--Mzapf 17:55, 17. Okt 2005 (CEST)

Nöö, hat nicht gestimmt. --Coma 18:02, 17. Okt 2005 (CEST)

Baumtypen

[Quelltext bearbeiten]

Es gibt ja auch noch weitere Baumtypen. Wie steht es zum Beispiel mit B-Bäumen in verschiedenen Variationen, Splay-Trees, Anwendungen von Bäumen als Gerüste von Graphen, z.B. minimale Spannbäume (Algorithmus von Kruskal) ? Sicherlich sind die hier angeführten Beispiele meist einen eigenen Artikel wert, sowie es zum Teil auch schon Artikel dazu gibt. Dennoch meine ich, dass zumindest Hinweise darauf sinnvoll sind. Allerdings bin ich noch recht neu hier, so dass ich bei der Abänderung von Artikeln eher zurückhaltend bin...

mfg, Paschelino*

Bestehende Artikel: B-Baum, Algorithmus von Kruskal

--Paschelino 16:47, 7. Dez 2005 (CET)

Und auch Entscheidungsbäume, zu welchen ich hier mal einen Link eingefügt hatte und welcher wieder gelöscht wurde, aus meiner Sicht unverständlich, sind doch Entscheidungsbäume fester Bestandteil der Spieltheorie und in Algorithmen der künstlichen Intelligenz, z.B. dem Minimax-Algorithmus (siehe auch Und-Oder-Baum).

--In4matic 09:23, 15. Okt. 2008 (CEST)Beantworten

In der generativen Linguistik wird, grob gesagt, davon ausgegangen, dass Syntax natürlicher Sprachen in assymentrischen Binärbäumen organisiert ist. Ich kenne mich mathematisch zu wenig aus, um das hier sinnvoll einzubauen, aber Graphentheorie und Sprachwissenschaft hängt eng genug zusammen, um da Verweise einzubauen.

Man koennte noch einbringen, dass in der Informatik Baeume stets nach unten wachsen und dazu ein schoenes umgedrehtes Bild eines echten Baumes zeigen. Wer sich jetzt fragt wieso eigentlich, der sollte mal versuchen einen riesigen Info-Baum von unten nach oben auf ein Blatt Papier zu malen! ;-)

Also, ich will nur ein OK von euch, dass ich das machen soll. --noLo aba G MacWee 13:09, 8. Jul 2006 (CEST)

Erstens ist es Unsinn, denn höchstens die Darstellung auf Papier oder ähnliches hat eine Richtung im Raum. Zweites malt man Bäume auch gerne mal von "unten nach oben". --Koethnig 10:23, 10. Jul 2006 (CEST)

Natuerlich wachsen Baume _im_ Computer irgendwohin. Koenntest Du mal ein Beispiel bzw. eine Aufzeichnung zeigen, wo man einen Info-Baum von unten nach oben aufbaut?

Nochmal, es gibt im Computer kein oben und kein unten (außer du definierst es und das kann ich mir dann ja definieren wie ich will). Zweitens gibt es unabhänig davon Top-Down- und Bottom-Up-Verfahren, aber auch dort ist oben und unten nur etwas in der entsprechenden Vorstellung der betrachtenden Person, die bewußt oder unbewußt ein oben oder unten definiert hat! --Koethnig

Okay, hat sich erledigt. Es gibt tatsächlich Bäume, die von oben noch unten gemalt werden und wo die Wurzel unten ist. Beispielsweise beim Huffman-Algorithmus. --noLo aba G MacWee 19:56, 25. Jul 2006 (CEST)

Frage zu "Äquivalente Charakterisierungen von Bäumen"

[Quelltext bearbeiten]

Ich habe lange an diesem Abschnitt geknabbert. Beim Formulieren meiner "Kritik" hier habe ich diese immer und immer wieder umgestellt. Ich formuliere deshalb jetzt mal ganz vorsichtig: Für mein Gefühl fehlt hier eine Definition. Der Abschnitt, zu dem ich hier schreibe, könnte implizit eine Definition sein, und vielleicht ist das die Ursache. Die Aussage „… sind äquivalent“ impliziert für mich, dass die Aussage „G ist ein Baum.“ bereits eine eigene Bedeutung besitzt. Ich finde außerhalb des Abschnittes aber keine Definition. Mein Vorschlag – für den Fall, dass nicht doch woanders eine Definition zu finden ist – wäre, wenigstens die Aussage „… sind äquivalent“ zu ersetzen durch „Ein Baum G kann durch folgende äquivalente Bedingungen definiert werden:“. Damit wüsste man auf den ersten Blick, dass es sich um eine Kombination von Definition und Satz handelt.

Unabhängig hiervon ist mir nicht klar, was mit den Formeln in den beiden letzten Aussagen gemeint ist. Ich kenne diese Schreibweise nicht, obwohl ich mal Mathematik und auch Graphentheorie studiert habe. Gibt es einen Link dazu? --Thomy der Genuss 14:45, 17. Nov. 2006 (CET)Beantworten

Gerichtete vs. ungerichtete Bäume

[Quelltext bearbeiten]

Für jemanden, der von einem Abschnitt über gerichtete und ungerichtete Graphen kommt („Ein Baum ist in der Graphentheorie ein spezieller Graph“), dürfte sich nicht sofort erschließen, dass hier – wenn ich es richtig interpretiere – mit gerichteten Bäumen nicht Bäume gemeint sind, die gerichtete Graphen sind, sondern gerichtete Graphen, auf denen eine Ordnung im üblichen Sinne definiert werden kann. (Und dies ist selbst dann noch keine Definition für das, was ich unter Bäumen verstehe!) Nur unter letzterer Interpretation macht der zweite Teil dieses Abschnittes einen Sinn. --Thomy der Genuss 14:45, 17. Nov. 2006 (CET)Beantworten


V, E

[Quelltext bearbeiten]

Hallo ihr Experten! V und E wurden gar nicht definiert oder sehe ich das falsch? Also V ist wohl die Menge der Kanten und E die Menge der Knoten, oder? --132.187.3.26 19:19, 10. Sep. 2007 (CEST)Beantworten

Hallo du Experte! V und E sind sehr wohl definiert, nämlich im Artikel über Graphen, so, wie sich das gehört. Wärst du dem Link dorthin gefolgt, hättest du bemerkt, dass du falsch liegst mit deiner Vermutung. --Koethnig 00:59, 11. Sep. 2007 (CEST)Beantworten
Ah, danke für den Tipp! Es wäre aber echt praktischer, das nochmal bei Bäumen zu haben als erst bei Graphen zu suchen. Aber trotzdem danke! --132.187.3.26 10:12, 12. Sep. 2007 (CEST)Beantworten

Entscheidungsbäume

[Quelltext bearbeiten]

Hallo,

in der künstlichen Intelligenz bzw. in der Spieltheorie werden doch häufig Entscheidungsbäume eingesetzt, um die optimale Strategie in einer spielartigen Situation zu finden. Beispiele sind hier der Minimax Algorithmus und Und-Oder-Baum.

--In4matic 09:34, 2. Okt. 2008 (CEST)Beantworten

Markierung von Bäumen

[Quelltext bearbeiten]

Hi, wieso steht nirgends was zu markierten Bäumen... unter Binärbaum auf unter Traversierung darauf verwiesen wie man Bäume abarbeiten kann. Aber das macht doch nur Sinn, wenn sie markiert, also "beschriftet" sind oder? Sollte diese Möglichkeit der Markierung nicht als allgemeine Eigenschaft in dem Artikel hier festgehalten werden? Grüße --WissensDürster 14:28, 24. Jan. 2009 (CET)Beantworten

Def. gerichteter Baum

[Quelltext bearbeiten]

Die Def. für gerichtete Bäume lautet z.Z.: "Ein gerichteter Baum ist ein gerichteter kreisfreier Graph mit genau einer Wurzel. (...)" Nach dieser Definition wäre G = ({A, B, C}, {(A, B), (A, C), (B, C)}) ein Baum: Es ist ein gerichteter Graph, der kreisfrei ist (ABC wäre nur in einem ungerichteten Graphen ein Zyklus) und der genau eine Wurzel (A) hat. Müsste es nicht eher heißen "Ein gerichteter Baum ist ein gerichteter Graph mit genau einer Wurzel, der unter Nichtbeachtung der Kantenrichtung kreisfrei ist."? So ähnlich steht es übrigens auch in der englischen Version.

Die Def. setzt dann fort mit "Wurzeln sind Knoten mit Eingangsgrad 0. (...)". Das ist zwar korrekt, aber der Vollständigkeit halber müsste es doch heißen "Wurzeln sind Knoten mit Eingangsgrad 0, von denen aus alle anderen Knoten im Graphen erreicht werden können." (mir fällt leider keine bessere Formulierung für die Erreichbarkeit ein, ohne das ganze als Formel hinzuschreiben). Dann (und nur dann) kann man m.A. auch das Wort "zusammenhängend" im Satz vorher weglassen. Sonst müsste da auch von einem "zusammenhängenden gerichteten Graphen" die Rede sein.

Etwas ungünstig ist aus meiner Sicht auch, dass die Begriffe Ein- und Ausgangsgrad verwendet werden, aber weder verlinkt sind noch im Artikel über allgemeine Graphen vorkommen.

--IronCanceller 2012-05-04

Definition gerichtete Bäume

[Quelltext bearbeiten]

Ich sehe ein Problem mit der Defition von gerichteten Bäumen.

"Ein gerichteter Baum ist ein gerichteter kreisfreier Graph mit genau einer Wurzel. Wurzeln sind Knoten mit Eingangsgrad 0. Knoten mit Ausgangsgrad 0 heißen Blätter."

Meines Erachtens fehlt hier ein wichtiger Punkt:

  • der Eingangsgrad eines Knotens ist maximal 1 bzw.
  • es exisitiert für jeden Knoten genau ein Pfad von der Wurzel zu diesem Knoten

--136.199.55.249 10:30, 9. Mai 2012 (CEST)Beantworten

Letzter Punkt von "Äquivalente Charakterisierungen von Bäumen"

[Quelltext bearbeiten]

Ich störe mich am letzten Punkt der äquivalenten Aussagen, durch die ein Baum definiert werden kann: "G ist (minimal) zusammenhängend und (maximal) azyklisch"

Diese Konjunktion ist zwar zweifelsohne wahr, lässt man aber die Klammern um "minimal" und "maximal" weg, genügt auch eine der beiden Aussagen: Ein minimal zusammenhängender Graph ist immer auch azyklisch und umgekehrt ist ein maximal azyklischer Graph stets zusammenhängend.

Ich schlage daher vor, diesen Aufzählungspunkt in zwei separate aufzuspalten:

  • G ist minimal zusammenhängend
  • G ist maximal azyklisch

Fraglich bleibt, ob der Großteil der Leser unmittelbar eine Vorstellung von den Begriffen "minimal zusammenhängend" und "maximal azyklisch" hat. In der englischen Wikipedia sind diese Punkte ausformuliert und entsprächen übersetzt etwa:

  • G ist zusammenhängend, aber nicht mehr zusammenhängend, sobald man eine beliebige Kante daraus entfernt
  • G ist kreisfrei, aber jede weitere Kante zwischen zwei beliebigen Knoten erzeugt einen Kreis

-- Prokopton (Diskussion) 15:59, 22. Jan. 2013 (CET)Beantworten

Hallo!
Ich finde deine Ausführungen sehr gut und eine Verbesserung des Artikels. Ich schlage vor, beide Ideen zu kombinieren:
  • G ist minimal zusammenhängend, d. h. G ist zusammenhängend, aber nicht mehr zusammenhängend, sobald man eine beliebige Kante daraus entfernt
  • G ist maximal azyklisch, d. h. G ist kreisfrei, aber jede weitere Kante zwischen zwei beliebigen Knoten erzeugt einen Kreis
Ggf. mit Wiki-Links zur Definition von zusammenhängend und Kreis
Viele Grüße -- Phil1881 (Diskussion) 23:06, 22. Jan. 2013 (CET)Beantworten
Diese Variante würde auch ich bevorzugen. Ich habe den Artikel daher mal vorschlagsgemäß angepasst, die Sichtung der Änderungen steht jedoch noch aus.
-- Prokopton (Diskussion) 19:49, 23. Jan. 2013 (CET)Beantworten

stark zusammenhängend

[Quelltext bearbeiten]

>von einem Knoten w aus stark zusammenhängender kreisfreier Graph.< Das ist schlichtweg falsch. Ein Graph ist stark zusammenhängend oder nicht. Es kann nicht sein, dass er nur von einem Knoten aus stark zusammenhängend ist und von den anderen nicht. Dann würde man ihn schwach zusammenhängend nennen. Die Definiton von gewurzelter Baum ist falsch! Er ist schwach zusammenhängend und von einem Knoten aus, kann man jeden anderen erreichen.

Vgl. Definition: "Ein gerichteter Graph heißt (stark) zusammenhängend von einem Knoten aus..." in Zusammenhang (Graphentheorie). Viele Grüße -- Phil1881 (Diskussion) 15:23, 5. Nov. 2013 (CET)Beantworten
Stimmt! Es ist nicht die Definition. Mach's besser! „(Stark)“ zusammenhängend ist aus Zusammenhang (Graphentheorie)#Gerichtete Graphen und dort „von einem Knoten aus“. --Nomen4Omen (Diskussion) 15:41, 5. Nov. 2013 (CET)Beantworten

Tiefe eines Baumes

[Quelltext bearbeiten]

Ist es nicht sinnvoll hier auch die Tiefe eines Baumes zu definieren? (nicht signierter Beitrag von 91.39.87.178 (Diskussion) 21:17, 29. Nov. 2014 (CET))Beantworten

Allgemeinere Definition als spezielle Halbordnung

[Quelltext bearbeiten]

Diese Definition fehlt hier leider komplett:

  1. Ein Baum ist eine Halbordnung , so dass
    • die Menge für alle wohlgeordnet ist und
    • jedes Paar eine größte untere Schranke beseitzt.
  2. Die Elemente eines Baumes heißen Knoten. Maximale Elemente werden Blätter genannt, alle anderen innere Knoten und das kleinste Element ist die Wurzel.
  3. Ein Knoten heißt Kind (oder Nachfolger) von , falls und es keinen Knoten mit gibt.
  4. Eine Kette heißt Pfad, falls impliziert, dass für alle . Maximale Pfade werden Äste genannt.
  5. Die Ebene, Tiefe oder Stufe eines Knoten ist die zur Wohlordnung isomorphe Ordinalzahl.
  6. Die Höhe eines Baumes ist die kleinste Ordinalzahl, die größer als die Ebenen aller Knoten ist.

Soll ich sie einarbeiten? --Jobu0101 (Diskussion) 00:12, 9. Jan. 2015 (CET)Beantworten

Übrigens: Für die, die es nicht so mit Wohlordnungen und Ordinalzahlen haben: Bäume nach dieser Definition der Höhe maximal sind genau die gewurzelten Bäume aus dem Artikel. Man bekommt die entsprechenden Kanten, indem man einfach jeden Knoten mit seinen Kindern verkantet. --Jobu0101 (Diskussion) 00:38, 9. Jan. 2015 (CET)Beantworten

So was gehört schon rein. Das Spezielle an der „speziellen Halbordnung“ müsste dann erklärt werden und die Beziehung zum DAG. Braucht man „isomorphe Ordinalzahl“ ?
Man muss sich auch klar machen, dass die Erweiterung auf unendliche Knotenzahlen nur für ganz wenige Leser interessant ist, so das der Raum und die Begriffe, die man dafür braucht gering gehalten werden sollten.
--Nomen4Omen (Diskussion) 10:47, 9. Jan. 2015 (CET)Beantworten
Ja, ich könnte das gerne übernehmen und auch versuchen, die Begriffe, die verwendet werden, dabei zu erläutern (bzw. im Falle, dass man eine Höhe von maximal omega hat, zu übersetzen). Jedoch ist mir gerade aufgefallen, dass der Artikel ja Baum (Graphentheorie) heißt (man beachte die Klammer). Gehört dieses allgemeinere Konzept dann wirklich hier rein oder sollte man lieber einen eigenen Artikel anlegen und hier nur darauf verweisen? Nagut, streng genommen ist jede Halbordnung ein gerichteter Graph, bei einem Baum stellt man sich die Kanten jedoch anders vor (nämlich zwischen Vater und Sohn und nicht etwas zwischen einem Knoten und allen Nachkommen). Schade finde ich auch, dass hier im Artikel nicht die Begriffe der Tiefe und Höhe behandelt werden. Das ist ja durchaus auch für Informatiker relevant. --Jobu0101 (Diskussion) 15:45, 9. Jan. 2015 (CET)Beantworten
Ich glaube, ihr sucht den Artikel Gewurzelter Baum, dort wird auch Tiefe und Höhe erklärt und dort könnte man vielleicht auch die Definition über die Halbordnung einbauen. Für beliebige (graphentheoretische) Bäume, trifft das ja alles nicht zu. Grüße -- HilberTraum (d, m) 15:59, 9. Jan. 2015 (CET)Beantworten
Ja, du hast recht. Da passt es wesentlich besser. Werde mich im Laufe des Tages mal drum kümmern. --Jobu0101 (Diskussion) 02:43, 10. Jan. 2015 (CET)Beantworten

@Nomen4Omen: Was genau meinst du mit "braucht man „isomorphe Ordinalzahl“"? Also die ersten Ordinalzahlen sind ja natürliche Zahlen. Das hat man, wenn der Knoten von der Wurzel nach endlich vielen Schritten erreicht werden kann (ein Schritt hier immer als der Übergang zu einem Kind). --Jobu0101 (Diskussion) 02:46, 10. Jan. 2015 (CET)Beantworten

  1. Ich meine, dass man mit der Gleichsetzung Ordinalzahl = Zahl ganz schön weit kommt. Wenn nun der Begriff Isomorphie hinzukommt, muss man eigentlich fast die ganze Wohlordnungstheorie erklären. Das scheint mir mit Kanonen auf Spatzen geschossen zu sein, wo doch die Sache, um die es geht, viel einfacher ist.
  2. Des Weiteren würde den Beitrag nicht gerne als die Definition schlechthin für den gewurzelten Baum etablieren. Lieber wäre mir dort ein Abschnitt àla „unendlicher gewurzelter Baum“ mit den genannten Aussagen und dort eben, dass die endlichen gewurzelten Bäume die besagte Untermenge sind.
  3. Ganz wichtig aber die Bemerkung von Benutzer:HilberTraum,  dass das nicht hierher, sondern in den Artikel gewurzelter Baum gehört.
--Nomen4Omen (Diskussion) 10:51, 10. Jan. 2015 (CET)Beantworten

Aufspaltung in 2 Artikel

[Quelltext bearbeiten]

Ist schon einmal diskutiert worden, ob es nicht Baum (Graphentheorie) und getrennt davon den Artikel Baum (Datenstruktur) geben sollte? Sind doch zwei sehr unterschieldliche Dinge.. Spricht etwas dagegen? wenn nicht, werd ich das mal versuchen.--Mischa (Diskussion) 19:19, 21. Nov. 2015 (CET)Beantworten

Erg.: jop, in der engl. Wikipedia ist es auch so, wie von mir vorgeschlagen: Tree (graph theory) und Tree (data structure). Baustelle für neuen Artikel hier: GELÖSCHT.--Mischa (Diskussion) 19:36, 21. Nov. 2015 (CET)Beantworten

Ist erledigt.--Mischa (Diskussion) 13:16, 22. Nov. 2015 (CET)Beantworten

Ich hab den Unterschied erst verstanden, als ich in das englische Artikelpaar geschaut habe und mir mal eine Grundüberholung erlaubt.
Was ich jetzt noch nicht verstehe: Wozu brauchen wir zu den beiden Artikeln hier noch den Wurzelbaum?--goiken 13:41, 23. Nov. 2015 (CET)Beantworten

DAGs

[Quelltext bearbeiten]

Sollten unter Verallgemeinerung nicht auch DAGs erwähnt werden? M.M.n ein wirklich wichtiger Graphentyp, der sich als direkte Erweiterung eines gewurzelten Baumes denken lässt. Dass dazu noch kein Lemma existiert, ist eh schade. -- 09:39, 21. Okt. 2016 (CEST)

Ich stimme der Wichtigkeit zu, finde aber, dass er weder in DAG noch in Graph (Graphentheorie)#Zyklisch/azyklisch noch in Halbordnung ordentlich benannt wird. Das Problem könnte sein, dass wir im Deutschen keinen so gut eingeführten Namen wie DAG haben. Am besten kommt mir noch vor: Gerichteter azyklischer Graph, von dem es tatsächlich auch schon eine Weiterleitung zu Graph (Graphentheorie) gibt. Trotzdem sollte er in irgend einem Artikel einen fett gedruckten Namen bekommen. --Nomen4Omen (Diskussion) 18:07, 21. Okt. 2016 (CEST)Beantworten

Spannbäume fehlen noch

[Quelltext bearbeiten]

Das in der allgemeinen Graphentheorie wichtige Ergebnis, das jeder Graph einen (sogar normalen) Spannbaum besitzt, klang noch gar nicht an. Normale Spannbäume werden auch nicht erläutert. Haltet ihr es für sinnvoll, das nochmal ausführlicher reinzuschreiben? --Sascha Laing (Diskussion) 18:29, 3. Mai 2019 (CEST)Beantworten

"Jeder zusammenhängende Graph..." ;-) Es gibt doch den recht ausführlichen Artikel Spannbaum. Deine Ergänzung des Lemmas habe ich entfernt und einen eigenen Abschnitt mit Verweis auf den Hauptartikel eingeführt. Viele Grüße -- Phil1881 (Diskussion) 12:13, 4. Mai 2019 (CEST)Beantworten

Baum + Kante = Kreis

[Quelltext bearbeiten]

@Nomen4Omen Durch Hinzufügen einer Kante entsteht (beim ungerichteten Baum!) ein Kreis. Beweis: Fügt man eine Kante zwischen a und b hinzu, so existiert neben dem vorhandenen Weg a-b ein zweiter Weg a-b (ein Kreis). siehe auch Abschnitt Charakteristika von Bäumen. Dort ist auch der unmittelbar vorstehende Satz Durch Entfernen einer Kante zerfällt ein Baum in zwei Teilbäume und bildet damit einen Wald mit zwei Komponenten wiederzufinden. Beide Sätze haben daher m.E. gleiche Berechtigung. --DixMartin (Diskussion) 18:03, 30. Jan. 2020 (CET)Beantworten

@DixMartin: OK. Wichtig ist, dass NUR eine Kante dazukommt und sonst nix. Die Problematik bei den gerichteten Bäumen wollen wir gar nicht ansprechen. --Nomen4Omen (Diskussion) 18:41, 30. Jan. 2020 (CET)Beantworten
1. zu zwischen zwei vorhandenen Knoten , ja danke. Das dient der Verdeutlichung, ist m.E. jedoch nicht zwingend erforderlich, da Kanten nur zwischen vorhandenen Knoten erstellt werden können.
2. zu oder auch von einem zu ihm selbst verwirrt daher eher, da Kanten von einem Knoten zu eben diesem Knoten als Schlinge bezeichnet werden, die je nach Definition nicht als Kreis zählt. -> streiche ich daher.
3. zur Problematik bei gerichteten Bäumen: füge ich noch einen Hinweis ein.
--DixMartin (Diskussion) 21:12, 30. Jan. 2020 (CET)Beantworten

k-Bäume

[Quelltext bearbeiten]

k-Bäume sind definitiv keine Bäume. Sie sollten daher nicht Teil dieses Artikels sein. Aber wohin damit? eigener Artikel? --DixMartin (Diskussion) 21:34, 22. Feb. 2020 (CET)Beantworten

Ja, sehe ich genau so. Der Artikel widerspricht sich selbst und sorgt für Verwirrung. In der Definition steht explizit, keine geschlossenen Pfade, aber hier wird suggeriert, dass ein Baum zyklisch sein kann. Nicht nur das, der vollständige Graph mit k Knoten wird als k-Baum bezeichnet. --YasinGiray (Diskussion) 17:41, 1. Aug. 2022 (CEST)Beantworten