Combinatorische Optimalisatie

Het forum voor overige vragen betreffende wiskunde uit het hoger onderwijs.

Combinatorische Optimalisatie

Berichtdoor 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
wiskundemeisjes
Nieuw lid
Nieuw lid
 
Berichten: 2
Geregistreerd: 12 Mrt 2013, 16:06

Terug naar Hoger onderwijs - overig

Wie is er online?

Gebruikers in dit forum: Geen geregistreerde gebruikers en 6 gasten

cron

Wie is er online?

Er zijn in totaal 6 gebruikers online :: 0 geregistreerd, 0 verborgen en 6 gasten (Gebaseerd op de gebruikers die actief waren gedurende 5 minuten)
De meeste gebruikers ooit tegelijkertijd online was 649 op 31 Okt 2014, 18:45

Gebruikers in dit forum: Geen geregistreerde gebruikers en 6 gasten
Copyright © 2009 Afterburner - Free GPL Template. All Rights Reserved.