Diskussion:Graph (Graphentheorie)/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Graph (Graphentheorie)/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung auVorlage:SSerhalb der Wikipedia

https://de.wikiup.org/wiki/Diskussion:Graph_(Graphentheorie)/Archiv/1#Thema_1

Anwendungsbeispiele

Es wäre schön, wenn sich jemand mal ein paar Anwendungsbeispiele überlegt. Dann würde das Ganze vielleicht auch weniger "abgehoben" beurteilt und wäre verständlicher. Vielen Dank im Voraus! (AK)

Laienverständlichkeit

So, hab hier mal eine Frage an die Leser des Artikels. Mal abgesehen davon, dass einige Begriffe, auf die verlinkt wird, noch nicht erklärt sind: Ist der Artikel auch für Laien verständlich? Oder sollte man vielleicht erst die Anschauung und Beispiele bringen und dann die Definitionen? --Coma

Dein Engagement in allen Ehren aber, aber für Laien ist der Artikel total unverständlich, weil schon das Wort Tupel eher verwirrt als Klärung bringt. Es sollte lieber vom einfachen zum Speziellen gegangen werden. Beispiel:

Das Tupel noch nicht erklärt ist, dafür kann ich jetzt auch nicht soooo viel. Aber jeden Begriff, den man benutzt zu erklären bringt auch nicht so viel, oder? --Coma 12:38, 28. Jan 2003 (CET)

Einfach ist in diesem Fall ja schon speziell! Gerichtete Graphen mit Mehrfachkanten sind hier am allgemeinsten(!), wie im Artikel erläutert. Einfache Graphen am meisten spezialisiert! --Coma 12:38, 28. Jan 2003 (CET)

Ungerichtet? Teilmenge?

...Dabei ist E in

• ungerichteten Graphen ohne Mehrfachkanten eine Teilmenge aller 2-elementigen Teilmengen von V...

---

Was ist ungerichtet? Was sind Teilmengen? (ungerichtet gehört z.B. in einen Artikel Kante (Graphentheorie))

An dieser Stelle wird erklärt, was ein ungerichteter Graph ist und wie seine Kantenmenge aussieht! --Coma 11:43, 28. Jan 2003 (CET)

Zu lang

Überhaupt ist der Artikel ist viel zu lang. Alles über Mehrfachkanten, Hypergraphen, Erweiterungen etc. gehört in eigene Artikel.

Die Artikel wären dann zu klein, der Laie muss dann zwanzig Seiten aufrufen, um einen einen Überblick zu einem Thema zu bekommen. Deshalb die großen Artikel mit vielen zusammengehörenden Begriffen. Was es für Graphen gibt und wie die Aussehen ist zum Beispiel ein Artikel (der zu dieser Diskussion). Was Zusammenhang von Graphen bedeutet ein anderer. Da muss man den anderen Artikel natürlich schon gelesen haben, oder wissen was ein Graph ist. Oder soll das in jedem Artikel erklärt werden??? Dann werden diese noch länger. Es ist ja alles wesentliche verlinkt. Und die Grundlegenden Begriffe der Mathematik, die man für Definitionen braucht habe ich auch verlinkt. Sollen die hier auch erklärt werden??? Das würde noch längere Artikel nach sich ziehen. Die ganzen Redirects die ich angelegt habe, können ja auch irgendwann die kleinen Begriffe noch einmal kurz erklären. Aber sie sollten dann immernoch einen Link auf den großen zusammenhängenden Artikel haben. --Coma 11:43, 28. Jan 2003 (CET)

Ungerichtete Graphen ohne Mehrfachkanten

Ich lerne grade für eine Prüfung Graphen und Algorithmen im Hauptstudium Informatik und würde deshalb gerne an "deinen" ;-) Seiten etwas herumwerkeln.

Allerdings haben wir uns hauptsächlich mit ungerichteten Graphen ohne Mehrfachkanten beschäftigt. Das sind aber auch die Graphen, die am meisten interessieren, deshalb finde ich es doof, immer ungerichteten Graphen ohne Mehrfachkanten dazuzuschreiben. Ich würde lieber wie folgt vereinbaren:

• Wenn nicht anders angegeben heisst Graph = ungerichteten Graphen ohne Mehrfachkanten

So, jetzt hab ich mir den Artikel nochmal angesehen. Da steht dies eigentlich drin! In Graphen ohne Mehrfachkanten läßt man den Zusatz "mit Mehrfachkanten" weg, usw... Du darst also gerne einfach nur Graph schreiben, ich würde an Deiner Stelle trotzdem lieber (wenigstens einmal im Artikel) darauf hinweisen, welche Graphen Du damit meinst! --Coma 12:38, 28. Jan 2003 (CET)

OK? --JakobVoss 21:39, 26. Jan 2003 (CET)

Zufälligerweise die Vorlesung bei Anusch Taraz und Stefan Hougardy? Die hab ich gehört, und Du hast recht! Wir wollen aber möglichst allgemeingültig bleiben. Du kannst ja gerne sagen, dass Du jetzt nur solche Graphen betrachtest, aber dass muss schon wengistens einmal im Artikel erwähnt werden! Der Grund, warum man Dinge oft nicht oder falsch versteht, besteht nämlich darin dass der Autor nicht genau genug ist. Wir sollten für den Leser und nicht für uns schreiben. Also sollten wir lieber genau sagen was wir meinen, was manchmal aufwendiger zum schreiben ist, aber dafür für den Leser schneller zum Verständniss führt. --Coma 11:43, 28. Jan 2003 (CET)

