Diskussion:Graphentheorie

Ich kann das ganze Vorhaben "Graphentheorie", jetzt wo ich angefangen habe etwas konkretisieren, da ich natürlich schon auf Probleme und deren Lösung gestoßen bin.

Also der grobe Fahrplan ist, einige größere Artikel zu schreiben, in denen viele Begriffe definiert und erklärt werden, die ähnlich sind, oder in irgendeinerweise zusammengehören. Für jeden Begriff gibts dann einen Artikel, der lediglich auf den großen Artikel umleitet. Später kann man diese Artikel ja auch mit kürzerem Text füllen, und nur auf den großen Artikel verweisen. Dann muß der Leser nicht ständig große Artikel lesen, wenn er eigentlich schon einen guten Überblick vom Thema hat und nur eine kurze Erklärung benötigt. Das sollte vor allem auch Schewek entgegenkommen, der schrieb:

Ich finde, grundlegende Begriffe sollten hier bleiben, und die entstehenden Unterartikel sollten nicht zu klein sein. -- Schewek

Ich finde es hilfreich, ein paar zentrale Begriffe zur Verlinkung im 'Hauptartikel' zu haben. Erstmal, um 'Inhalt' im Hauptartikel zu haben, aber auch, um weiterzuleiten. - Leg mal los, ich schaue zu. -- Schewek

Momentan gibts noch keine Beispiele, da ich Bilder malen will, aber dies wohl recht aufwendig wird. Sollte jemand interesse haben, die Aufgabe zu übernehmen, wär das auch toll. Aber er sollte aus Konsistenzgründen dann auch alle Beispiele zu allen Artikeln (der Graphentheorie) erstellen und bitte möglichst akkurat und sauber arbeiten. Wenn der-/diejenige sich vorher mit mir abstimmt, wäre das sicher hilfreich.

Ich werde außerdem eine Liste graphentheoretischer Artikel pflegen, die alle Artikel zur Graphentheorie zusammenfaßt, damit man einen Überblick bekommen kann, was es so gibt und was schon fertig ist. Wer meint, in der Liste würden noch Dinge fehlen, sollte die an das Ende eintragen. Ich kümmere mich dann um die Einordnung.

In der Diskussion zu Graph (Graphentheorie) hab ich eine Frage zur Struktur des Artikels gestellt, die auch allgemeinen auf die anderen Artikel übertrag bar ist. Es wäre nett, wenn vor allem Leute, die nicht so viel Ahnung von Mathe bzw. Graphentheorie haben mal sagen könnten, wie sie zu der Frage stehen. Alle anderen können natürlich auch ihren Senf dazugeben.

Die Reste des alten Artikels hab ich jetzt in diese Diskussion verschoben. --Coma 12:01, 13. Jan 2003 (CET)

---

Wow! Ich bin begeistert. Nur eins ist mir aufgefallen: Wenn man die ungerichteten Graphen über ungeordnete Paare definiert, sind Schleifen möglich. Die zweielementigen Teilmengen bringen das nicht. Deshalb sind die Schleifen jetzt bei den ungerichteten Graphen verschwunden. Sie sollten aber doch Schleifen besitzen können, oder? --Rade

Ich glaube der Artikel Graph (Graphentheorie) beantwortet jetzt die Frage. Bist Du damit so zufrieden? Auf jedenfall danke für den Hinweis! --Coma

---

---

Noch unerklärte Teile des alten Artikels

---

Beispiel

1 _____ 2 _____ 3
 \     /       /
  \   /       /
   \ /       /
    5 _____ 4

Dieser Graph hat fünf Ecken: V = {1,2,3,4,5}. Die Kantenmenge als Menge ungeordneter Paare ist E = { (1,2), (1,5), (2,3), (2,5), (3,4), (4,5) }. Betrachtet man geordnete Paare, so müssen auch (2,1), (5,1), etc. in E aufgenommen werden. Der Graph ist mit den Gruppen {1,3}, {2,4}, {5} 3-partit. (1,2,5,1,2,3) ist ein Weg und (5,1,2,3) sogar ein Pfad. Der Graph ist nicht vollständig.

Seine Adjazenzmatrix hat folgende Gestallt:

  | 1 2 3 4 5
--+----------
1 | 0 1 0 0 1
2 | 1 0 1 0 1
3 | 0 1 0 1 0
4 | 0 0 1 0 1
5 | 1 1 0 1 0

Ein K₄ sieht folgendermaßen aus:

         1______2____
         |\     |   |
         | \    |   |
         |  \   |   |
         |   \  |   |
         |    \ |   |
         4_____3    |
         |__________|

