Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Knotenabdeckung ohne adjazente Knoten mit maximaler Summe der Knotengewichte
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Knotenabdeckung ohne adjazente Knoten mit maximaler Summe der Knotengewichte
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 181
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-05-27


Hallo,

Gegeben ist ein gerichteter Graph \(G = (V,E)\) wobei jedes \(v \in V\) ein Knotengewicht \(f_{v} \in \mathbb{N}\) hat. \(G\) ist ein Baum, also zusammenhängend und kreisfrei. Nun soll für diesen Graphen eine Knotenabdeckung \(S\) gefunden werden, sodass es keine Kante \(e \in E\) gibt, bei der beide Knoten in \(S\) liegen. Anders formuliert dürfen also keine adjazenten Knoten beide in \(S\) liegen. Die Summe der Knotengewichte soll dabei maximal sein.

Mein naiver Ansatz ist generate-and-test, also alle möglichen Abdeckungen generieren und das Maximum dabei ermitteln. Das ist allerdings etwas langsam. Hat jemand eine Idee, wie es effizienter gestaltet werden kann?

Danke!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6872
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-05-27


Als erstes fallen einige naheliegende Reduktionsschritte auf:

Ich gehe davon aus, dass alle Knotengewichte positiv sind. Knoten ohne positive Gewichte kommen nie in S.

1) Knoten ohne Nachbarn gehören zu S.
2) Knoten, die leichter sind als alle benachbarten Blätter(*) zusammen, gehören nicht zu S. In dem Fall gehören alle benachbarten Blätter zu S.
3) Knoten, die schwerer sind als alle Nachbarn zusammen gehören zu S. Alle Nachbarn gehören dann nicht zu S.
(*) Blätter sind Knoten mit genau einem Nachbarn.

Ist für einen Knoten entschieden, dass er zu S gehört, so kann man ihn, alle inzidenten Kanten und alle Nachbarknoten entfernen und im weiteren nur noch den reduzierten Graphen betrachten.
Ähnliches gilt, wenn entschieden ist, dass ein Knoten nicht zu S gehört. Dann kann man ihn und alle inzidenten Kanten entfernen.
Durch diese Reduktion können weitere isolierte Knoten und Blätter entstehen, so dass die Regeln 1 und 2 eventuell für weitere Knoten gelten. Es könnte auch neue Knoten geben, für die 3 gilt, weil ein Knoten Nachbarn verloren hat.

Diese Reduktion kann man so lange vornehmen, bis sich im Restgraph keine Knoten mehr finden lassen, die eines der drei Kriterien erfüllen.

Darüber hinaus kann man bei nicht-zusammenhängenden Graphen alle Zusammenhangskomponenten separat betrachten.


Ein zweiter naheliegender Schritt wäre die Modellierung als 0-1-lineares Optimierungsproblem. Für jeden Knoten $i$ führen wir eine Variable $x_i$ ein, die 1 ist, wen $x_i$ zu S gehört und 0, wenn nicht.
Für jede Kante $(i,j)$ gibt es eine Nebenbedingung, nämlich $x_i+x_j\leq 1$.
Wenn vorhanden kann man also einen fertigen Algorithmus zur Lösung von 0-1-LPs benutzen.
Wenn nicht, ergibt sich aus der Beobachtung zumindest ein naheliegender Ansatz für ein Branch-and-Bound-Verfahren.
Die Lösung des relaxierten linearen Problems (d.h., es wird zwar $0\leq x_i\leq 1$ gefordert, aber die $x_i$ müssen nicht ganzzahlig sein) liefert eine obere Schranke für den Zielfunktionswert.
Eine Verzweigung im Suchbaum entsteht, in dem man entscheidet, ob man einen bestimmten Knoten zu S dazu nimmt, oder nicht. Je nach Entscheidung reduziert sich der Graph so oder so. In beiden Nachfolge-Graphen berechnet man die obere Schranke für die optimale Lösung. Den "schlechteren" Teilbaum legt man zunächst zur Seite und arbeitet im "besseren" weiter. Dort wählt man wieder einen Knoten aus, verzweigt usw.
Irgendwann stößt man auf eine zulässige Lösung. Dies ist bereits dann der Fall, wenn alle $x_i$ des relaxierten Problems ganzzahlig sind.
Damit hat man eine untere Schranke für den optimalen Zielfunktionswert.
Jetzt kann man Teilbäume mit zu schlechter oberer Schranke wegwerfen.
Im folgenden werden Teilbäume weiter verzweigt, in der Hoffnung, dass entweder ihre obere Schranke dadurch sinkt (am besten unter die globale untere Schranke, dann kann man sie ganz verwerfen), oder dass man eine bessere Lösung findet, wodurch die untere Schranke steigt.