Du hast schon recht. Ich finde es nur besser, wenn unter Graph (Graphentheorie) einem nicht gleich alle Spezialfälle um die Ohren gehauen werden, sondern erstmal für klein Fritzchen gesagt wird, dass ein Graph aus Knoten und Kanten besteht.

Dass diese Kanten gerichtet sein können und es mitunter mehrfach- und Hyperkanten gibt, dass man Graphen auch Färben kann und dass alles eigentlich ein Spezialfall von Hypergraphen ist, ist ja ganz korrekt und wichtig, aber es sollte erstmal nur erwähnt werden, indem auf weitere Artikel verwiesen wird. Natürlich werden die Artikel dann kleiner, und man muss einiges mehfach erkären, aber das sehe ich nicht als Nachteil.

Im Grunde ist der Artikel schon ok, aber es sollte vielleicht einiges gekürzt und in andere Artikel veragert werden.

Vielleicht finden wir irgendwo einen Mittelweg :-) --JakobVoss

Hoffentlich :-)! Ich sehe ein, das die Artikel noch nicht gut für Laien geeignet sind, ich hab sie ja auch erstmal nur für Mathematiker geschrieben! Ich hatte auch extra angefragt, ob es besser wäre erst die Anschauung und dann die korrekten mathematischen Definitionen zu geben! Es gab darauf aber keine Reaktion, also hab ich erstmal alles so gelassen wie es ist, weil man den unteren Abschnitt nicht einfach nach oben stellen kann. Was Knoten usw. sind, wird ja auch knapp und allgemein in Graphentheorie erklärt, deswegen sollte dieser Artikel schon genauer sein. Und Du selbst hast ja Spezialfälle von Graphen hier eingetragen, was ich für unsinnig halte, weil diese speziellen Graphen in anderen Artikeln schon erklärt werden, und dies glaube auch etwas ausführlicher.

Ich bin der Meinung, das man in Übersichtsartikeln ein ganzes Thema zusammenhängend und möglichst genau erläutern sollte und für jeden Extra-Begriff noch zusätzlich eine Extra-Definition in einem Extra-Artikel geben kann (bisher nur Redirects). Der Laie liest dann am besten den Übersichtsartikel, wenn er sich informieren will (auch wenn er bisher noch nicht so sehr für ihn geeignet ist), der Experte, bei dem einiges vorausgesetzt werden kann, ließt die kurze Erklärung +Definition in dem Extra-Artikel.

Und vor allem, bevor wir in den Artikel rumdoktern, sollten wir diskutieren (ist bei mir momentan problematisch, da ich nicht ständig einen Computer zur Verfügung habe). Die Übersichtsartikel haben eine ganz spezielle Reihenfolge. Die späteren Artikel greifen eventuell auf Definitionen der vorherigen zurück. Ich hab mir bei all dem schon ne Menge gedanken gemacht. Und wenn Du einfach was änderst, könnte dies viel mehr durcheinander bringen, als Du Dir auf den ersten Blick vielleicht vorstellen kannst. Es ist nämlich gar nicht so einfach, darauf zu achten die Leser nicht ständig im Kreis laufen zu lassen.

Ich bezweifle, dass sich die gesamte Struktur der gesamten Graphenartikel, so wie du sie möglicherweise geplant hast, vollständig aufrechterhalten läßt (solange du nicht alles alleine machst). Außerdem ist Wikipedia kein Lehrbuch, sondern ein Nachschlagewerk - man sollte also an jeder Stelle einsteigen können. Das beste ist einfach so viel wie möglich zu verlinken. --JakobVoss

Also besser ist es, Du fragst erst oder weist auf Fehler hin (die sicher existieren) und ich versuch es dann in der Diskussion zu erläutern oder ändere einfache Sachen (kann aber immer ein paar Tage dauern, bis ich die Diskussion lese, weil ich wie gesagt momentan Probleme mit meinem Compi zu Hause habe).

Bei Beispielen gibts im übrigen keine Probleme. Wenn Du die Lücken ausfüllen willst ist das kein Problem, sie sollten sich aber auch nur auf die Begriffe im Artikel beziehen. --Coma 13:40, 28. Jan 2003 (CET)

So war es mit den Beispielen aber auch nicht gemeint. Man sollte Beispiele von ganz allgemeinen Graphen, möglichst mit Bild angeben, so dass der Leser den Sinn der Definitionen im allgemeinen Artikel leichter versteht! --Coma 09:24, 29. Jan 2003 (CET)

Ja, ich habe schon verstanden, dass da noch allgemeine Beispiele fehlen, aber besser spezielle Beispiele als gar keine. Ich halte mich schon bei Änderung der allgemeinen Strukturen zurück, aber bei neuen Artikeln wie Einfacher Graph werde ich nicht jedesmal erst Rücksprache halten

Ich fände es besser den Artikel "einfacher Graph" nach "ungerichteter Graph ohne Mehrfachkanten" umzubennen, und ein Redirect von "einfacher Graph" drauf anzulegen (verschieben dorthin tuts auch). Ausserdem wär es ganz nett, wenn Du die neuen Artikel unten in die Liste graphentheoretischer Artikel einträgst...

ich nehm alles zurürck, so herum ist es doch besser. In der Liste graphentheoretischer Artikel solltest Du aber das (R) löschen, wenn dort kein Redirct mehr zu finden ist! --Coma 11:57, 30. Jan 2003 (CET)

Messwerte

Hallo Graph Spezialisten. Ich dachte auch die Darstellung von Messwerten (und eventuell Strichen dazwischen) in einem kartesischen (oder wie auch immer ?) Koordinatensystem ist ein Graph. Diese Definition scheint aber weder unter Funktionsgraph noch unter Graph(Graphentheorie) zu stehen. --Dirk33 20:56, 26. Feb 2004 (CET)

