Páros gráfok -- Párosítások

1.
Egy vállalatnál hét pályázó jelentkezett hat üres munkahelyre, egy ember esetleg több helyre is. Aladár az 1-es, Béla az 1-es és 6-os, Csaba a 2-es, 3-as és 4-es, Dénes a 2-es és 5-ös, Elemér a 3-as, 4-es és 5-ös, Ferenc az 1-es és 6-os végül Géza a 6-os munkahelyre.

2.
Állapítsuk meg az előző feladatban szereplő páros gráf(ok)ban

3.
Igaz-e, hogy ha egy összefüggő páros gráfban van Hamilton-kör, akkor van teljes párosítás is? Igaz-e ennek megfordítása?

4.
Ha egy páros gráf minden csúcsának fokszáma r, akkor a gráfban van teljes párosítás. Igazoljuk továbbá, hogy egy ilyen gráf éleit ki lehet színezni r színnel úgy, hogy minden csúcsba különböző színű élek fussanak.

5.
Egy páros gráf egyik pontosztályában van olyan X részhalmaz, melyre $N(X)\leqslant \vert X\vert-2$. Bizonyítsuk be, hogy a gráfban nincsen Hamilton-út.

6.
Mutassuk meg, hogy egy fának legfeljebb egy teljes párosítása van.

7.
Ha egy gráfban van két teljes párosítás, akkor létezik páros hosszúságú kör is.

8.
Bizonyítsuk be, hogy ha egy páros gráf minden csúcsának fokszáma 4, akkor van benne olyan kör, melynek hossza legalább 8.

9.
Egy 2n csúcsú teljes gráfból elhagyjuk egy teljes párosítás éleit. Hány különböző 3 hosszú kör található a maradék gráfban?

10.
Minimálisan hány fordulóban lehet megszervezni n csapat körmérkőzését?

11.
Egy társaságban $\omega$ darab fiú és $\omega$ darab lány van úgy, hogy bármely k darab fiú összesen legalább k darab lányt ismer (ahol $\omega$ jelöli a megszámlálható számosságot). Igaz-e általánosan, hogy a fiúk összeházasíthatók különböző lányokkal (vigyázat: a végtelen rendesen belekavar a dologba)? ($\star$)

12.
Legyenek $A_i (i=1,\ldots,n)$ illetve $B_i (i=1,\ldots,n)$ olyan m-elemű halmazok, amelyek ugyanazt a T halmazt partícionálják (Tnyilván mn elemű). Igazoljuk, hogy van olyan $\sigma\in S_n$ permutáció, amelyre $A_i\cap B_{\sigma(i)}$ semmilyen i-re $(i=1,\ldots,n)$ nem üreshalmaz.

13.
Legyen a nemnegatív elemű, négyzetes A mátrix olyan tulajdonságú, hogy minden sorában és minden oszlopában a számok összege 1 legyen (amúgy az ilyen mátrixot hívjuk duplán sztochasztikusnak). Mutassuk meg, hogy a determinánsa tartalmaz nemnulla kifejtési tagot.

14.
Képzeljünk el egy szigetet, melyen n házaspár tengeti nyomorúságos életét. A sziget fel van parcellázva n darab vadászterületre, minden házaspár pontosan az egyik felett rendelkezhet. Hasonlóképpen n darab mezőgazdasági területre is fel van parcellázva a sziget (a két parcellázás nem feltétlenül esik egybe). Mutassuk meg, hogy minden házaspárhoz található olyan szigetdarabka, melyet mindkét tevékenység szempontjából birtokolnak.

Vissza