Diskussion:Matching (Graphentheorie)

k-Faktor

Hallo

ich habe den Artikel k-Faktor in eine Begriffsklärungsweiche geändert. Wolfgang Feld

So ist es richtig! :-) --Coma 16:55, 14. Okt 2005 (CEST) Die zusätzliche Information in diesem Artikel ist aber trotzdem überflüssig, niemand der diesen Artikel sucht interessiert das... Coma 16:57, 14. Okt 2005 (CEST)

Algemeines

Wieso kommt eigentlich Jack Edmonds bzw. sein Matching-Algorithmus hier nicht vor? Und ist der Ausdruck Paarung wirklich üblich? Ich bin ja auch kein Freund von Anglizismen, aber bisher kannte ich nur die Bezeichnung Matching ... --Christian Gawron 17:50, 30. Dez 2005 (CET)

Das Wort "Paarung" wird z.B. von Reinhard Diestel in "Graphentheorie" verwendet. --Koethnig 18:01, 30. Dez 2005 (CET)

Paarung bedeutet aber 2 --schnellmerker (nicht signierter Beitrag von 79.247.177.43 (Diskussion | Beiträge) 10:53, 9. Aug. 2009 (CEST))

Ich würde "Zuordnung" bzw. "Zuordnungsproblem" bevorzugen, das schafft den Anglizismus auch ab und entspricht in meiner Vorstellung genau dem genannten Problem (es gibt sogar einen Wiki-Artikel "Zuordnungsproblem"). --Nyrygyk (Diskussion) 13:30, 6. Nov. 2013 (CET)

Überschneidung

Es gibt Überschneidungen zwischen diesem Artikel und Paarung (Graphentheorie). Genaugenommen ist das hier nur die größere Version. Also können wir Paarung (Graphentheorie) doch eigentlich löschen und hierher redirecten. Was meint Ihr? --magnummandel 21:01, 11. Feb. 2007 (CET)

Ich bin für folgende Vorgehensweise:

• Paarung (Graphentheorie) löschen
• Paarungen in Graphen nach Paarung (Graphentheorie) verschieben
• Paarungen in Graphen löschen

Die jetzige Struktur mit den Übersichtsartikeln ist ein Anliegen von Benutzer:Koethnig, deshalb würde ich auf seine Meinung warten.--Stefan Birkner 00:23, 12. Feb. 2007 (CET)

Das richtige Vorgehen ist: Den Artikel Paarungen in Graphen so zu lassen, wie er ist. Den Inhalt von von Paarung (Graphentheorie) ins Glossar Graphentheorie zu verschieben. Links auf den Artikel "Paarung (Graphentheorie)" anpassen und den Artikel dann zu löschen. --11:41, 13. Feb. 2007 (CET)

Beweise und Schreibstil

Ist es Absicht, dass in dem letzten Abschnitt 9x das Wort "leicht" im Zusammenhang mit der Beweisbarkeit vorkommt? Wenn es so leicht ist, solle entsprechende Person bitte die Beweise dazu schreiben, verlinken, oder sie sonst irgendwie hinterlegen, aber nicht einfach behaupten es sei so. Für mich als Ottonormalstudent sind viele dieser Beweise nicht 'einfach'. Dies ist eine Unsitte, die auch in sehr vielen Fachbüchern vorkommt und mich immer wieder auf die Palme bringt. --HaraldBlatand 18:21, 8. Mär. 2007 (CET)

1. Du hast recht, dass ist eine Unsitte!
2. Beim ersten "leicht" steht der Beweis da! Er ist wohl nur so leicht, dass du ihn übersehen hast. Das "leicht" war also überflüssig.
3. Das zweite leicht konnte ich nicht so leicht herausformulieren. Treffender wäre, dass der Beweis relativ kurz ausfallen kann und wenig weiterführende Kentnisse benötigt. Nichtmal innerhalb des Gebietes der Graphentheorie.
4. Das dritte leicht fand selbst ich als "Experte" nicht so leicht und habe das durch das Wort "einfach" ersetzt, weil: einfach ist der Algorithmus. :-)
5. Das vierte "leicht" ist tatsächlich auch wieder ganz leicht.
6. Das fünfte "leicht" kann man auch durch ein "direkt" ersetzten, was ich getan habe.
7. Das sechste "leicht" war dann überflüssig durch umformulierung. Der Beweis steht da.
8. Das siebete "leicht" war überflüssig, weil die Idee des Beweises da steht.
9. Das achte und neunte leicht war ebenfalls überflüssig durch die umgebene Formulierung.

--Koethnig 11:50, 9. Mär. 2007 (CET)

Algorithmen zur Lösung des Assignment-Problems

ich habe den Eindruck, dass die Verweise auf Sätze und Algorithmen in 'wichtige Aussagen' und 'Paarungen in bipartiten Graphen' etwas unstrukturiert präsentiert werden, bzw. diese beiden Absätze irgendwie so nicht zu trennen sind. Im Umfeld Paarung gibt es anscheinend auch einige verwandte Artikel, die nichts voneinander wissen (z.B. bereits die Übersichtsseiten Matching - Paarung und Paarung - Ungarische Methode).

Vielleicht findet sich jemand sattelfestes, der das mal überarbeiten kann?

Und möchte jemand evtl. Lösungen für 'gewichtetes bipartites matching' mal überblicksmäßig erklären ('ungarischer Algorithmus', 'Kuhn-Munkres', 'primal-duale Lösung', 'Knotenbeschriftung', 'Auktionsalgorithmus')?

Vielen Dank, Micha. --194.121.90.163 10:46, 17. Jan. 2008 (CET)

Beziehung zum maximalen Fluss

Da hat sich wohl ein Fehler eingeschlichen, es sollte "größte Paarung" heissen und nicht "maximale Paarung". -- Webskipper 23:34, 3. Feb. 2010 (CET)

dichte graphen haben doch IMMER (fast) perfekte Paarungen, oder?

Mich stört die Formulierung "In [dichten Graphen] gibt es meistens auch eine (fast) perfekte Paarung". Dichte Graphen sind meines Wissens so definiert, dass ihr minimalgrad >= n/2 ist. Solche Graphen haben nach Satz von Dirac einen Hamiltonkreis, von dem aus man alternierend Kanten nehmen kann und so IMMER eine (fast) perfekte Paarung findet. Insofern sollte IMHO das "meistens" gestrichen werden... -- AlgorithMan 20:47, 22. Mär. 2010 (CET)

Verbesserung des Artikels?

Im Zuge des Schreibwettbewerbs hat sich ja viel in dem Artikel getan, aber ist er im Vergleich zu dieser Version wirklich besser geworden? Der alte Artikel gab meiner Meinung einen guten Gesamtüberblick. Am besten gefallen hatte mir das allgemeinverständliche Beispiel, um überhaupt das Prinzip von Matchings zu verstehen. Der Überblick über die wichtigsten Sätze und Algorithmen war auch angebracht. Von dem ist kaum noch etwas geblieben. Die Allgemeinverständlichkeit hatte am meisten zu leiden. Beim allgemeinen Fall werden jetzt in aller Ausführlichkeit der Satz von Tutte und der Algorithmus von Edmonds erklärt, was eigentlich eher in eigene Artikel gehört. Außerdem ist die Seite jetzt vielzusehr mit Formeln vollgepackt. Wirklich sehr schade… --Sinuhe20 18:23, 11. Okt. 2011 (CEST)

Bergeh?

Heißt der Mann, dessen Sätze zitiert werden, nicht "Berge"?

Thomas (nicht signierter Beitrag von 92.252.38.1 (Diskussion) 23:14, 29. Nov. 2011)

Hallo Thomas. Ja, ich habe es verbessert. Danke. Das war wohl ein Tippfehler.--Pacogo7 22:24, 29. Nov. 2011 (CET)

Bilder am Schluß beim Beispiel des Edmonds Algorithmus passen nicht

Hallo, das Beispiel über den Verlauf des Algorithmus von Edmonds am schluss hinkt. Die Bilder bzw. die beschreibungen scheinen durcheinander.

Und können in der Diskussion Themen wie 'Berge wird ohne "h" geschrieben' gelöscht werden, wenn sie erledigt sind ? (nicht signierter Beitrag von 77.185.15.212 (Diskussion) 16:52, 17. Mär. 2012 (CET))

Definitionen: nicht erweiterbar

Müsste es unter „Definitionen“ -> „nicht erweiterbar“ statt

falls es keine Kante e ∈ E derart gibt [...]

nicht heißen:

falls es keine Kante e ∈ E \ M derart gibt [...] (nicht signierter Beitrag von 134.2.15.240 (Diskussion) 10:19, 11. Mär. 2013 (CET))

Völlig richtig bemerkt, wurde von mir geändert. Andreschulz (Diskussion) 15:07, 9. Mai 2013 (CEST)

Petersens Satz als Eulerkreisproblem

Im Artikel heißt es

Die Tatsache (2), bekannt als Satz von Petersen, lässt sich auch als eine leichte Verallgemeinerung des Eulerkreisproblems formulieren.

Aha, ich finde das überhaupt nicht offensichtlich und kenne eine solche Verallgemeinerung nicht. Vielleicht kann man hier ja mal eine Quelle angeben??? Andreschulz (Diskussion) 15:04, 9. Mai 2013 (CEST)

Steht doch in der Anmerkung, dass das aus dem Vorwort von Lovász & Plummer hervorgeht. Wie das genau funktionieren soll, buchstabieren sie zumindest an dieser Stelle aber leider auch nicht aus (und ganz spontan sehe ich die Verbindung erst einmal auch nicht). --goiken 16:11, 9. Mai 2013 (CEST)

Gesättigte und maximale Matchings

In der Literatur an meiner Universität wird anstatt von "nicht erweiterbaren" Matchings generell von gesättigten Matchings gesprochen.

Als Definition ist die (meiner Meinung nach leichter verständlichere) folgende angegeben: Ein Matching heißt gesättigt, wenn es in dem Graphen kein weiteres Matching gibt, dass mindestens das gesättigte Matching enthält (und zusätzlich noch weitere Kanten).

Eventuell könnte man den Begriff mit aufnehmen?

Bilder überflüssig

Die Bilder haben keinen nennenswerten Informationsgehalt. Was hat das mit einem Matching zu tun, dass sind 6 gelbe Quadrate. Daneben nochmal genau das gleiche, wenn nicht selbe Bild. Sollte durch in vernünftiges Bild ersetzt werden.

--77.179.136.177 18:56, 12. Jul. 2016 (CEST)

Die fetten Kanten sollen gematchte Kanten darstellen. (nicht signierter Beitrag von 217.82.225.250 (Diskussion) 23:26, 13. Jul 2016 (CEST))