Zumindest in der Graphentheorie hat sowas auch nichts zu suchen... :-) Also wenn, dann bei Funktionsgraph, aber auch da wohl nur sehr bedingt... Ich sags mal so: Etwas mit Funktionsgraphen hat es schon zu tun... --Coma 23:37, 26. Feb 2004 (CET)

Ich habe nochmal in ein paar Lexikas und im Internet geschaut Graph als Darstellungsform von (gegebenenfalls miteinander verbundenen) Punkten ist wohl etwas allgemeiner als nur durch Punkten die durch eine Funktion beschreibbar sind. (Darstellung von RELATIONEN mittels Punkten bei denen gewisse Punkte mit Linien verbunden sind). Das mit den Messwerten stimmt dann wohl. --Dirk33 02:25, 27. Feb 2004 (CET)

Der Punkt ist, dass es auch etwas grundsätzlich anderes beschreibt. Bei Funktionsgraphen für Messwerten, wird eine Zahl eine andere zugeordnet. Bei einfachen Graphen in der Graphentheorie ist es die Beschreibung einer symmetrischen Relation. Bei Digraphen einer ganz allgemeinen Relation... --Coma 07:38, 27. Feb 2004 (CET)

Beispiele

Sodele, nun hab ich mich mal durch die wirklich sehr abgehobenen Beschreibungen durchgekämpft und zu den fünf Grundtypen mal fünf Beispiel skiziert. Hab' ich alles richtig verstanden? --Perlentaucher 06.08.2004

Der Witz bei Hypergraphen ist, dass eine Kante auch mehr als 2 Knoten verbinden kann. Das kommt im Bild nicht ganz raus. Ausserdem sind Hypergraphen normalerweise ungerichtet. --Mellum 20:03, 6. Aug 2004 (CEST)

Hyperkanten zeichnet man oft so, dass man die betreffenden Knoten, die sie enthalten umkreist. Bei vielen Kanten wird das natürlich schnell unübersichtlich. Die Bilder sollten unter einer Extraüberschrift "Beispiele" stehen und Bildunterschriften bekommen. Etwas kleiner dürfen sie auch sein und am besten man schreibt zu jedem Beispiel noch die Struktur hin, und was es nun für einen Graphentyp sein soll. Dann wäre es fast schon perfekt! :-) --Coma 15:29, 7. Aug 2004 (CEST)

Hypergraphen kann man auch als bipartite Graphen zeichnen, mit den Hyperknoten auf der einen Seite und den Hyperkanten auf der anderen. Das ist meistens uebersichtilicher als die Umkreisungsvariante. --Mellum 12:49, 9. Aug 2004 (CEST)

Hmm, das sollte man noch im Artikel erwähnen (danke für die Info), falls nicht schon geschehen. Werde das ggf. gleich erledigen. --Coma 15:14, 9. Aug 2004 (CEST)

Ok, hab' den Hypergraphen erstmal wieder rausgenommen, und die Beispiele in eine eigene Beispiel-Abschnitt einsortiert. Die Bildunterschriften erklären welcher Graphentyp sie sein sollen. Kleiner dauert 'n bissel was, da die Proportionen von Dotty (GraphViz) erstmal automatisch gesetzt werden. Frage: Arbeiten hier im Graphenuniversum noch andere mit GraphViz? --Perlentaucher 06.08.2004

Danke, sehr schön!!! Eine Bitte noch: Der gerichtete Graph mit Mehrfachkanten könnte so auch einer ohne Mehrfachkanten sein (unterschiedliche Richtungen bilden keine Mehrfachkante). Da sollte irgendwo noch eine zweite Kante in die selbe Richtung hinzugefügt werden. Für die Graphen mit Mehrfachkanten wäre auch jeweils eine zweite Variante schön, wo statt der mehrfach gezeichneten Kante die Vielfachheit an die Kante rangeschrieben wird. --Coma 15:14, 9. Aug 2004 (CEST)

Bezeichnung Englisch-Deutsch

In der deutschen Literatur zu Graphentheorie scheint G=(E, K) vorzuherrschen (z.B. M. Aigner: "Diskrete Mathematik", O. Ore, "Graphentheorie"); mit E für die Eckenmenge, K für die Kantenmenge. Sollte das im Artikel geändert werden? SPTH 16:36, 14. Jan 2006 (CET)

Nee, weil wir (fast) überall V für die Knoten und E für die Kanten haben. Wir sagen hier auch er Knoten statt Ecken. --Koethnig 18:36, 14. Jan 2006 (CET)

Ich halte es im deutschsprachigen Zweig der Wikipedia für angemessen, deutsche Bezeichnungen zu verwenden, sofern sie sich in der deutschsprachigen Literatur durchgesetzt haben. Auch die Verwendung sprachlich unglücklicher Wendungen wie "adjazent" erschwert meiner Meinung nach das Verständnis: Übersetzungen wie "benachbart" sind hier viel naheliegender. --FRR 15:34, 5. Aug 2006 (CEST)

Die deutschsprachigen Bezeichnungen "Knoten" und "Kanten" haben sich auch durchgesetzt, aber die Symbolik aus englischsprachigen Büchern "G=(V,E)" wird in den Informatik-Fakultäten gelehrt. Das Buch "Graphentheorie. Eine anwendungsorientierte Einführung" von Peter Tittmann spricht auch von V als Knotenmenge und E als Kantenmenge. -- Mathias bla? 15:43, 5. Aug 2006 (CEST)

