Diskussion:Blätter und innere Knoten in der Graphentheorie

Die Definition passt unter Umständen nur für ungerichtete Bäume. Was ist wenn bei einem gewurzeltem Baum von der Wurzel nur eine Kante ausgeht? Ist die Wurzel dann auch ein Blatt oder ist die Definition hier lückenhaft? Was ist mit einem gerichteten Baum aus nur einem Knoten, ist der dann Wurzel, Blatt und innerer Knoten zugleich? -- Nichtich 02:35, 12. Mai 2008 (CEST)

Sollte man nicht die Schreibweisen Grad 1 und Grad Null vereinheitlichen? qued --Herzi Pinki 20:02, 13. Mai 2008 (CEST)

offen --Herzi Pinki 00:35, 19. Mai 2008 (CEST)

Wird es für diesen Artikel auch Quellen geben? Immerhin als Musterbeispiel für einen geprüften Artikel angelegt. --Herzi Pinki 22:32, 16. Mai 2008 (CEST)

Ich habe den Artikel ursprünglich angefasst, um ihn zu prüfen, ist aber bisher nichts geworden. Wenn ich weiter bin, Liste ich mal meine Quellen auf, ich muss noch einige Standardwerke konsultieren. -- Nichtich 00:13, 19. Mai 2008 (CEST)

Überlappung: Will ja nicht böse sein, aber unter Grad (Graphentheorie)#Blatt steht das einfacher (im doppelten Sinn), da dort vermutlich implizit gerichtete Bäume vorausgesetzt werden. --Herzi Pinki 20:14, 13. Mai 2008 (CEST)

Wenn jemand nachschlägt, was ein Blatt ist, soll er ja gerade eine geprüfte Antwort erhalten, ohne implizite Annahmen mitbringen zu müssen.

Betonung lag auf Überlappung (im Sinne von Redundanz), nicht auf den impliziten Annahmen. --Herzi Pinki 00:35, 19. Mai 2008 (CEST)

Für nicht zusammenhängende Graphen (etwa einem Wald) lässt sich die Definition hier nicht anwenden, da der ganze Artikel von zusammenhängenden Graphen ausgeht. --Herzi Pinki 22:32, 16. Mai 2008 (CEST)

Steht ja auch nirgends. ;-) Der Artikel erklärt nur, was im Rahmen der Graphentheorie Blätter eines Baumes sind. Das sollte nicht mit einer formalen Definition verwechselt werden. Im Übrigen denke ich schon, dass es auch für Wälder passt. -- Nichtich 00:13, 19. Mai 2008 (CEST)

für Wälder passt es nicht, da ja explizit die Einschränkung auf Bäume gemacht wird. Ob Wälder Blätter haben, bleibt offen. --Herzi Pinki 00:35, 19. Mai 2008 (CEST)

Ja, Wälder selbst haben keine Blätter, das habe ich in der Form auch nirgends gefunden. Aber die Bäume eines Waldes haben Blätter. Das ist so wie eine Fußballmannschaft, die keine Tore schießt, weil ja eigentlich immer ein Spieler den Ball ins Tor befördert. -- Nichtich 02:33, 19. Mai 2008 (CEST)

Versuch einer Prüfung

Die (noch nicht abgeschlossen dokumentierte) Prüfung des scheinbar trivialen Artikels verlief komplizierter als gedacht. Als Vorab-Fazit finde ich folgendes bemerkenswert:

• Praktisch jeder Artikel enthält unscharfe Aussagen wie zum Beispiel "üblicherweise", "meist", "in der Regel" - ob diese angemessen (wieder so ein unscharfer Begriff) sind, hängt von der Meinung des Prüfers ab
• Es gibt - selbst in der Mathematik - nicht eine Definition sondern mehrere verschiedene, je nachdem welche Quelle herangezogen wird. Die Quellen meinen jedoch das gleiche. Was die Quellen meinen, bzw. eigentlich: Was "Stand der Forschung" ist, hängt von der Interpretation des Prüfers ab.
• Das Heranziehen mehrere Quellen setzt die Sorgfalt des Prüfers voraus.
• Auch Quellen enthalten Lücken, wenn man nur tief genug nachbohrt - Alles baut auf irgendwelchen impliziten Annahmen auf. Was vorrausgesetzt werden kann und ab wann eine Lücke vorliegt, hängt von der Einschätzung des Prüfers ab.
• Die Vorstellung, alle Aussagen, liessen sich durch Quellen "belegen", ist naiv. Quellen belegen nur, dass etwas in einer Quelle steht. Wie die Quelle zu bewerten und zu verwenden ist, hängt von der Erfahrung des Prüfers ab.
• Was dem einen Prüfer ausreicht, ist für den anderen eine Ungenauigkeit, Lücke oder unbelegte Aussage. Das heisst: Prüfer können unterschiedlicher Meinung sein.

Bei weniger formalen Themen sollten diese Phänomene noch stärker auftreten. Prüfungen sind immer subjektiv, deshalb sollten Prüfungen immer an einzelne, identifizierbare Personen gebunden sein.

Was noch fehlt

