Combinatorische Optimalisatie

Het forum voor overige vragen betreffende wiskunde uit het hoger onderwijs.
wiskundemeisjes
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 12 mar 2013, 16:06

Combinatorische Optimalisatie

Bericht door wiskundemeisjes » 07 jun 2013, 10:33

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

Plaats reactie