Die Eckenmenge mit E zu bezeichnen birgt zudem auch Verwechslungsmöglichkeit mit der englischen Kantenmenge. (nicht signierter Beitrag von 213.49.146.117 (Diskussion | Beiträge) 17:14, 12. Jan. 2010 (CET))

gewichtete Kanten/Knoten

Leider wird mit keinem Satz erwähnt, was denn nun eine Gewichtung genau bringt und wie diese aufgebaut ist. Ich habe in dem Zusammenhang von positiver und negativer Gewichtung gelesen (im Artikel Algorithmus von Dijkstra, außerdem wird von "kantengewichteter Graph" auf diesen Artikel hier weitergeleitet), kann damit aber nichts anfangen und finde auch nichts dazu in diesem Artikel hier. Es sollte also nicht nur erklärt werden, was eine Gewichtung ist, sondern auch, wie man sie erstellt und was sie bringt.

Habe mal ein erläuterndes Beispiel eingetragen, vielleicht hilft dies ein wenig weiter; die Qualität der Strukturen ist wirklich nicht zufriedenstellend. Dieser Artikel ist eine große Definitionssammlung ohne Motivation für Graphen und deren Anwendung in Berechnungsmodellen. Mathias bla? 15:05, 3. Jul 2006 (CEST)

abzählbar viele Färbungen?

Mir ist neu, dass ganzzahlige Gewichte als "Farben" zu bezeichnen sein sollen. Erstens wäre dann jeder gewichtete euklidische [Distanz-]Graf mit ganzzahligen Entfernungen in Wahrheit ein gefärbter Graph, zweitens bestreite ich, dass sich abzählbar unendlich viele Farben finden lassen. An anderer Stelle wird von "gültiger" Färbung gesprochen. Welche ganzzahlige Kantengewichtung wäre hier ungültig?

Hochgradig zweifelnd @SIG@

"Graph"-Artikel

Der Inhalt dieses Artikels ("Typen von Graphen in der Graphentheorie") entspricht dem, was ich erwartet hätte, wenn ich unter "Graph" nachschlage; der Artikel Graph (Graphentheorie) ist noch nicht ausgereift. Wäre es sinnvoll, den langen Titel ("Typen von Graphen in der Graphentheorie") und den kurzen Artikel zu löschen und dem Schlagwort "Graph" diesen Artikel zuzuordnen? --FRR 15:39, 5. Aug 2006 (CEST)

Nein. "Graph" soll nur kurz und knapp sein, eigentlich gehört der Inhalt des Artikels "Graph" ins Glossar und der Artikel gelöscht. Dieser Artikel soll die grundlegenden Typen darstellen und ist als Übersichtsartikel für Einsteiger in das Gebiet gedacht (und hat genau deshalb auch so einen langen Namen). Evtl. kann man ihn nach "Graphentypen in der Graphentheorie" verschieben, der Titel klingt vielleicht etwas besser, aber dann sollte man auch alle Links auf diesen Artikel anpassen! --Koethnig 12:58, 7. Aug 2006 (CEST)

Der bisherige Artikel zu "Graph" wird kaum jemandem weiterhelfen, der nicht vorher wußte, was ein Graph ist: Er ist unvollständig, in sich widersprüchlich und bietet keinerlei Anschauung. Unvollständig etwa deshalb, weil die Definition nicht beschreibt, was die Ecken mit den Kanten zu tun haben und unklar bleibt, wie sich die mathematischen Objekte des gerichteten und ungerichteten Graphen unterscheiden. Widersprüchlich ist er, weil ein als (V, E) definierter Graph keine Mehrfachkanten enthalten kann. Außerdem hat wohl jeder, der an einen Graphen denkt, ein graphisches Modell vor Augen. Ein zentraler Begriff wie "Graph" sollte auf einen sinnvollen Artikel verweisen. --FRR 14:36, 7. Aug 2006 (CEST)

Wie ich schon sagte, der Inhalt soll auch in Glossar. Dieses ist dann nicht mehr für Laien gedacht, sondern zum Nachschlagen von Definitonen. --Koethnig 21:01, 7. Aug 2006 (CEST)

(un)endliche Graphen

Zitat aus dem Artikel: Einen Graph, dessen Knotenmenge endlich ist, nennt man endlicher Graph. Zwangsläufig ist in diesen auch die Kantenmenge endlich.

Ist das wirklich richtig? Können (rein mathematisch gesehen) zwischen zwei Knoten nicht auch unendlich viele Kanten existieren? --193.81.246.92 16:28, 8. Aug 2006 (CEST)

"Graph" - Nominativ/Genitiv/Dativ/Akkusativ

Laut Wahrig wird der "mathematische" Graph dekliniert wie "der Bär". Das heißt,

• der Bär -> der Graph
• des Bären -> des Graphen
• dem Bär -> dem Graph
• den Bär -> den Graph

Allerdings habe ich auch schon dem Graphen und den Graphen gesehen. Man sollte es dann aber zumindest konsistent halten! -- Mathias bla? 15:59, 17. Aug 2006 (CEST)

Laut Duden heißt es: der Graph, des Graphen, dem Graphen, den Graphen - eben genau wie: der Bär, des Bären, dem Bären, den Bären. Steht im Wahrig wirklich "dem Bär"??? (nicht signierter Beitrag von 84.154.60.30 (Diskussion | Beiträge) 19:43, 5. Apr. 2009 (CEST))

Phi

