matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieCliquenüberdeckung
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Graphentheorie" - Cliquenüberdeckung
Cliquenüberdeckung < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Cliquenüberdeckung: Tipp
Status: (Frage) beantwortet Status 
Datum: 15:27 Fr 09.06.2006
Autor: Puma1981

Ich habe folgendes Problem:
Ich versuche zu zeigen, dass ein Algorithmus eine minimale (Kanten-)Cliquenüberdeckung liefert für einen chordalen Graphen.
Ich finde mit dem Algorithmus eine Cliquenüberdeckung, jedoch weiß ich nicht, wie ich beweisen soll, dass diese die minimale Anzahl an Cliquen benötigt. Kennt jemand Beweise für Cliquenüberdeckungen die ich dazu vergleichen kann oder hat jemand einen Hinweis für mich?

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.


        
Bezug
Cliquenüberdeckung: Antwort
Status: (Antwort) fertig Status 
Datum: 07:13 Mo 12.06.2006
Autor: mathiash

Hallo und guten Morgen,

Literatur solltest Du per google finden, ueber chordale Graphen - aber meines Wissens nicht ueber Cliquen-Ueberdeckungen - findest Du auch in
den lehrbuechern etwas, zB dem von Brandstädt.

Da Du nicht mehr ueber den Algorithmus verraten hast, auch nur ein sehr generischer Ansatz: Probier doch einfach
zum Beweis anzunehmen, es gäbe noch eine kleinere
Cliquenueberdeckung als die vom Algorithmus konstruierte, und diese Annahme dann zum Widerspruch mit der Spezifikation des Algorithmus
zu fuehren.

Viele Gruesse,

Mathias

Bezug
                
Bezug
Cliquenüberdeckung: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 11:03 So 18.06.2006
Autor: Puma1981

Aufgabe
Hallo,
vielen Dank für die schnelle Antwort. Bin aber leider bei meinem Problem immer noch nicht weiter gekommen.
Ich habe einen Algo, der mir eine Überdeckung liefert, aber mir fehlt eine passende untere Schranke, die mir die optimalität zeigt.
Hier der Algo:
(1) [mm] A=\emptyset; Q=\emptyset; [/mm]
(2) Finde PES (perfektes Eliminationsschema) von G=(V,E) (Da G ein chordaler Graph, muss dieses existieren. => {x1, x2, ..., xn}=V mit Nachbarschaft von xi [mm] \cap [/mm] {x(i-1), ..., x1} bildet eine Clique)
(3) for i=1 to n do
(4)     A=(Nachbarschaft von xi [mm] \cup [/mm] xi) [mm] \cap [/mm] {xi,...,x1} (=Clique nach Konstruktion)
(5)     if ein B Element Q existiert, so dass B Teilmenge von A dann
(6)            Q = ( Q \ B ) [mm] \cup [/mm] A;
(7)     else Q = Q [mm] \cup [/mm] A;
(8)     A = [mm] \emptyset [/mm] ;
(9)     Für alle B Element Q mit Kardinalität von B gleich 1 führe aus: Q = Q \ B

=> Kardinalität von Q ist die minimale Anzahl der benötigten Cliquen für eine Kanten-Cliquenüberdeckung.

Kann mir einer einen Tipp geben, wie ich die Optimalität zeigen kann? Oder ist der Algo falsch und es existiert ein Gegenbeispiel?
Bin für jeden Hinweis dankbar!



Bezug
                        
Bezug
Cliquenüberdeckung: Antwort
Status: (Antwort) fertig Status 
Datum: 08:40 Mo 19.06.2006
Autor: mathiash

Hallo und guten Morgen,

als erstes würd ich immer klären, ob das Problem nicht sogar NP-hart sein könnte oder so.
Mal angenommen nicht, so
könnte man zB versuchen zu zeigen, dass nach Behandlung des Knoten [mm] x_i [/mm]  Q eine optimale
Cliquenüberdeckung des von [mm] x_1,\ldots x_i [/mm] induzierten Teilgraphen ist.

Man könnte auch versuchen zu zeigen:

(a) Sei [mm] Q^{\star} =\{C_1,\ldots , C_l\} [/mm] eine optimale Cliquenüberdeckung, dann enthält die vom Algorithmus
konstruierte Cliquenüberdeckung zu jedem [mm] C_j [/mm] eine ''Ober-''Clique  [mm] A_i\supseteq C_j. [/mm]

