Das Problem ist folgendes: Bei einer poset der Teilmenge S die maximalen Elemente von S. findenFinding maximalen Elemente einer Teilmenge des Poset
Zum Beispiel das hass Diagramm des poset in http://ndp.jct.ac.il/tutorials/Discrete/node34.html betrachten. Bei einer Teilmenge davon: {12, 2, 8} sind die maximalen Elemente 12 und 8.
Ich weiß nicht, ob ich das Problem genau beschreibe. Ich denke, das Problem könnte eine Sortierung oder Berechnung der transitiven Schließung beinhalten, aber ich bin ein wenig verwirrt.
Können Sie mir einen Ansatz für einen schnellen Algorithmus geben? Ich möchte es in O (n^2)
Vielen Dank.
Eine kleine Erläuterung. Meine Anwendung verwendet RDF-Grafiken. Zwei Knoten sind vergleichbar, wenn eine bestimmte Kante vorhanden ist, die die <-Beziehung darstellt. Zwei Knoten könnten vergleichbar sein, wenn es eine solche explizite Beziehung oder eine implizite transitive Beziehung gibt.
Also nehmen Sie an, dass das Hass-Diagramm genau mein RDF-Diagramm ist. Wenn ich von 2 bei einer Tiefensuche anfange, woher weiß ich, dass die 8 und 12 nicht vergleichbar sind? Sie sind möglicherweise nicht explizit, aber sie könnten implizit sein.
Wenn zwei Knoten vergleichbar sind. die Bestellbeziehung, dann muss mindestens einer von ihnen einen Nachfolgerknoten haben, der die Bestellbeziehung "überträgt", richtig? –
Ja das ist richtig. Wenn Sie jedoch den Pfad a-b-c haben, sind a und c "implizit" vergleichbar. Darauf aufbauend vermute ich, dass ich die transitive Schließung jedes Knotens der Teilmenge berechnen muss und die "Reinigung" der vergleichbaren Elemente vornehmen muss. – Alex
Angenommen, a-b impliziert a