Wenn ich das richtig sehe, dann ist Phi die Zuordnung, die einer Kante ihre Eckknoten zuordnet. Müsste dann Phi nicht eigentlich eine Abbildung N->ExE sein und nicht, wie im Artikel steht, N->E? Außerdem steht nur da, dass es Phi gibt und welche Urbild- und Bildmengen es hat, nicht aber, was es tut. --217.95.38.70 19:00, 26. Jan. 2007 (CET)

Psi: Abbildung von E nach VxV

frage/anmerkung: Psi soll wohl eine Abbildung von E nach VxV sein. Sonst macht die Definition eines gerichteten Graphens keinen Sinn. Denn dort wird nämlich vom Paar (v,v') gesprochen, welches Bild einer Kante sein soll. (nicht signierter Beitrag von 80.141.118.36 (Diskussion | Beiträge) 14:14, 21. Mär. 2007 (CET))

Schnittmenge: leere Menge!?

frage/anmerkung: Sollte die schnittmenge von V mit E nicht die leere menge sein? E ist ja teilmenge von VxV aber nicht von V (nicht signierter Beitrag von 62.178.75.222 (Diskussion | Beiträge) 22:52, 2. Mär. 2007 (CET))

Du hast recht. Ich habe den Artikel entsprechend abgeändert. --Stefan Birkner 18:57, 5. Mär. 2007 (CET)

Aufbau

Die erste Definition des Graphen ist nicht allgemein genug, um die nachfolgenden Erweiterungen einzuschließen. Auf jeden Fall besteht ein Graph aus E, V und Psi. Daher sind entweder klar gerichtete und ungerichtete Graphen sowie gewichtete und ungewichtete zu unterscheiden. Dann gäbe es keinen allgemeinen Graphen. Oder es wäre der allgemeine Graph zu definieren, so daß alle genannten Typen Spezialfälle des allgemeinen sind. Dies ist meines Erachtens der sinnvollere Weg.

Außerdem sollte man nicht einen Graphen an sich zunächst als gerichtet oder ungerichtet beschreiben, um dann darauf hinzuweisen, daß diese Eigenschaft doch nur seinen Kanten zukommt, nicht dem Graphen selber. Ein Graph genau dann ungerichtet, wenn die Beziehung (v',v)=(v,v') für alle Paare gilt, und gerichtet, wenn er nicht ungerichtet ist.

Gibt es Einwände? Ansonsten würde ich die entsprechenden Teile bald ändern. Douba 12:14, 28. Mär. 2007 (CEST)

Das ganze hängt ja davon ab, wie man Graphen mathematisch modelliert. Der Artikel sollte das besser herausstellen, dass es da veraschiedene Möglichkeiten gibt. Wenn man nur ungerichtete Graphen betrachten will, wird man Graphen nicht so allgemein modellieren, dass man auch gerichtete betrachten kann. --Koethnig 00:21, 31. Mär. 2007 (CEST)

Qualitätssicherung

Hallo, ich setze das Lemma auf Qualitätssicherung, denn es gibt zum Hauptthema Graphentheorie eine Unzahl von Artikeln und Unterthemen und Erklärungsseiten plus Glossar, da blicke ich fast nicht mehr durch!. Habe gerade Löschanträge gestellt und QS-Anträge gemacht.

Siehe dazu auch schon wie oben angemerkt: Abschnitt Graph-Artikel.

Wer noch Lemmas zum selbigen Thema findet: auch bitte hier auflisten bzw. selbst abarbeiten. Danke! Gruß Wikifantexter 16:16, 18. Dez. 2007 (CET)

Unverständlich

Zitat aus dem Artikel: Statt mehrere Linien zwischen zwei Punkten zu zeichnen, kennzeichnet man Mehrfachkanten auch häufig durch ihre Vielfachheit. Was soll das heißen? Gruß Wikifantexter 15:10, 18. Dez. 2007 (CET)

Man schreibt halt an die Kante ran, wie oft sie da sein soll. Wo ist das Problem? --Juliabackhausen 14:23, 3. Apr. 2008 (CEST)

math

statt dem Zeichen für Durchschnitt $\varnothing$ sollte lieber das mathematische Zeichen für die leere Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \emptyset} benutzt werden, um die leere Menge zu kennzeichnen. Leider ist der Artikel geschützt. Desweiteren nutzt man lieber ≠ oder $\neq$ statt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \not =} für leichtere Lesbarkeit (des Markups).

Das Zeichen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varnothing} ist für die leere Menge allgemein gebräuchlich. Welche TeX-Notation leichter lesbar ist, ist von Autor zu Autor verschieden. --Stefan Birkner 17:09, 14. Apr. 2007 (CEST)

Vermutlich, weil Windows lange Zeit das emptyset-Zeichen vermissen ließ, hat man sich mit dem Durchschnittszeichen begnügt. Aber das ist nur eine Theorie. ;) 84.185.88.73 18:36, 18. Apr. 2007 (CEST)

Qualitätssicherung

Verschiedene Lammata zum Thema mathematischer Graph. Ich stelle gerade Löschanträge. Wer Artikel zum Thema findet, bitte hier auflisten. Ich habe verschiedene Lammata schon hier zusammengefasst. Danke! Gruß Wikifantexter 15:25, 18. Dez. 2007 (CET)

Sehe gerade, dass es auch ein Lemma Graphentheorie gibt! Gruß Wikifantexter 16:28, 18. Dez. 2007 (CET)

Digraph (erledigt)

Wer aus der deutschen Wikipedia erfahren möchte, was ein Digraph ist, wird nur im Kreis verwiesen. Ist vermutlich mal wieder das Ergebnis von Änderungen, die von Leuten durchgeführt wurden, die mit den Inhalten der betroffenen Artikel nicht vertraut sind. Merke: Redirektionen ändern ist keine lokal begrenzte Angelegenheit. --130.83.161.40 16:24, 16. Jan. 2008 (CET)

