Sistemi različnih predstavnikov

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

Splošni opis

Imamo n množic: A_1 , A_2 , \ldots A_n

Elementi a_1 , a_2 \ldots a_n so sistem različnih predstavnikov za družino \{ A_1 , A_2 , \ldots A_n \}, če velja:

  • a_i \in A_i , i = 1, 2, \ldots n
  • a_i \neq a_j \ \mbox{za} \ i \neq j

Prirejanje: M \subseteq E(G) je prirejanje, če noben par povezav iz M nima skupnega krajišča.

"Reševanje": Problem predstavimo z dvodelnim grafom (glej primer), kjer iščemo prirejanje, ki pokrije levo stran.

Potreben in hkrati zadosten pogoj sledi iz Hallowega izreka


Zgled

Osebe A, B, C, D, E, F so člani petih odborov:

O_1 = \{ A, B ,C \} ; \ O_2 = \{ A, B \} ; \ O_3 = \{ A, C, D, E ,F \} ; \ O_4 = \{ C, D, E \} ; \ O_5 = \{ C, D, E, F \}

Predstavitev z dvodelnim grafom:

Fri-uni-komb-srp1.png

Hallov izrek

Družina množic \{ A_1 , A_2 , \ldots A_n \} ima sistem različnih predstavnikov natanko takrat, ko za vsak nabor indeksov I \subseteq \{ 1, 2, \ldots n \} velja \left | I \right | \leq \left | \bigcup_{i \in I} A_i \right |

Vzpostavljeno iz »http://www.e-studij.si/Sistemi_razli%C4%8Dnih_predstavnikov«
Osebna orodja
Imenski prostori
Različice
Dejanja
navigacija

Tiskanje/izvoz
orodja