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

4. gyakorlat, 2007. március 7.

                                Koblinger Egmont <egmont@cs.bme.hu>

Párosítások, Gallai

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

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

42. Határozzuk meg az r-reguláris páros gráfok élkromatikus számát.

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

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

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

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

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

48. Határozzuk meg a független élek maximális számát az alábbi két gráfban. Bizonyítsuk be, hogy nem lehet többet találni!

49. Az a_{1}, a_{2} … a_{2007} csúcsokból álló G gráf a_{i} és a_{j} pontja akkor van összekötve, ha i+j osztható 3-mal (és i ≠ j). Határozzuk meg τ(G), ν(G), ρ(G), α(G), ω(G) értékét.

50. Bizonyítsuk be, hogy Δ(G) · τ(G) ⩾ |E(G)|.

51. Igazoljuk, hogy α(G) ⩾ n − 2ν(G).

52. Bizonyítsuk be, hogy egy háromszögmentes G gráfban α(G) · τ(G) ⩾ |E(G)|.

53. Mutassuk meg, hogy χ_{e}(G) + ν(G) ⩽ e + 1.

54. Határozzuk meg véges egyszerű G gráfokra a \frac{τ(G)}{ν(G)} érték lehető legkisebb és legnagyobb értékét.