Der Artikel Digraph sollte dich nun zufrieden stellen. --Juliabackhausen 14:48, 3. Apr. 2008 (CEST)

Satz in eine Fußnote übertragen

Ich würde den Satz "E bezeichnet also nicht die Eckenmenge" lieber als Fußnote anbringen am Ende des Artikels. Denn bis zu diesem Satz war die Zuordnung V und E vollkommen klar, nun "spukt" jedoch auch och die fehlerhafte Assoziation E == Ecke durch meinen Kopf. (nicht signierter Beitrag von 80.171.49.176 (Diskussion | Beiträge) 10:34, 15. Mär. 2008 (CET))

Sprachen-Verlinkung

Multigraph: bg:Мултиграф en:Multigraph it:Multigrafo pl:Multigraf pt:Multigrafo

Graph: bg:Граф (математика) en:Graph (mathematics) fr:Graphe (théorie des graphes) hu:Gráf (halmazelmélet) it:Grafo lt:Grafas (matematika) pl:Graf (matematyka) ru:Граф (математика) (nicht signierter Beitrag von Juliabackhausen (Diskussion | Beiträge) 15:12, 3. Apr. 2008 (CEST))

Orientierter Graph

Die englische Wikipedia unterscheidet zwischen einem gerichteten Graph, der sowohl a->b als auch b->a erlaubt, während ein orientierter Graph nur entweder a->b oder b->a enthält. Ich denke, diese unterscheidung ist wesentlich, zum Beispiel für die Anzahl möglicher Zyklen, die gesamtkantenzahl etc. Vielleicht wäre eine Überarbeitung diesbezüglich angebracht? 88.74.254.142 22:17, 20. Apr. 2008 (CEST)

"Abbildungen" V und E

Was sollen denn jeweils Definitionsmenge und Zielmenge dieser "Abbildungen" V und E ("Definitionen") sein? Die Graphen bilden keine Menge, sondern eine echte Klasse. -- Lückenlos^wecken! 22:50, 3. Aug. 2009 (CEST)

Reparatur: Man könnte einfach erklären, dass man ("manchmal") V(G) für die Menge der Knoten und E(G) für die Menge (oder …) der Kanten von G schreibt. Die Schreibweise bringt aber allenfalls etwas, wenn man von mehreren Graphen nebeneinander spricht, z. B. wenn es um Isomorphie geht. Hier im Artikel bringt sie dagegen einfach nichts, und man sollte einfach überall V statt V(G) und E statt E(G) schreiben. -- Lückenlos^wecken! 12:42, 4. Aug. 2009 (CEST)

Ich habe die Notation nicht entfernt, aber etwas anders beschrieben. Ich habe auch das Nachfolgende noch etwas überarbeitet und nehme den Baustein raus. --Zahnradzacken 21:16, 17. Jan. 2011 (CET)

Lol. Wenn sowas simples wie parametrisch polymorphe Paarprojektionen ein Problem darstellen, hat man sich definitiv vermodelliert. Immer diese Mengenlehrler mit ihrem seltsamen Zeug.

Das ganze lässt sich leicht lösen, indem man V und E nicht einen Typ Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X\to Y} gibt, mit Mengen X und Y, sondern so einen wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall A. \forall B. A\times B \to A} (oder entsprechend mit B hinten). Die Zähmung erfolgt hier nicht durch Einschränkung auf Mengen, sondern durch die Parametrizität — keine Funktion, die wirklich diesen Typ hat, kann irgend etwas nicht-triviales oder gar grundlagenerschütterndes machen.

Benutzer:Uwe Lück sei die Lektüre des entsprechenden, leider noch nicht existierenden, Teils von Typentheorie empfohlen. :)

Für den Graph-Artikel ist diese Typangabe jedoch eher nix. Anderes, weitschweifendes, ablenkendes Thema. --Daniel5Ko 21:56, 17. Jan. 2011 (CET)

Dein Ton macht mich etwas zweifeln. Woran genau übst du Kritik? Ist am Abschnitt etwas dringend zu verbessern? --Zahnradzacken 12:43, 18. Jan. 2011 (CET)

Eigentlich an der ursprünglichen Fragestellung. Der voreilige unstrukturierte Sprung zu Klassen und das anschließende "Oh, Gott!" ist nicht notwendig. (Zur Artikelverbesserung kann diese Diskussionsfortsetzung allerdings nicht beitragen... Das war eigentlich eher sinnloses Gesenfe.)--Daniel5Ko 15:13, 18. Jan. 2011 (CET)

Was ist E(G)(e) und E(G)((w,v))?

Scheinbar ist es eine Abbildung, dann wäre eine Definiton im Artikel hilfreich. Ich vermute es ist E(G)(e)=E(e)=e, dann müsste da aber stehen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle E(G)(e)\neq \emptyset} oder |E(G)(e)|>0. So oder so wäre eine genauere Erläuterung hilfreich... --Schönen Gruß "Wohingenau" 00:21, 25. Nov. 2009 (CET)

Es stand schon implizit im Artikel: Bei einem Multigraphen (V,E) ist E eine Multimenge. Das heißt E(x) ist die Häufigkeit von x. Hier wird dann E auch noch erstmal als Abbildung definiert, sodass E(G) die Multimenge ist und E(G)(e) die Häufigkeit. Ich hoffe, einige zusätzliche Erklärungen im Text erleichtern nun das Verständnis. --Zahnradzacken 21:20, 17. Jan. 2011 (CET)