(b) Die vom Algorithmus konstruierte Cliquenüberdeckung Q ist inklusionsminimal, d.h. für jedes [mm] A\in [/mm] Q ist
[mm] Q\setminus \{A\} [/mm]  keine Cliquenüberdeckung mehr.

(a) sollte man leicht ueber die PES-Eigenschaft zeigen können, (b) sollte aus der Konstruktion des Algorithmus
einsichtig sein.

Frohes Schaffen !

Mathias

Bezug
                                
Bezug
Cliquenüberdeckung: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 15:18 Di 04.07.2006
Autor: Puma1981

Hallo Mathias,

vielen Dank für deine schnelle Hilfe. Du hast mich da schon ein gutes Stück weiter gebracht. Leider konnte ich noch immer nicht zeigen, dass der Algorythmus eine minimale (Kanten-)Cliquenüberdeckung liefert.
Auch kein Wunder, so wie oben definiert liefert er auch keine. :o( Also ein neuer Versuch:

Das hat sich Dank deiner Beweisskizze herausgestellt:

(a) Sei [mm] Q^{\star} [/mm] = { [mm] C_{1}, C_{2},...,C_{l} [/mm] } eine optimale Cliquenüberdeckung, dann enthält die vom Algorithmus
konstruierte Cliquenüberdeckung Q zu jedem [mm] C_{j} [/mm] eine ''Ober-''Clique [mm] C_{i} \subseteq A_{j} [/mm] mit [mm] A_{j} \in [/mm] Q.

=> Dies kann man leicht zeigen. Da G=(V,E) ein chordaler Graph existiert ein PES (perfektes elimination schema) [mm] x_{1}, x_{2}, [/mm] ...., [mm] x_{n} [/mm] (=V) mit [mm] \forall [/mm] i [mm] \in [/mm] {1,....,n}: { [mm] N(x_{i}) \cap [/mm] { [mm] x_{i},....,x_{1} [/mm] } } bildet eine Clique in G. [mm] (N(x_{i}) [/mm] bezeichnet die Nachbarschaft von [mm] x_{i} [/mm] inklusive [mm] x_{i}) [/mm]
Wähle beliebiges [mm] C_{j} \in Q^{\star}. [/mm] Es gilt [mm] C_{j} \subseteq [/mm] { [mm] x_{1},...., x_{n} [/mm] }. Wähle dann [mm] x_{s} \in C_{j} [/mm] mit s größter Index in [mm] C_{j}. [/mm] Wenn [mm] x_{s} [/mm] beim Algorythmus an der Reihe ist, dann ist [mm] C_{j} \subseteq [/mm] { [mm] N(x_{s}) \cap [/mm] { [mm] x_{s},....,x_{1} [/mm] } }  =: A [mm] \in [/mm] Q (gilt weil [mm] C_{j} [/mm] Clique und somit in der Nachbarschaft enthalten). A kann später zwar aus der Menge gelöscht werden, aber nur, wenn A durch eine Clique ersetzt wird, die A enthält und somit auch [mm] C_{j} [/mm] enthält. Damit ist a) gezeigt.

(b) Die vom Algorithmus konstruierte Cliquenüberdeckung Q ist inklusionsminimal, d.h. für jedes  
A [mm] \in [/mm] Q ist Q \ {A} keine Cliquenüberdeckung mehr.

=> Dies stimmt bei der Arbeitsweise des Algorythmuses leider nicht.
Daher muss man nun die Menge der Cliquen von Q "bereinigen". Wenn eine Clique [mm] A^{\star} [/mm] von Q überdeckt werden kann durch Cliquen [mm] A_{1}, A_{2},...., A_{k} \in [/mm] Q \ [mm] {A^{\star}} [/mm]  ( [mm] A^{\star} \subseteq [/mm] A{1} [mm] \cup [/mm] .... [mm] \cup A_{k} [/mm] ) dann lösche [mm] A^{\star}. [/mm] Wiederhole dies, bis kein Element von Q mehr von anderen Elementen von Q überdeckt werden kann.
Sei S das bereinigte Q. (Also Q ohne die Cliquen die überdeckt werden können.)

