[BuK] A11.1

[FoSAP] Formale Systeme, Automaten, Prozesse
[BuK] Berechenbarkeit und Komplexität
[MaLo] Mathematische Logik

A11.1

Beitragvon chrisblablub » 21.02.10 20:34

Hi,

kann mir vlt jmd seine lsg zur aufgabe 11.1 geben?
Wär super nett :)

Mfg
Chris
chrisblablub
 
Beiträge: 109
Registriert: 07.08.08 12:33

Re: A11.1

Beitragvon bt » 22.02.10 02:12

ich vermute die wenigsten haben verstanden wozu du gerne ne lösung hättest.
bt
 
Beiträge: 129
Registriert: 12.09.07 09:36
Studiengang: Informatik (M.Sc.)
Studiert seit: WS 08/09
Anwendungsfach: E-Technik

Re: A11.1

Beitragvon MartinL » 22.02.10 11:17

Ich kann in dem Zusammenhang darauf hinweisen, dass dieses Forum mehr bietet als eine Lösungstauschbörse - wenn konkrete Fragen gestellt werden fühlen sich vielleicht auch mehr Leute angesprochen darauf zu antworten.
MartinL
 
Beiträge: 531
Registriert: 23.01.07 20:48
Studiert seit: WS 06/07
Anwendungsfach: Mathe

Re: A11.1

Beitragvon chrisblablub » 22.02.10 12:33

naja es gibt doch nur eine aufgabe 11.1 oder nicht? aufgabe 1 von blatt 11 halt..aber ne idee wie z.b. die a geht wäre auch schon schön :)

mein plan bisher wäre VertexCover auf SetCover zu reduziern aber so ganz weiss ich nich wie
chrisblablub
 
Beiträge: 109
Registriert: 07.08.08 12:33

Re: A11.1

Beitragvon MartinL » 22.02.10 12:57

Bei VertexCover geht es darum eine Menge von Kanten abzudecken mit einer bestimmten Anzahl von Knoten.

Jeder Knoten deckt einen Teil der ganzen Kantenmenge ab und man darf nur eine gewisse Anzahl von Knoten nehmen. Es bietet sich also irgendwie an die Beschränkung in SetCover zu benutzen um die Knotenanzahlschranke von VertexCover zu benutzen.

Denk mal noch etwas darüber nach. Wenn du keine Idee hast kannst du dich noch mal melden. Es bringt dir für die Klausur aber mehr, wenn du selber drauf kommst als wenn ich einen ganzen Lösungsweg vorgebe. Das kann ich im Zweifelsfall später immer noch machen ...
MartinL
 
Beiträge: 531
Registriert: 23.01.07 20:48
Studiert seit: WS 06/07
Anwendungsfach: Mathe

Re: A11.1

Beitragvon chrisblablub » 23.02.10 00:11

ich habs immer noch nich, wie könnte man die teilmengen M1-Mk und U wählen?
chrisblablub
 
Beiträge: 109
Registriert: 07.08.08 12:33

Re: A11.1

Beitragvon MartinL » 23.02.10 16:33

die Gesamtmenge ist die Menge aller Vertexes. Man wählt nun für jeden Knoten k eine Menge M_k die alle zu k adjazenten Vertexes enthält und wählt nun die gewichte für alle Mengen auf 1 und die Gesamtschranke b setzt man auf das b von Vertex cover. Jedes SetCover führt nun zu einer Menge von Knoten, die alle Kanten abdecken (per Def des SetCover und Wahl der Mengen) außerdem hat man nicht mehr als b Sets, also mehr als b Knoten benutzt.
MartinL
 
Beiträge: 531
Registriert: 23.01.07 20:48
Studiert seit: WS 06/07
Anwendungsfach: Mathe

Re: A11.1

Beitragvon chrisblablub » 24.02.10 15:11

ahh danke :)

ich glaub die lsg is falsch..wenn man einen oder mehr isolierte vertices im Graph hat, sin die für das VertexCover underheblich, im SetCover würden diese aber bei der Vereinigung der TeilMengen evtl fehlen, d.h. die Vereinigung der genutzten b Teilmengen wäre != der menge aller vertices. Seh ich das richtig?
Es geht aber wenn man die menge aller zu Knoten i adjazenten kanten nimmt und U = E.
chrisblablub
 
Beiträge: 109
Registriert: 07.08.08 12:33

Re: A11.1

Beitragvon MartinL » 25.02.10 02:31

Ich hab irgendwie auch offenbar gepennt als ich das geschrieben hab. Denk dir da wo Vertexes steht ein Kanten. In der Erklärung unten ists auch richtig ...
MartinL
 
Beiträge: 531
Registriert: 23.01.07 20:48
Studiert seit: WS 06/07
Anwendungsfach: Mathe

Re: A11.1

Beitragvon chrisblablub » 25.02.10 11:58

Ok, dann is das ja geklärt. Danke!
chrisblablub
 
Beiträge: 109
Registriert: 07.08.08 12:33


Zurück zu Theoretische Informatik