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

5. gyakorlat, 2005. március 18.

                                   Koblinger Egmont <egmont@cs.bme.hu>

Gallai tételek

54. Állapítsuk meg a 44. feladatban (múlt gyakorlat) szereplő páros gráf(ok)ban • a minimális lefogó ponthalmazokat és ezek elemszámát,

• a maximális független ponthalmazokat és ezek elemszámát,

• a minimális lefogó élhalmazokat és ezek elemszámát,

• a maximális független élhalmazokat és ezek elemszámát.

55. 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!

56. Az a_{1}, a_{2} … a_{2004} 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.

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

58. Igazoljuk, hogy χ(G) ⩾ \frac{|V (G)|}{α(G)}. Keressünk olyan gráfokat, ahol ez a becslés pontos, illetve ahol pontatlan.

59. Bizonyítsuk be, hogy minden n csúcsú gráfra χ(G) · χ(\overline{G}) ⩾ n.

60. Bizonyítsuk be, hogy egy G teljes páros gráfban (ahol tehát a két színosztály között minden él jelen van) mindig felláll, hogy ν(G) · ρ(G) = |E(G)|.

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

Puska: τ (tau) – lefogó pontok minimális száma α (alfa) – független pontok maximális száma ρ (ró) – lefogó élek minimális száma ν (nű) – független élek maximális száma