Es fehlt eine exaktere Definition, die auch die Sonderfälle (isolierte Knoten, Wurzel, In-Tree vs. Out-Tree ... erfasst. Eine solche Definition ließe sich aber nicht einfach mit Quellen prüfen, sondern selber entwickeln - also Keine Theoriefindung. Eine Definition wäre beispielsweise:

• In einem Baum (=kreisfreier Graph) ist ein Knoten mit höchstens einem Nachbarn ein Blatt und ein Knoten mit mehr als einem Nachbarn ein innerer Knoten.

Offene Frage ist, ob die Nichtbehandlung der Sonderfälle eine "entstellende Lücke" im Artikel ist oder nicht. Wenn die Fachliteratur Lücken aufweist, sollte es an dieser Stelle auch Wikipedia dürfen. -- Nichtich 02:33, 19. Mai 2008 (CEST)

Hat sich erledigt. Die Tabelle mit den möglichen Definitionen ist allerdings noch etwas unschön und könnte verständlicher gestaltet werden!

Momentan ließe sich noch angeben:

Praktische Bedeutung

z.B. bei der Verwendung von Bäumen als Datenstruktur. Was wäre da zu nennen?

• In einigen Fällen werden Daten nur in den inneren Knoten und in einigen Fällen werden Daten nur in den Blättern gespeichert (Beispiele?!).
• Mir fällt außerdem die Baumstruktur eines XML-Dokumentes ein mit leeren Elementen, Textknoten als Blättern etc., aber das ist wahrscheinlich zu komplex
• Ein schönes Beispiel aus der Praxis wäre vielleicht: bei einem Ableitungsbaum sind die Blätter Terminalsymbole und die inneren Knoten Nichtterminalsymbole.

Weitere Eigenschaften

Minimale und Maximale Anzahl von Blättern in einem Graph mit n Knoten (n>=1) ist 1 ("Kette") bzw. n<=2 : n, n>2 : n-1 ("Stern"). Grundsätzlich sollten aber nicht zu viele weiteren Details, die nicht primär mit Blättern und inneren Knoten zu tun haben in den Artikel. Sicherlich gibt es Sätze, die Aussagen über Blätter in speziellen Bäumen machen, aber das gehört dann zu den speziellen Bäumen und nicht hierher. -- Nichtich 13:00, 25. Mai 2008 (CEST)

Ein kleines bischen mehr zur Geschichte

Eine interessante Definition verwendet anscheinend Petersen: "Defining a leaf to be part of a graph which can be seperated from 
the rest by removing just one edge ..." ( J. Petersen: On the theorem of tait. 1898, p. 225, zitiert nach: "Graph theory 1736-1936"). 
Zu den Ursprüngen gibt es ggf. noch etwas bei Sylvester und Polya: "The concept of a tree, a  connected graph without cycles, 
appeared implicitly in the work of Gustav Kirchhoff (1824-87), who employed graph-theoretical ideas in the calculation of currents 
in electrical networks or circuits. Later, Arthur Cayley (1821-95), James J. Sylvester(1806-97), George Polya(1887-1985), and others 
use 'tree' to enumerate chemical molecules." [1]

Ecken

Halte die Einführung des Begriffs Ecke in der Definition von Blatt für ungünstig, da dieser Begriff weder definiert, noch verlinkt, noch außerhalb der Definitionen verwendet wird. --Herzi Pinki 00:28, 25. Mai 2008 (CEST)

Das ist ein Originalzitat und Diestel ist Standardwerk. Ich habe eine eigene Anmerkung im Zitat hinzugefügt. "Ecke" wird auch unter Knoten (Graphentheorie) erklärt. -- Nichtich 14:42, 25. Mai 2008 (CEST)

Geschichte

Danke für das Hinzufügen, historische Aspekte haben bisher gefehlt. Zum Bild: Fig 3. widerspricht der Graphentheorie. Ich sehe hier nur 2 unterschiedliche Graphen, nicht 3 wie das Arthur Cayley tat. Die beiden rechten sind identisch. Dafür lassen sich aus dem linken Beispiel (eine Wurzel mit 3 direkten Blättern) beliebige Bäume mit 3 Blättern konstruieren, indem einfach eine neue Wurzel vor der aktuellen Wurzel eingefügt wird und diese damit zu einem inneren Knoten verkommt, aber die Anzahl der Blätter mit 3 unverändert bleibt. Es fehlen hier also u.U. Randbedingungen. --Herzi Pinki 00:28, 25. Mai 2008 (CEST)

Hm, beim zweiten Punkt hast du recht, da fehlt noch eine Randbedingung, vermutlich muss die Anzahl der Knoten pro Ebene zunehmen. Leider ist Cayleys Definition eines Baums etwas gewöhnungsbedürftig. Der erste Punkt sollte durch das folgende Bild in Cayleys Artikel klarer werden, zum Glück ist alles digital beim Internet Archive vorhanden. Wie könnte man den Hinweis in den Artikel aufnehmen? -- Nichtich 13:05, 25. Mai 2008 (CEST)

ich denke auch beim ersten Punkt Recht zu haben. --Herzi Pinki 23:53, 2. Jun. 2008 (CEST)

König (1936) verwendet den Ausdruck "Blatt" nicht im Zusammenhang mit Bäumen, ebensowenig spricht er von "inneren Knoten". Er definiert allerdings allgemein für Graphen Knotenpunkte vom Grad 1 als "Endpunkt".