Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I'd like to use FindIndependentEdgeSet[g] repeatedly to get random maximal matchings of a fixed graph, but each time I call this function it gives me the same answer (i.e. the same list of edges).

How do I "randomise" it?

share|improve this question
1  
@Öskå Select[Subsets[EdgeList[g = CycleGraph[4]]], IndependentEdgeSetQ[g, #] && Length@# == 2 &] –  belisarius May 23 at 0:00
    
@belisarius R-r-r-ight :) Deleting comments so I don't look stupid :P –  Öskå May 23 at 9:08

1 Answer 1

Example graph:

g = PetersenGraph[5, 5];

Get independent edge sets:

indies = Select[Subsets[EdgeList[g]], IndependentEdgeSetQ[g, #] &];

Get some random set (repeat as needed):

RandomChoice[indies]

(* {1<->1, 2<->2, 3<->3, 4<->9, 6<->7} *)

Edit: Rahul notes I missed the "maximal" part.

(* pull out only longest sets *)
With[{ml = Max[Length /@ indies]}, indiesM = Select[indies, Length[#] == ml &]];

(* repeat as needed *)
RandomChoice[indiesM]
share|improve this answer
    
This does not always give maximal matchings. So it solves the problem in the title of the question but not the one in the body... –  Rahul Narain May 23 at 4:16
    
@RahulNarain: Thanks for catching, edited. –  rasher May 23 at 6:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.