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

5. gyakorlat, 2006. március 22.

                                      Koblinger Egmont <egmont@cs.bme.hu>

Gallai tételek – Színezések 1.

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

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

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

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

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

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

51. Hány szín szükséges az alábbi gráf pontjainak kiszínezéséhez?

52. Legyen V (G) = {v_{1}, …, v_{100}}, ahol v_{i} és v_{j} között akkor és csak akkor megy él, ha 7 ≥ |i − j|. Mennyi G kromatikus száma?

53. Minden páros G gráfra χ(G) ⩽ 2. Mikor nem áll egyenlőség?

54. Bizonyítsuk be, hogy minden páros G gráfra χ(G) = ω(G).

55. Legyenek G csúcsai az összes természetes számok és legyen az n és m csúcs éllel összekötve pontosan akkor, ha n + m páratlan. Mennyi a gráf kromatikus száma?

56. A V (G) = 1, 2, … 1023 ponthalmazon definiáljuk a G gráfot úgy, hogy benne k és m pontosan akkor van összekötve éllel, ha nem egyenlőek és az egyik osztja a másikat. Határozzuk meg χ(G) é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