Vorteile gegenüber "Erzeuge und Teste":
a) Ganze Teilbäume müssen nicht untersucht werden, wenn die obere Schranke des relaxierten Problems zu schlecht ist.
b) Erhält man in der Lösung des relaxierten Problems eines Teilbaumes eine ganzzahlige Lösung, so muss dieser Teilbaum auch nicht weiter untersucht werden, weil das gleichzeitig die beste Lösung des unrelaxierten Problems ist.

Nachteile:
Wenn man nicht gerade eine Tiefensuche implementiert, muss man u.U. viele Teilbäume im Speicher halten.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 181
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-05-28


Tut mir Leid ich habe vergessen zu erwähnen, dass Knotengewichte \(\geq 0\) sind.
Vielen Dank für deine Mühe!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 181
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2021-05-28


Angenommen man hat einen Graphen \(G = (V,E)\) mit \(V = \{1,2,3\}\), \(E=\{(1,2),(2,3)\}\) und \(f(1)=1\), \(f(2)=2\), \(f(3) = 3\), wobei \(f\) die Gewichtsfunktion ist. Dann würde der Algorithmus doch (wenn man bei der Wurzel \(1\) startet) Knoten \(2\) auswählen. Dann könnte man Knoten \(3\) nicht mehr auswählen und die Lösung wäre nicht optimal, sehe ich das richtig?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6872
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-05-28


Knoten 2 ist doch leichter als die beiden Nachbarknoten (die Blätter sind) zusammen.Von daher würde Knoten 2 ausdrücklich nicht gewählt, wodurch 1 und 3 isoliert sind und gewählt werden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 181
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2021-05-29


Ja stimmt, tut mir Leid - ich hab deinen Algorithmus nicht richtig durchdacht.
Ein Problem bei deinem Vorschlag ist die Implementierung - das herauslöschen von Knoten und Kanten braucht recht lange und wird unübersichtlich. Hast du eine Idee wie man das Problem lösen kann, so dass es in eine leichte Implementierung mündet? Zum Beispiel mit dynamischer Programmierung?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 181
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-05-29


Und was passiert, wenn es in dem Graphen keinen Knoten gibt, auf den eine der Regeln angewendet werden kann? Man müsste die Existenz von so einem Knoten in jedem Schritt beweisen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Fabi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.03.2002
Mitteilungen: 4574
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2021-05-29


Hi,

Ein naiver Algorithmus, der zumindest das richtige Ergebnis liefert (wenn auch viel zu langsam), ist der folgende: Für einen gewichteten Baum G bezeichne w(G) das optimale Gewicht einer Knotenabdeckung, die keine adjazenten Knoten enthält. G kann auch genausogut ein Wald sein; dann ist offensichtlich w(G) die Summe der optimalen Knotengewichte der einzelnen Komponenten.

Wähle eine beliebige Ecke v von G. Sei F der Wald, der durch Entfernen von v entsteht, und F' der Wald, der durch Entfernen von v und aller Nachbarknoten von v entsteht.