Nun muss noch gezeigt werden, dass |S| = [mm] |Q^{\star}| [/mm] gilt. (Also unsere gefundene Cliquenüberdeckung S genau so viele Cliquen benötigt, wie die "perfekte" Cliquenüberdeckung [mm] Q^{\star}.) [/mm]
Dazu erstelle ein Matching zwischen [mm] Q^{\star} [/mm] und S:
Dabei gilt: Es soll eine Kante zwischen [mm] A_{j} \in [/mm]  S und [mm] C_{i} \in Q^{\star} [/mm] existieren, wenn [mm] C_{i} \subseteq A_{j}. [/mm]
(Matching => Wenn mehrere Elemente von S ein Element von [mm] Q^{\star} [/mm] enthalten, dann zeichne nur eine Kante.)
(Mehrere Elemente von [mm] Q^{\star} [/mm] können nicht in einem Element von S enthalten sein, da sonst die "perfekte" Cliquenüberdeckung verbessert werden könnte. Zwei Cliquen aus [mm] Q^{\star} [/mm] können durch eine Clique von S überdeckt werden. Wiederspruch zur Minimalität.)

Nun möchte man nur noch zeigen, dass jedes Element von S einen Matchingpartner in [mm] Q^{\star} [/mm] enthält, dann wäre man fertig.

Dies ist ein Versuch, dies mittels eines Widerspruches zu beweisen:
Angenommen [mm] A_{0} \in [/mm] S hat keinen Matchingpartner. (Kein C [mm] \in Q^{\star} [/mm] ist in [mm] A_{0} [/mm] enthalten.)
Da [mm] Q^{\star} [/mm] Cliquenüberdeckung [mm] \exists C_{1}, C_{2},...., C_{k} \in Q^{\star} [/mm] so dass gilt [mm] A_{0} \subseteq C_{1} \cup [/mm] .... [mm] \cup C_{k}. [/mm]
Für alle [mm] C_{i} [/mm] (i [mm] \in [/mm] {1,....,k}) existiert nach (a) ein [mm] A_{i} \in [/mm] Q (=unbereinigte Cliquenüberdeckung).
Nach der "Bereinigung" sind eventuel einige dieser [mm] A_{i} [/mm] nicht mehr in S (=bereinigte Cliquenüberdeckung).
Wenn [mm] A_{i} [/mm] nach der "Bereinigung" nicht, mehr in S, muss gelten:
[mm] \exists A_{1'}, [/mm] .... , [mm] A_{l'} \in [/mm] S mit [mm] A_{i} \subset A_{1'} \cup [/mm] .... [mm] \cup A_{l'}. [/mm]
Wenn [mm] A_{0} \not\in [/mm] { [mm] A_{1'},...., A_{l'} [/mm] }, dann läßt sich [mm] A_{0} \in [/mm] S überdecken mit Elementen von S. Widerspruch.

Es fehlt also nur noch zu zeigen, dass [mm] A_{0} \not\in [/mm] { [mm] A_{1'},...., A_{l'} [/mm] } gilt. Wie gehe ich da am besten vor? Oder habe ich da einen Fehler in der Argumentation?
Wäre sehr froh, wenn du mir wieder schnell einen Tipp geben könntest!
Vielen Dank!

Bezug
                                        
Bezug
Cliquenüberdeckung: Antwort
Status: (Antwort) fertig Status 
Datum: 05:33 Fr 07.07.2006
Autor: mathiash

Hallo und guten Morgen,

sorry, dass sich das mit meiner Antwort so verzögert, aber die Woche war hier einigermassen voll, so dass ich erst jetzt dazu komme.

Nun, eine Cliquenüberdeckung ist doch eine Menge von Cliquen, so dass jede Kante des Graphen in mindestens einer Clique der Überdeckung
vorkommt.

Wenn nun eine Clique [mm] A_0 [/mm] aus der vom Algorithmus konstruierten Überdeckung [mm] {\mathcal S} [/mm] keinen Partner in der optimalen Überdeckung [mm] {\mathcal O}^{\star}[/mm] findet, so
kann man sie einfach streichen, und die verbleibende Menge von Cliquen [mm] {\mathcal S}\setminus\{A_0\}[/mm] ist dann immer noch Cliquenüberdeckung (da nämlich [mm] {\mathcal O}^{\star}[/mm]  eine ist und weil jedes Element aus [mm] {\mathcal O}^{\star}[/mm]
einen Matchingpartner hat), also wäre [mm] A_0 [/mm] schon bei der Bereinigung entfernt worden.

Das sollte es dann aber auch gewesen sein.

Frage: War das eine Übungsaufgabe, oder schreibst Du ne Arbeit darüber oder wozu brauchst Du das ?

Viele Grüße,

Mathias

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]