Barion Pixel Frobenius tétele | mateking
 

Frobenius tétele

A $G(A, B, E)$ páros gráfban akkor és csak akkor létezik teljes párosítás, ha

$ \mid A \mid = \mid B \mid$ és

$ \mid X \mid \leq \mid N(X) \mid $ minden $X \subseteq A $ ponthalmazra.

Frobenius tétele arról szól, hogy mikor létezik egy gráfban teljes párosítás.

1.

a) Egy bálon 10 fiú és 10 lány vesz részt. Minden lány legalább 6 fiút ismer és minden fiú is legalább 6 lányt. Az ismertségek kölcsönösek. A nyitótáncon mindenki ismerőssel szeretne táncolni. Bizonyítsuk be, hogy ez lehetséges.

b) Egy 12 csúcsú páros gráfban minden csúcs foka 3 vagy 4. Bizonyítsuk be, hogy van a gráfban teljes párosítás.