Nun gilt $w(G) = max(w(F), f_v+w(F'))$: w(F) ist das optimale Gewicht einr Knotenabdeckung, die v nicht enthält; und $f_v+w(F')$ ist das optimale Gewicht einer Knotenabdeckung, die v enthält.

Naiv handelt man sich hier an jeder Ecke etwa einen Faktor 2 ein, was den Algorithmus unbrauchbar macht. Die entscheidende Beobachtung ist jetzt aber, dass es garnicht soviele Bäume gibt, die rekursiv auftauchen: Jeder Baum, der rekursiv aufscheint, hat eine Ecke u, deren Abstand von v minimal ist, und besteht genau aus allen Ecken, die von v aus gesehen auf der anderen Seite von u liegen (und u selber), da wir ja rekursiv von v aus ausgehend Knoten herausnehmen!

Es gibt also für jede Ecke u von G genau einen Baum $G_u$, für den wir eine optimale Knotenabdeckung finden müssen: $G_u$ besteht aus den Ecken, von denen aus man auf dem kürzesten Weg nach v bei u vorbeikommt. Mit diesen Beobachtungen ist das Problem jetzt leicht mit einem DP-Ansatz lösbar:

- Wähle eine Wurzel v von G
- Für jede Ecke w von G initialisiere $w(G_u)$ als 'unknown'

- Solange es Knoten mit $w(G_u)$ 'unknown' gibt:
  - Wähle im Unterbaum der Knoten, in denen noch 'unknown' steht, ein Blatt u
  - Sei U die Menge der Nachbarn von u, die weiter weg von v sind als u; sei U' die Menge der Knoten     mit Abstand 2 von u, die weiter weg sind von v als u.
  - Setze $w(G_u) = max(\sum_{x \in U} w(G_x), f_u+\sum_{x \in U'} w(G_x)$

$\sum_{x \in U} w(G_x)$ ist das Gewicht einer optimalen Knotenabdeckung von $G_u$, die u nicht enthält; $f_u+\sum_{x \in U'} w(G_x)$ das Gewicht einer optimalen Knotenabdeckung, die u enthält.

vG,
Fabi

[Die Antwort wurde nach Beitrag No.5 begonnen.]


-----------------
"There would be the mathematical equivalent of worldwide rioting." (P.C.)

Willst du Hamburg oben sehen, musst du die Tabelle drehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 181
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2021-05-29


Danke für deine Mühe!
Ich verstehe diesen Abschnitt deiner Begründung nicht so ganz
"Jeder Baum, der rekursiv aufscheint, hat eine Ecke u, deren Abstand von v minimal ist, und besteht genau aus allen Ecken, die von v aus gesehen auf der anderen Seite von u liegen (und w selber), da wir ja rekursiv von v aus ausgehend Knoten herausnehmen!"

Mit "...deren Abstand von v minimal ist..." meinst du den Abstand verglichen mit allen anderen Knoten in dem Unterbaum? Also "die näheste" Kante zu \(v\)?
Und mit "... die von v aus gesehen auf der anderen Seite von u liegen..." meinst du damit alle Knoten, die über einen Weg zu \(v\) über \(u\) läuft? Wenn man also zwei näheste Kanten \(u_1\), \(u_2\) in einem Schritt des Algorithmus hat, sind dann alle Knoten gemeint, die über einen Weg der \(u_1\) oder \(u_2\) zu \(v\) verlaufen?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Fabi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.03.2002
Mitteilungen: 4574
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2021-05-29


Hi,

Wenn man u entfernt, zerlegt man den ursprünglichen Baum in zwei Bäume. $G_u$ ist der Baum, der nicht die Wurzel v enthält, zusammen mit u selber. Dann ist u derjenige Knoten in $G_u$, der am nächsten an v liegt.

Das w in dem von dir zitierten Teil hätte natürlich auch ein u sein müssen.

Die Frage mit den zwei nähesten Kanten verstehe ich nicht; der Algorithmus arbeitet Knoten für Knoten ab; man arbeitet niemals an mehreren Knoten, sondern verwendet bereits bekannte Knoten, um einen noch unbekannten Knoten auszurechnen.

vG,
Fabi


-----------------
"There would be the mathematical equivalent of worldwide rioting." (P.C.)

Willst du Hamburg oben sehen, musst du die Tabelle drehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6872
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2021-05-29


@Fabi: Schöner Algorithmus! Schade, dass mir das nicht eingefallen ist. Die Beschreibung Deines Algorithmus ist ja fast einfacher als der generische Branch&Bound-Ansatz mit Lösung des relaxierten Problems und liefert in Polynomialzeit (Vielleicht geht es sogar in Linearzeit) die Optimale Lösung.

Hier mal die Beschreibung von dem, was ich mir ausgedacht habe in der Hoffnung auf Linearzeit zu kommen.

1) Wir wandeln den Baum in einen Wurzelbaum W mit Wurzel w um (welcher Knoten die Wurzel ist, ist egal). Ist der Graph nicht zusammenhängend, bilden wir einen Wald aus Wurzelbäumen.
2) Jeder Knoten v definiert einen Teilbaum T(v), der aus ihm selbst und seinen (direkten und indirekten) Nachfolgern innerhalb von W besteht.
3) Wir ermitteln für jedes v den Abstand zu w. Das geht in Linearzeit, wenn man W einmal von w aus systematisch durchläuft und Buch darüber führt, welche Kanten von w wegführen, den Abstand zu w also vergrößern und beim umgedrehten Durchlaufen den Abstand zu w daher verringern.
4) Wir sortieren alle v absteigend nach dem Abstand zu w. Mit Bucket-Sort geht das in Linearzeit, da die Abstände ganze Zahlen von 0 bis n-1 sind.
5) Iterativ berechnen wir nun für jeden Knoten v die optimale Lösung wie folgt:
a) wir ermitteln die Kinder v1, v2, ... von v sowie die Enkel u1, u2, ... von v
b) jetzt gibt es zwei Möglichkeiten: die optimale Lösung für T(v) enthält v, dann besteht sie gerade aus v und den optimalen Lösungen für T(w1), T(w2), ...
oder sie enthält v nicht und besteht aus den optimalen Lösungen füt T(v1), T(v2), ...
Da alle Werte T(vi) und T(wj) bereits bekannt sind (weil sie von w weiter entfernt sind), lassen sich Gewichte dieser beiden Lösungskandidaten leicht berechnen und vergleichen.
6) T(w) ist schließlich die gesuchte Lösung.

