Graphentheorie < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 09:30 So 28.10.2007 | | Autor: | wursthans |
| Aufgabe | Aufgabe1:
Formuliere einen Algorithmus, der mit Laufzeit O(|V | + |E|) entscheidet, ob ein gegebe-
ner Graph bipartit ist und gegebenenfalls eine Bipartition V = V1 ∪ V2 ausgibt. Es wird
nicht vorausgesetzt, daß der Graph zusammenh¨angend ist. Begr¨unde die Korrektheit des
Verfahrens.
Aufgabe 2:
Sei eine Gradfolge d = (d1 ≥ . . . ≥ dn), di ∈ ZZ, n ≥ 2 gegeben. Dann existiert genau dann
ein Baum G mit Gradsequenz d, wenn Pn
i=1 di = 2n − 2 gilt.
Aufgabe 3:
Sei G = (V,E) ein Graph. Man bezeichnet einen Schnitt als inklusionsminimalen Schnitt,
wenn er nichtleer ist und per Inklusion minimal ist. Genauer, ein Schnitt E(W, V [mm] \W) [/mm] ist
inklusionsminimal, falls es kein W′ ⊂ V (G) gibt mit ∅ 6= E(W′, V [mm] \W′) [/mm] ( E(W, V [mm] \W).
[/mm]
Sei nun G zusammenh¨angend. Zeigen sie, daß ein Schnitt E(W, V \ W) genau dann in-
klusionsminimal ist, wenn die induzierten Graphen G(W) und G(V \ W) jeweils zusam-
menh¨angend sind.
Aufgabe 4:
Sei G = (V,E) ein Graph. Eine Clique in G ist eine Teilmenge der Knotenmenge, die einen
vollst¨andigen Graphen induziert. Bezeichne mit CLIQUE das Problem zu entscheiden, ob
G eine Clique der Gr¨oße k besitzt. Zeigen Sie komplexit¨atstheoretisch, dass CLIQUE NP-
vollst¨andig ist. Kann man CLIQUE graphentheoretisch in STABILE MENGE ¨ubersetzen? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Kennt jemand die Lösungen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:42 Mo 29.10.2007 | | Autor: | Bastiane |
Hallo wursthans!
Wo sind denn deine eigenen Ansätze? Wir sind hier doch kein Übungsaufgaben-Löse-Forum!
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
|
