Wiskundeforum

Hallo,

Ik heb een vraag over max cut en semidefiniete programmering. Het zijn twee opgaven:
Vraag 1:
Zij G een graaf:
a) bewijs dat mc(G) >= 2/3 |E(G)| als G 3-regulier is, waarbij mc(G) de maximale cardinaliteit van een snede in de (ongewogen) graaf G aangeeft.
b) bewijs dat mc(G) >= 2/3 |E(G)| als \chi(G) \in {3,4}

Hier had ik zelf een aantal ideeen bij: |E(G)| <=3 |V(G)|, en dit dan gebruiken, maar weet niet hoe? En voor het chromatisch getal, om de snede zo te maken dat de lijn tussen twee kleuren een lijn in de snede is.. maar weet ook hier niet hoe dit precies te bewijzen.

En dan vraag 2:
Wat is de maximale waarde van de som van de tien hoeken tussen 5 niet-nul vectoren in R^3? Hierbij dacht ik zelf dat je die hoek misschien kan berekenen door: de hoek tussen 2 vectoren is \pi maal de kans dat een random vlak door de oorsprong deze twee vectoren scheidt. Maar ook hier weet ik niet hoe ik precies moet bewijzen...

Hopelijk kan iemand snel helpen. Ik zou deze opdrachten graag voor woensdag af hebben..

Groetjes,

Stefanie