Plättbarkeit

Informal heißt ein Graph planar oder plättbar, wenn man ihn in die Ebene zeichnen kann, ohne dass sich zwei Kanten überschneiden. Ein Graph der in die Ebene eingebettet ist heißt eben. Ein ebener Graph heißt gesättigt, wenn der durch Hinzufügen einer beliebigen Kante entstehende Graph nicht mehr eben ist. Die beiden oben gezeichneten Graphen sind eben. Ein K₅ ist nicht planar.

Bäume

Ein Baum kann auch eine Wurzel haben - ein spezieller Knoten, der in Bezug auf gewisse Anwendungen als Startpunkt oder Basis angesehen wird. Siehe auch Binärbaum

Ausführungen zur Adjazenzmatrix

Sind zwei Graphen auf der selben Knotenmenge gegeben, dann können die Adjazenzmatrizen multipliziert werden (Matrixmuliplikation). Die Elemente der Ergebnismatrix geben an, ob ein Knoten durch eine Kante aus dem ersten Graphen gefolgt von einer Kante aus dem zweiten Graphen erreicht werden kann. Dementsprechend ergibt die Multiplikation einer Adjazenzmatrix mit sich selbst (Quadration) die Verbindungen über exakt zwei Kanten an. Allgemein gibt M^k die Existenz von Verbindungen (Pfade) der Länge k an.

Stabilisator

Habe den Link auf Stabilisator geändert, da es Stabilisator (Mathematik) ohnehin nicht gab. Stimmt das so auch für die Graphentheorie (evtl. mit kleinen Änderungen in Gruppenaktion)?--Gunther 15:54, 1. Mär 2005 (CET)

Und wo hast du das geändert und was hat das mit der Graphentheorie zu tun? --Coma 17:01, 1. Mär 2005 (CET)

Oh, sorry, das war so wohl nicht zu verstehen: Im Artikel Stabilisator stand vor meiner Änderung: "in der Mathematik speziell in der Graphentheorie ein fester Punkt eines Graphen, siehe Stabilisator (Mathematik)". Das habe ich ersetzt durch: "in der Mathematik eine Menge von Symmetrien, die einen Punkt fest lässt, siehe Gruppenaktion". Da ich keine Ahnung von Graphentheorie habe, wollte ich kurz nachfragen, ob ich mit meiner Annahme richtig liege, dass das derselbe Begriff ist (ja, mir ist aufgefallen, dass der alte Text sagt, es sei der Punkt und nicht die Untergruppe).--Gunther 17:08, 1. Mär 2005 (CET)

Da gehe ich stark davon aus. In der Graphentheorie heißt der Punkt dann vermutlich einfach nur Knoten, ist mathematisch aber das selbe. Graphen sind ja nur eine von vielen Objekten/Dingen über die man Symmetrien festlegen kann, es hat also nichts speziell mit der Graphentheorie zu tun. Die Änderung war insofern richtig. --Coma 17:29, 1. Mär 2005 (CET)

Geschichte

Der Abschnitt zur Geschichte ist in der englischen Wikipedia weit besser ausgebaut. Interessant ist auch, wie die Graphentheorie eigentlich aus der Chemie hervorging (siehe hier bzw. Dennis Rouvray's "The Origins of Chemical Graph Theory" ( Mathematical Chemistry 1(1991), 1-39)) -- Nichtich 19:06, 25. Mai 2008 (CEST)

Hier ein Hinweis:

• Wladimir Velminski: Leonhard Euler. Die Geburt der Graphentheorie. Kulturverlag Kadmos, Berlin 2008, ISBN: 978-3-86599-056-3.

Spektrale Graphentheorie

Die gehört meines Erachtens in einen eigenen Artikel, natürlich mit mehr Inhalt.--Suhagja (Diskussion) 18:04, 26. Okt. 2012 (CEST)

BKL2

Sollte im BKL2-Baustein nicht vor allen Dingen Graphentheorie (Chemie) erwähnt sein? Ist schon eine böse Falle mit den grundverschiedenen Betonungen und Bedeutungen, die man dem Wort in geschriebenem Zustand ja nicht ansehen kann... --Zopp (Diskussion) 11:08, 22. Mai 2014 (CEST)

Die chemische Graphentheorie ist nur eine spezielle Anwendung der mathematischen und den Begriff "Graphēntheorie" (mit Betonung auf der zweiten Silbe) gibt es nicht. Daher wird hier gar keine BKL2 benötigt. Grüße, --Quartl (Diskussion) 19:13, 22. Mai 2014 (CEST)