Erweiterung des Artikels - Typen von Graphen und Operationen auf Graphen

Im englischen Artikel werden noch wichtige Typen von (Teil-)Graphen und Operation auf Graphen aufgelisten. Da der Artikel hier auch ein Übersichtsartikel ist, wäre es meiner Meinung ganz sinvoll wenn diese Sachen hier auch aufgelistet werden. Leider bin ich noch nicht so mit dem Thema vertraut und hab auch keine Literatur zur Hand. Weiß also nicht ob es Sinn macht das einfach so zu überesetzen und hier einzufügen... --Schönen Gruß "Wohingenau" 00:32, 25. Nov. 2009 (CET)

Sehr unübersichtlicher Artikel

Ich finde den Artikel sehr unübersichtlich. Man kann doch auch erst eine Definition geben, dann ein paar Beispiele dazu. Also z.B.
Ungerichteter Graph: Definition, Beispiel, Bild
Gerichteter Graph: Definition, Beispiel, Bild
Multigraph: Definition, Beispiel, Bild (ein sehr anschauliches gibt es im englischsprachigen Multigraph-Artikel)
Und was die Laien betrifft, die alles erklärt haben wollen, denke ich, diese Diskussion zieht so manchen mathematischen Artikel in Mitleidenschaft. Man kann eben nicht alles so erklären, daß es jeder versteht. Wer z.B. den Unterschied zwischen einem 2-Tupel und einer zweielementigen Menge nicht versteht, wird auch den Unterschied zwischen einem gerichteten und einem ungerichtetem Graphen nicht verstehen können
(nicht signierter Beitrag von 94.79.132.64 (Diskussion | Beiträge) 09:51, 27. Apr. 2010 (CEST))

Definition der Morphismen

Ich vermisse bei den einzelnene Definitionen die Definition der dazugehörigen Morphismen. Sollte man denn nicht Interesse haben, zwei Graphen vergleichen zu wollen? --Peter Addor 07:46, 22. Feb. 2011 (CET)

Kantenidentität in Multigraphen

Ich kenne aus dem Bereich der Graphtransformation diese Definition: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G = (V,E,s,t), V \cap E = \emptyset} wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s,t:E \rightarrow V} jeder Kante ihren Quell- bzw. Zielknoten zuordnen (alternativ geht es auch mit nur einer Abbildung $edge:E\rightarrow V\times V$).

Dadurch ist es z.B. möglich, zwei Kanten zwischen denselben Knoten unterschiedliche Labels/Attribute zuzuordnen, was bei Multimengen nicht möglich ist. Mit der Definition über Multimengen kenne ich mich nicht so gut aus - hat die irgendwelche Vorteile?

Sollte man diese Definition als Alternative mit reinnehmen oder vielleicht sogar die jetzige ersetzen? -- 92.227.21.219 20:49, 24. Mai 2011 (CEST)

Der Artikel könnte (vor allem) im Abschnitt Definitionen eine grundlegende Überarbeitung vertragen. Er sieht aus wie ein Auszug aus dem Buch von R. Diestel, nur dass hier das Layout schlechter ist. Ich finde es nicht sinnvoll, dass der Abschnitt so überladen ist. Man bräuchte mindestens mehr Formatierung, aber am besten einen anderen Ansatz. Zugleich wäre es gut, wenn man alternative Definitionen hätte, wie etwa deine von oben. Bisher liest es sich so, als wäre die Definition im Artikel die einzig richtige. Wer hat Vorschläge? --Zahnradzacken 14:52, 25. Mai 2011 (CEST)

Schlingen fehlen

Laut im Artikel gegebener Definition ist E in ungerichteten Graphen ohne Mehrfachkanten eine Teilmenge aller 2-elementigen Teilmengen von V. Ich denke, man braucht auch 1-elementige Teilmengen, sonst sind Schlingen (Kanten, die einen Knoten mit sich selbst verbinden) unmöglich. -- UKoch (Diskussion) 20:31, 9. Mai 2012 (CEST)

