Könnte mir jemand diesen Teil erklären:
Seit einiger Zeit betrachtet Herr O-dot sogar potenzielle Lebensgraphen. Ein PLG ist ein ungerichteter
Graph, der Lebensgraph einer Gruppe von Personen sein könnte, für den es also
Zeitspannen gibt, eine für jeden Knoten, so dass zwei Zeitspannen sich genau dann überlappen,
wenn es zwischen den beiden entsprechenden Knoten eine Kante gibt.
Nachdem er es länger vermutet hatte, konnte Herr O-dot neulich beweisen, dass es einen
ungerichteten Graphen gibt, der kein PLG ist. Allerdings hat er es noch nicht geschafft, einen
PLG-Tester zu programmieren, der entscheiden soll, ob ein vorliegender Graph ein PLG ist.
Denn diesen verstehe ich einfach nicht, und meine Informatiklehrerin auch nicht.
Michael Jungmair said:
Könnte mir jemand diesen Teil erklären:
Ein PLG ist ein ungerichteter
Graph, der Lebensgraph einer Gruppe von Personen sein könnte, für den es also
Zeitspannen gibt, eine für jeden Knoten, so dass zwei Zeitspannen sich genau dann überlappen,
wenn es zwischen den beiden entsprechenden Knoten eine Kante gibt.
Zugegeben, den Satz könnte man auch in mehrere Sätze zerlegen ...
Erklärt ist die Angelegenheit ja nun schon. Ein Beispiel für einen PLG ist genau der Graph aus der Abbildung, halt ohne die Beschriftungen in den Knoten.
Viel Erfolg!
Also wie ich das jetzt verstanden habe, muss man (wie auch immer es realisiert wird)
Allerdings frage ich mich was bei Teilaufgabe 2) gemeint ist:
"Wenn ein Eingabegraph kein PLG ist, soll eine minimale Teilmenge der Knoten ausgegeben werden, so dass bereits diese Knoten mit den Kanten zwischen ihnen keinen PLG bilden."
Wenn der Eingabegraph doch schon kein PLG ist, soll man also die Knoten heraussuchen, ohne die man einen PLG erhällt ?
LG
N Q said:
Also wie ich das jetzt verstanden habe, muss man (wie auch immer es realisiert wird)
- einen Graph eingeben (ohne die Angaben zur Lebenszeit).
- überprüfen, ob dieser Graph ein PLG sein könnte
- Lebenszeiten finden, so dass der Graph immernoch einen Lebensgraphen darstellt
zu 2: Die PLG-Eigenschaft ist definiert (wenn auch nicht so leicht verständlich ... ;) - also nicht "sein könnte", sondern "ist". Und: Überlege, in wie weit sich 2. und 3. unterscheiden.
Allerdings frage ich mich was bei Teilaufgabe 2) gemeint ist:
"Wenn ein Eingabegraph kein PLG ist, soll eine minimale Teilmenge der Knoten ausgegeben werden, so dass bereits diese Knoten mit den Kanten zwischen ihnen keinen PLG bilden."
Wenn der Eingabegraph doch schon kein PLG ist, soll man also die Knoten heraussuchen, ohne die man einen PLG erhällt ?
Ein Teilgraph ist zu identifizieren, aber eben einer mit möglichst wenig Knoten, der dann kein PLG ist. Was daraus für den Graphen mit der verbleibenden Knotenmenge folgt, kann man sich überlegen.
Eine klarere Antwort möchte ich hier nicht geben; langsam geht es um Fragestellungen, zu denen sich jede(r) selbst Gedanken machen sollte.
Felix Roth said:
Ich verstehe es so, wenn es mehrere Teilmengen von Knoten und Kanten gibt, an denen die PLG Eigenschaft scheitert, soll eine kleinste davon angegeben werden (was eine kleinste Teilmenge ist, muss man noch definieren).
Die Aufgabenstellung bezieht die Minimalität auf die Anzahl der Knoten.