In Schritt 5) kann ein Knoten zwar viele Kinder und Enkel haben (O(n) sind möglich), aber jeder Knoten ist nur Kind bzw. Enkel von (maximal) einem Knoten. Daher bleibt die Anzahl der in Schritt 5 zu betrachtenden Summanden für alle Knoten v zusammen bei O(n).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Fabi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.03.2002
Mitteilungen: 4574
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2021-05-31


Hi,

Wenn die Datenstruktur des Baums an sich nicht gerade sehr ungeschickt gewählt ist, sollte man meinen Algorithmus in linearer Zeit implementieren können:

- Wähle einen Wurzelknoten v
- Mithilfe einer Breitensuche erstelle eine Liste der Knoten von G in aufsteigendem Abstand von v. Zusätzlich merke dir für jeden Knoten u dessen Elternknoten.
- Initialisiere für jeden Knoten u einen Childweightcounter als 0 und einen Grandchildweightcounter als $f_u$. Ersterer soll $\sum_{x \in U} w(G_x)$ tracken, letzterer $f_u+\sum_{x \in U'} w(G_x)$
- Jetzt iteriere in umgekehrter Reihenfolge über die erstellt Liste der Knoten, d.h. beginnend bei dem Knoten mit größter Entfernung zur Wurzel.

Für jeden Knoten u setze

$w(G_u) = max(Childweightcounter, Grandchildweightcounter)$

Dann setze

$Childweightcounter(Grandparent(u)) = Childweightcounter(Grandparent(u))+w(G_u)$

und

$Grandchildweightcounter(Grandparent(u)) = Grandchildweightcounter(Grandparent(u))+w(G_u)$

Da wir uns den Elternknoten jedes Knotens bei der Breitensuche ohnehin gemerkt haben, ist der Zugriff auf den Elternknoten in konstanter Zeit möglich. Damit läuft dieser Algorithmus in linearer Zeit.

vG,
Fabi



-----------------
"There would be the mathematical equivalent of worldwide rioting." (P.C.)

Willst du Hamburg oben sehen, musst du die Tabelle drehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 181
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2021-05-31


Hey,

Vielen Dank für eure Mühe. Ist \(U\) die Menge aller Nachbarn von dem Knoten \(x\) der in jedem Schritt betrachtet wird und \(U'\) die Menge aller Nachbarn von Nachbarknoten von \(x\)?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Fabi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.03.2002
Mitteilungen: 4574
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2021-05-31


Hi,

Wie in meinem ersten Post:

2021-05-29 13:52 - Fabi in Beitrag No. 7 schreibt:
 - Sei U die Menge der Nachbarn von u, die weiter weg von v sind als u; sei U' die Menge der Knoten mit Abstand 2 von u, die weiter weg sind von v als u.


Explizit braucht man diese Mengen aber nicht, wenn man von u aus direkt Parent und Grandparent updatet.

vG,
Fabi




-----------------
"There would be the mathematical equivalent of worldwide rioting." (P.C.)

Willst du Hamburg oben sehen, musst du die Tabelle drehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 181
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2021-06-02


Okay, vielen Dank noch mal.
Aber was mache ich bei
\(Childweightcounter(Grandparent(u))=Childweightcounter(Grandparent(u))+
w(G_u)\) wenn \(Grandparent(u)\) nicht existiert? Irgendwie kriege ich den Zeilenumbruch nicht richtig hin, sorry



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Fabi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.03.2002
Mitteilungen: 4574
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2021-06-02


2021-06-02 10:38 - dvdlly in Beitrag No. 14 schreibt:
Okay, vielen Dank noch mal.
Aber was mache ich bei
\(Childweightcounter(Grandparent(u))=Childweightcounter(Grandparent(u))+
w(G_u)\) wenn \(Grandparent(u)\) nicht existiert? Irgendwie kriege ich den Zeilenumbruch nicht richtig hin, sorry

Nichts. Ebenso wenn Parent(u) nicht existiert (dh wir stehen gerade an der Wurzel) - es gibt halt keine Knoten mehr, die wir noch updaten müssen.

vG,
Fabi



-----------------
"There would be the mathematical equivalent of worldwide rioting." (P.C.)

Willst du Hamburg oben sehen, musst du die Tabelle drehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly hat die Antworten auf ihre/seine Frage gesehen.
dvdlly hatte hier bereits selbst das Ok-Häkchen gesetzt.
dvdlly wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]