Paarung (Graphentheorie) in NICHT bipartiten Graphen

[yankee]

Hi @ll,

ich habe ein Paarungsproblem in einem ungerichteten ungewichteten Graphen.
Sinn der Sache ist es so viele Paare wie möglich zu finden.

Ich drehe langsam am Rad, weil ich mit Google schon hunderte Dokumente gefunden habe, die beschreiben, dass man sowas effizient lösen kann und dann leider einlenken, dass sie in dem jeweiligen Dokument jetzt aber nur mit einem bipartiten Graphen beschäftigen. Mein Graph ist aber nicht bipartit. :wall:

Wie gehe ich da vor? Kennt jemand ein (verständliches) Dokument, dass nahe bringt, wie man dieses Problem behandelt?

[Gausi]

Ich hab mir den Artikel nicht durchgelesen, aber Efficient algorithms for finding maximum matching in graphs hört sich jetzt nicht schlecht an. Gefunden über scholar.google.com

Generell scheint das über diese alternierenden Pfade zu gehen - d.h. man fängt mit einem Matching an, und verbessert das Stück für Stück über diese Pfade.

[WS1976]

Hallo,

ich versteh nur Bahnhof! Hat das irgendetwas mit Programmiertechnischen Dingen zu tun?
Oder handelt es sich vielleicht um eine Frage an die mathematische Fakultät Karlsruhe?

Grüsse
Rainer

[Dax]

Das klingt doch sehr nach der ersten Aufgabe des BWInf diesen Jahres...

[yankee]

Zitat:

Zitat von Gausi

Ich hab mir den Artikel nicht durchgelesen, aber Efficient algorithms for finding maximum matching in graphs hört sich jetzt nicht schlecht an. Gefunden über scholar.google.com

Mhh... Kann man an den Artikel auch irgendwie ohne zu bezahlen dran kommen? ;-).

Zitat:

Zitat von WS1976

ich versteh nur Bahnhof! Hat das irgendetwas mit Programmiertechnischen Dingen zu tun?
Oder handelt es sich vielleicht um eine Frage an die mathematische Fakultät Karlsruhe?

Doch, es hat was mit Programmieren zu tun. Graphentheorie eben.

Zitat:

Zitat von Dax

Das klingt doch sehr nach der ersten Aufgabe des BWInf diesen Jahres...

:-P

[WS1976]

Hallo,

Graphentheorie hat absolut nichts mit Programmieren zu tun, sondern ist ein Teilgebiet der Mathematik.
(Vorlesungskatalog WS2006 TU Karlsruhe)
Wie willst du eine vernünftige Antwort bekommen, wenn du hier solche hochspezialisierte Fragen stellst, die kaum ein Mathematikstudent beantworten kann?
Wo ist der Bezug deiner Frage zu einem programmiertechnischen Problem?
Unser Dr. (der Mathematik hier im Hause) kanns jedenfalls nicht!

Gruss
Rainer
PS: Ich weiss ich mach wieder unbeliebt, aber das gehört (in dieser Form) einfach nicht hierher!

[yankee]

Zitat:

Zitat von WS1976

Graphentheorie hat absolut nichts mit Programmieren zu tun, sondern ist ein Teilgebiet der Mathematik.

Komisch, dass Graphentheorie dann in den Abiturvorgaben vom Informatik LK steht. Nur recht oberflächlich, Dijkstra und das wars, aber es steht drin. Gut, die Graphen selbst kommen vielleicht aus der Mathematik, aber die ganzen Problemlösung (kürzester Weg, Paarungsprobleme, Eulersche Kreise,...) sind IMHO Informatikthemen. Es geht schliesslich um Algorithmen.
Wie du sicherlich erfolgreich ignoriert hast, geht es mir um die erste Aufgabe des Bundeswettberwerbs für INFORMATIK.

Zitat:

Zitat von WS1976

Wie willst du eine vernünftige Antwort bekommen, wenn du hier solche hochspezialisierte Fragen stellst, die kaum ein Mathematikstudent beantworten kann?

In dem ich statt Mathematikstudenten einfach Informatiker Frage.

Zitat:

Zitat von WS1976

Wo ist der Bezug deiner Frage zu einem programmiertechnischen Problem?

siehe oben.

Zitat:

Zitat von WS1976

Unser Dr. (der Mathematik hier im Hause) kanns jedenfalls nicht!

Hängt vielleicht damit zusammen, dass er Dr Mathematik und nicht Informatik ist.

Zitat:

Zitat von WS1976

PS: Ich weiss ich mach wieder unbeliebt, aber das gehört (in dieser Form) einfach nicht hierher!

Stimmt. Du machst dich unbeliebt und das gehört hier auch nicht her. Es geht hier um ein Paarungsproblem und nicht über die Diskussionsrunde "fröhliches Fachgebietraten".


Ich bin zumindest erstmal jedenfalls zu einer Lösung gekommen: Ich habe mich in letzter Zeit mit dem Buch "Das Geheimnis des kürzesten Weges" mit Graphentheorien beschäftigt. Bin aber erst auf der Hälte des Buchs angekommen und bin gerade erst auf die Idee gekommen mal vorzublättern um zu schauen, ob Paarungsprobleme da noch behandelt werden. Und tatsächlich.
Wenn das Buch weiterhin so verständlich ist wie bisher weiss ich demnächst mehr als jeder Mathestudent :-DDD.

Vielen Dank @Gausi auf jeden Fall, dass du versucht hast mir zu helfen :-).

[Gausi]

Hey, kein Problem. Den Artikel kriegt man übrigens "einfach so", wenn man den Link über ein Uni-Netz (oder auch andere ähnliche Institutionen) aufruft. Dann kommt direkt das PDF, nicht so ne komische Login-Abfrage ;-).

[HERMES]

@WS1976:
1. Sein wann hat Karlsruhe eine TU???
2. (Unter der annahmen, dass du Uni Karlsruhe(TH) meinst) Dort gibt es Vorlesungen für Informatiker die sich mit Graphentheorie und Graphenalgorithmen beschäftigen.
3. Warum sollte man hier keine Theoriefragen diskutieren dürfen, es tauchen hier ja auch immer mal wieder Physik, Chemie oder andere fragen auf

[WS1976]

Hallo,
seit ich dort mein Diplom gemacht hab. Vielleicht heisst das heute nicht mehr so.
Zu meiner Zeit wars die Technische Universität Karlsruhe.

Rainer