Bevezetés a számításelméletbe II.

4. gyakorlat, 2005. március 11.

                            Koblinger Egmont <egmont@cs.bme.hu>

Párosítások

44. 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.

• Ábrázoljuk a helyzetet páros gráffal.

• Döntsük el, hogy betölthető-e mind a hat munkahely. Ha nem mind, akkor legfeljebb hány tölthető be?

• Javít-e valamit, ha Ferencnek több pénzt ígérünk, és így elérjük, hogy elfogadja a 2-es munkahelyet?

45. 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?

46. Igazoljuk, hogy ha egy páros gráf r-reguláris (vagyis minden csúcsának fokszáma r), akkor a gráfban van teljes párosítás. Mit állíthatunk ezen gráfok élkromatikus számáról?

47. Egy páros gráf egyik pontosztályában van olyan X részhalmaz, melyre |N(X)| ⩽ |X| − 2. Bizonyítsuk be, hogy a gráfban nincsen Hamilton-út.

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

49. Igazoljuk, hogy ha egy gráfban van két teljes párosítás, akkor létezik benne páros hosszúságú kör is.

50. 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.

51. 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?

52. 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 (amúgy az ilyen mátrixot hívjuk duplán sztochasztikusnak). Mutassuk meg, hogy a determinánsa tartalmaz nemnulla kifejtési tagot.

53. Képzeljünk el egy szigetet, amely fel van parcellázva n darab azonos méretű vadászterületre, valamint n azonos méretű mezőgazdasági területre is (a két parcellázás nem feltétlenül esik egybe). Mutassuk meg, hogy beköltöztethető n lakó úgy, hogy mindenki egy vadászterület és egy mezőgazdasági parcella fölött rendelkezzék, és mindenkhez található legyen olyan szigetdarabka, melyet mindkét tevékenység szempontjából birtokol.