Knotenüberdeckung

10.12.2008, 13:12	Jane10	Auf diesen Beitrag antworten »
Knotenüberdeckung Hallo, ich muss in einer Ausarbeitung etwas zum Thema "Knotenüberdeckung" schreiben und vortragen. Leider habe ich bis jetzt nur wenig Literatur gefunden. Vielleicht kann mir jemand hier im Forum helfen!? Vielleicht habt ihr Ideen für interessante Links oder Bücher. Wäre echt super! Ach so, es soll ziemlich schulnahe Literatur sein. Danke!
11.12.2008, 00:14	Abakus	Auf diesen Beitrag antworten »
RE: Knotenüberdeckung In welchem Kontext steht das bzw. worum geht es insgesamt? Was ist eine Knotenüberdeckung (grob gesagt)? (Ich habe Schwierigkeiten das einzuordnen (Knotentheorie?).) Grüße Abakus
11.12.2008, 08:36	Jane10	Auf diesen Beitrag antworten »
Eine Knotenüberdeckung ist grob gesagt eine Menge von Knoten, so dass, jede Kante zu mindestens einem davon inzident ist. Knotenüberdeckungsprobleme treten häufig bei NP-Problemen auf. Mehr hab ich auch noch nicht. Meine Literaturquelle vom Prof ist leider nur Wikipedia und die restlichen Quellen, die ich finden kann, sind meis auf englisch. Knotenüberdeckung = Vertex Cover
11.12.2008, 19:21	Abakus	Auf diesen Beitrag antworten »
Ah... es geht also um Graphentheorie. Da gibt es eine ganze Reihe von ähnlichen Problemen, eine math. Modellierung geht oft mit Methoden der linearen Optimierung. Hier zB: sei $\begin{eqnarray} x_i = 1 \end{eqnarray}$ , wenn ein Knoten $\begin{eqnarray} i \end{eqnarray}$ für eine Überdeckung ausgewählt wird, und $\begin{eqnarray} 0 \end{eqnarray}$ sonst. Dann könnte man formulieren: $\begin{eqnarray} \min z := \sum_{i=i}^{n} x_i \end{eqnarray}$ udN.: $\begin{eqnarray} x_i + x_j \ge 1 \end{eqnarray}$ für alle $\begin{eqnarray} (i,j) \in E \end{eqnarray}$ $\begin{eqnarray} x_i \in \{0, 1\} \end{eqnarray}$ für alle $\begin{eqnarray} i \in V \end{eqnarray}$ Das lässt sich dann auch mit geeigneten Methoden lösen. Grüße Abakus

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »