1 svar
59 visningar
Penna12 2
Postad: 5 jul 2018 12:49 Redigerad: 5 jul 2018 12:52

Kombinatorik

Hej, jag behöver hjälp med en lite del av en uppgift. Frågan lyder:

Låt för varje n2 grafen Gn=(Vn,En), där 

Vn=partitioner av 1,...,n i två parter= A,B:A,B1,..,n=ABAB=, och två partitioner bildar en kant om någon av parterna i den ena partitionen är en äkta delmängd av någon av parterna i den andra. 

a) Rita upp G2,G3 och G4.

 Det jag har svårt med är att förstå det sistnämnda, dvs. "två partitioner bildar en kant om någon av parterna i den ena partitionen är en äkta delmängd av någon av parterna i den andra". Om vi försöker rita upp grafen för G4. Partitionerna av {1,2,3,4} är:

{1,234}, {2,134}, {3,124}, {4,123}, {12,34}, {13,24}, {14,23}. Men nu har jag svårt, hur vet jag vilka som bildar en kant, dvs. hur avgör jag om någon av parterna i den ena partitionen är en äkta delmängd av någon av parterna i den andra. Jag har facit, och då vet jag att t.ex. {1,234} bildar kanter med {2,134}, {3,124}, och {4,123} mm. men t.ex. kopplas inte {13,24} och {14,23} till en kant varför? Hur ser man det? 

Tack på förhand.

haraldfreij 1322
Postad: 5 jul 2018 13:05

{1,234} har parterna {1} och {234}. {3,124} har på motsvarande sätt parterna {3} och {124}. Du ser att {1} (som är en part i första paritionen) är en delmängd av {124} (som är part i andra partitionen), och därför ska de två noderna ha en kant mellan sig.

Ingen av parterna {13} och {24} är ju däremot delmängd av {14} eller {23}, eller vice versa, så där får du ingen kant.

Svara
Close