Der Artikel basiert überwiegend auf Reinhard Diestels Buch. Dort sind Schleifen nur in Multigraphen erlaubt. Andere Autoren lassen auch andere Definitionen zu (siehe en:Graph (mathematics)#Multigraph und Schleife (Graphentheorie)), aber ich finde den Artikel schon verschachtelt genug, um das alles an einem Ort zu erklären. --Zahnradzacken (Diskussion) 08:29, 13. Mai 2012 (CEST)

Gerichteten Graphen mit eigenständigen Mehrfachkanten

Ich nehme Bezug auf diese Ergänzung. Hier wird der Begriff der "gerichteten Graphen mit eigenständigen Mehrfachkanten" eingeführt. Die gegebene Definition verstehe ich als äquivalent zur Definition von gerichteten Graphen mit Mehrfachkanten. Sehe ich das richtig oder kann mir jemand den Unterschied aufzeigen? Viele Grüße -- Phil1881 (Diskussion) 11:17, 2. Jun. 2012 (CEST)

Naja, ein Unterschied wäre zum Beispiel, dass man bei dem hinzugefügten Graphentyp zwischen zwei Knoten unendlich viele Kanten haben kann, und bei dem anderen nicht. --Daniel5Ko (Diskussion) 15:00, 2. Jun. 2012 (CEST)

Hallo, vielen Dank für deine Antwort! Ich verstehe Multimengen so, dass dort auch unendlich gleiche Elemente enthalten sein können. Also warum können in einer Multimenge über dem kartesischen Produkt $V\times V$ nicht auch unendlich viele Kanten definiert sein? Viele Grüße -- Phil1881 (Diskussion) 13:25, 3. Jun. 2012 (CEST)

Wenn eine Multimenge über $A$ als Funktion $A\to \mathbb {N}$ definiert wird, dann ist genau dort der Grund.

Aber ignorieren wir diesen Unterschied mal (er kann beseitigt werden, wenn man das will) und gehen zum nächsten Unterschied: Man zähle die Graphen, die genau zwei Knoten, X,Y, haben und genau eine Kante von X nach Y. Wieviele gibt's? In dem einen Fall immer einen, im anderen |E|, wenn man E vor dem Zählen festlegt, oder eine undefinierte Anzahl, wenn E je Graph variieren darf. --Daniel5Ko (Diskussion) 17:08, 3. Jun. 2012 (CEST)

Hallo, gibt es nicht im Beispiel "zwei Knoten, dazwischen genau eine Kante" bis auf Isomorphie nur einen Graphen? Weil man die Kanten unterschiedlich bezeichnen kann, ist das doch immer noch derselbe (isomorphe) Graph. Viele Grüße -- Phil1881 (Diskussion) 14:14, 4. Jun. 2012 (CEST)

Richtig. Bis auf Isomorphie. --Daniel5Ko (Diskussion) 19:47, 4. Jun. 2012 (CEST)

Die Varianten unterscheiden sich darin, ob man parallele Kanten unterscheiden kann oder nicht. Wenn man nur einen einzigen Graphen betrachtet, ist das vielleicht irrelevant.

Es macht aber einen großen Unterschied, wenn man Graphhomomorphismen betrachet. Wenn man die Kanten unterscheiden kann, kann man genau festlegen, welche Kante auf welche Bildkante abgebildet wird. Das nimmt man beispielsweise für typisierte Graphen her: Da ordnet ein Graphhomomorphismus jedem Knoten und jeder Kante einen Typ zu. Wie soll man einen solchen Graphhomomorphismus definieren, wenn man die Kanten nicht unterscheiden kann? -- 92.226.192.117 09:17, 11. Okt. 2012 (CEST)

Schwerpunkt des Artikels

Eigentlich ist ein Graph in der Mathematik, speziell in der Graphentheorie m.E. klar definiert, nämlich als einfacher, ungerichteter Graph in Terminologie dieses Lemmas.

Zum Beleg schreibt G. Diestel in Abschnitt 0.10 "Verwandte Begriffsbildungen" seiner "Graphentheorie", die auch im Lemma referenziert wird, einleitend: Der Übersicht halber erwähnen wir in diesem Abschnitt noch einige Begriffe, die im Text nicht oder nur am Rande vorkommen, wonach er all die Hyper- und Multi-Graphen und ihre Freunde listet, die die restlichen 300 Seiten keine Rolle mehr spielen. Ergänzend möchte ich auch auf die Definition in Graphentheorie verweisen.

Im Lemma werden diese aber ganz nach vorne gekehrt, der eigentliche Graphenbegriff, jedenfalls soweit er die Graphentheorie betrifft, aber nicht entsprechend hervorgehoben und mithin verstellt und zugedeckt. Noch bevor Graphen definiert werden, stehen im Lemma die Definition von Multigraphen, Digraphen und Hypergraphen.

M.E. ist das für jemand, der wissen möchte, was unter "Graph" im Sinne der Graphentheorie zu verstehen ist, unglücklich.

Mein Vorschlag für dieses Lemma ist, hier Diestel zu folgen und die Definition des Graphen im Sinne der Graphentheorie klar von verwandten Begriffen zu trennen.

-- Lowtec (Diskussion) 00:20, 9. Mär. 2014 (CET)

An sich finde ich es gar nicht so schlecht, in diesem Artikel alle möglichen Typen von Graphen anzusprechen. Strukturell kann der Artikel aber sicher noch verbessert werden. Für einfache ungerichtete Graphen hätten wir bereits den Artikel Einfacher Graph. Grüße, --Quartl (Diskussion) 20:40, 9. Mär. 2014 (CET)

Die verschiedenen Begriffsbildungen zusammenfassend darzustellen, finde ich auch gut. Hieße das Lemma "Graph (Begriffsbildungen)" o.ä., wäre das auch alles vollkommen in Ordnung. Nun ist das Lemma aber "Graph (Graphentheorie)" und damit muss m.E. auch die Fassung im Sinne der Graphentheorie klar herausgehoben werden. Hmm, vielleicht versuche ich eine "strukturelle Verbesserung" in diesem Sinne... --Lowtec (Diskussion) 11:54, 11. Mär. 2014 (CET)

Graph aus mehreren unabhängigen Teilen?

Korrigiert mich bitte, wenn ich falsch liege, aber meiner Meinung nach geht aus der aktuellen Definition eines Graphen nicht hervor, dass jeder Knoten mit einem anderen verbunden sein muss (z. B., indem jeder Knoten in E vorkommen muss). Auch finde ich nicht die (allgemeinere) Bedingung, dass man von einem Knoten aus jeden anderen erreichen können muss. Wenn dies nämlich nicht der Fall wäre, gäbe es Graphen, die quasi aus mehreren, nicht verbundenen Teilen bestehen würden! Dann wiederum wären aber die bestehenden Skizzen nicht allgemein genug. Was denkt ihr? (nicht signierter Beitrag von 87.149.73.152 (Diskussion) 19:21, 9. Jan. 2015 (CET))

Richtig, Graphen können auch unzusammenhängend sein und dann aus mehreren Zusammenhangskomponenten bestehen. --Quartl (Diskussion) 19:59, 9. Jan. 2015 (CET)