1 svar
59 visningar
Tinelina 111
Postad: 6 nov 2019

Grafteori/ Kombinatorik

G=(V,E) is a bipartite graph with a perfect matching. Prove that for every v_1 in V there is a edge (v_1,v_2) such that there is a perfect matching containing (v_1,v_2).

Mitt försök:

Låt v_1 vara en vertex i V. Då G har en perfect matching, så gäller det att för varje v_1, är v_1 sammankopplad med endast en edge. Låt denna edge vara (v_1,v_2). Vi har därför att för alla v_1 så ingår (v_1,v_2) i en perfect matching.

 

Jag antar att detta är fel då det känns för trivitalt. Jag vet t.ex. att V=W union U, där W och U är disjunkta och då gäller att (då G har en perfect matching) |W|=|U|, och |V| är jämnt. Men vet inte hur jag kan använda det, om jag ska det.

 

Tacksam för hjälp

Smutsmunnen 110
Postad: 9 nov 2019

Denna uppgift var en del av en examinerande inlämning.

Svara Avbryt
Close