4. Einstieg in Graphentheorie

Einstieg in Graphentheorie

  • ?

    Hallo,
    ich wollte mal anfangen, mich ein klein wenig Algorithmen zu widmen und bin dabei auf folgendes Problem gestoßen:
    Ich habe eine Menge an Personen. Jede Person ist mit einer bestimmten Teilmenge anderer Personen befreundet. Nun möchten sich alle jeweiligen Freunde treffen. Da sie aber nicht sehr viel Geld haben, kann jede Person nur zu einer bestimmten Anzahl an Freunden reisen. Nun muss ich herausfinden, wer wohin reist, damit sich alle Freunde mal getroffen haben.
    Hier mal ein kleines Beispiel zur Verdeutlichung:
    Person A hat B und C als Freund und kann 1 mal reisen.
    Person B hat A, C und D als Freund und kann 2 mal reisen.
    Person C hat A, B und D als Freund und kann 2 mal reisen.
    Person D hat B und C als Freund und kann 0 mal reisen.

    Als Ergebnis soll dann rauskommen, dass
    A zu B
    B zu C und D
    C zu A und D
    reist.
    Nun ich weiß, dass das Ergebnis ein gerichteter Graph ist, und dass auf Wikipedia alle Algorithmen dazu aufgelistet sind. Jedoch versteh ich die Erläuterungen wegen meinem begrenzten mathematischen Wissen nur sehr schwer und weiß nun nicht, welcher nun der passende Algorithmus für mein Problem ist.
    Könnt ihr mir da helfen? 🙂

    0
  • ?

    Ich möchte nicht aufdringlich sein, aber habt ihr wirklich keine Antwort? Habe ich das ganze irgendwie zu seltsam erklärt? 🤡

    0
  • ?

    GraphJonny schrieb:

    Ich möchte nicht aufdringlich sein, aber habt ihr wirklich keine Antwort? Habe ich das ganze irgendwie zu seltsam erklärt? 🤡

    Bloß weil du dein Ergebnis als Graph aufschreiben kannst, heißt das noch lange nicht, dass dir Graphentheorie weiter hilft.

    Falls jede Person zu genau einer andere Person reisen soll, dann ist dein Problem ein Matching-Problem. Wenn jede Person mehr als einmal Reisen kann, dann fällt mir spontan kein Graphenalgorithmus ein, der dir weiter hilft.

    0
  • ?

    ProgChild schrieb:

    Falls jede Person zu genau einer andere Person reisen soll, dann ist dein Problem ein Matching-Problem. Wenn jede Person mehr als einmal Reisen kann, dann fällt mir spontan kein Graphenalgorithmus ein, der dir weiter hilft.

    Die Anzahl der Reisen variiert wie gesagt leider. Und wenn es jetzt kein Algorithmus aus der Grpahentheorie sein muss, habt ihr dann eine Idee?

    0
  • M

    Es geht in polynomieller Zeit, weil sich das Problem als lineares Programm darstellen lässt. Einen praktikablen Algorithmus hab ich allerdings nich parat. Woher kommt denn die Aufgabenstellung?

    0
  • M

    OK, ich habe eine Lösung. Meine erste Überlegung war Folgende: Für einen Knoten v, sei c(v) die Anzahl der Reise, die der Knoten unternehmen darf. Analog sei für eine Knotenmenge U der Wert c(U) gleich der Summe der Reisen, wie oft die Knoten in U insgesamt reisen dürfen. Dann gibt es genau dann eine Lösung für das Problem, wenn für jede Teilmenge U von V gilt: c(U) >= |E(G[U])|, wobei G(U) der von U induzierte Graph ist. Das sieht schonmal ziemlich nach dem Heiratssatz aus und genau so kann man das Problem auch lösen.

    Sei ein Graph G = (V, E) gegeben. Konstruiere einen Graphen G':
    V(G') = E(G') + Θ. Dabei seien in Θ für jeden Knoten v aus V(G) so viele Knoten w_{v,1}, ..., w_{v,c(v)}, wie Knoten v Reisen machen darf.

    In E(G') sind alle möglichen Kanten f={w,z}, wobei w = {x,y} aus E(G) ist und z ein von x oder y induzierter Knoten in Θ.

    Finde nun ein perfektes maximales Matching in G' (Kardinalität |E(G)|). Dieses ist zugleich die Lösung für das ursprüngliche Problem: Jede Kante f = {w,z} gibt die Orientierung der Kante w in G vor, nämlich von dem Knoten weg, der z induziert hat.

    Edit: Das Matching kann natürlich nicht perfekt sein, wenn die Partitionen nicht gleich groß sind.

    0
  • ?

    Michael E. schrieb:

    Es geht in polynomieller Zeit, weil sich das Problem als lineares Programm darstellen lässt.

    Mit welchem Algorithmus löst du denn eine lineare Optimierungsaufgabe in polynomieller Zeit?

    0
  • M

    ProgChild schrieb:

    Mit welchem Algorithmus löst du denn eine lineare Optimierungsaufgabe in polynomieller Zeit?

    Z.B. mit der Ellipsoidmethode von Khachiyan oder dem Innere-Punkte-Verfahren von Karmarkar. Die sind zugegebenermaßen in der Praxis nicht relevant, weil der Simplexalgorithmus schneller ist, aber hier ganz hilfreich, weil sie eine obere Schranke für die Komplexität liefern.

    0
  • M

    Sicher Lineare Optimierung und nicht ganzzahlige Lineare Optimierung (NPc)

    0
  • ?

    Wow, danke Michael E. für deine Mühen und die ausführliche Erklärung 🙂
    Fürs erste sieht das ganze verständlich aus, aber ich lass es mir alles nochmal durch den Kopf gehen, wenn ich mehr Zeit habe.
    Ich werde mich vielleicht wahrscheinlich noch mal melden, wenn ich Fragen habe 😉

    0
Anmelden zum Antworten