Bevezetés a számításelméletbe II.
3. gyakorlat 2003. február 28.
 
 
Perfekt gráfok, élszínezés, PERT

 

1. Mutassunk példát olyan $G$ gráfra, amely nem perfekt, de teljesül rá a $\chi(G)=\omega(G)$ egyenlőség.
2. Egy legalább két csúcsú teljes gráf valamely $v$ csúcsához illeszkedő élek közül néhányat elhagytunk. Bizonyítsuk be, hogy az így nyert gráf perfekt.
3. Igazoljuk, hogy tetszőleges $G$ gráfra $\omega(L(G)) \ge \Delta(G)$. Igaz-e mindig az egyenlőség is?
4. Legyen $G$ egy 100-reguláris egyszerű gráf 2003 ponttal. Határozzuk meg $\chi'(G)$ értékét!
5. Állapítsuk meg, hogy mennyi a feladat elvégzéséhez minimálisan szükséges idő az alábbi PERT-diagram által leírt munkafolyamatnál? Adjuk meg a kritikus utakat is!
   
   
   
   
   
   
   
   
6. Határozzuk meg az alábbi munka elvégzéséhez szükséges minimális időt, és a kritikus utakat a $p$ paraméter függvényében.
   
   
   
   
   
   
   
   
7. Adott egy $G$ irányítatlan egyszerű gráf. Bizonyítsuk be, hogy a gráf éleinek tetszőleges irányított kör mentes irányítása esetén az emeletek száma legalább $\chi(G)$.
8. Bizonyítsuk be, hogy az 5 pontú teljes gráf élgráfja $L(K_5)$ nem perfekt.
9. HF Előbb páratlan, majd páros $n$ esetére is határozzuk meg az $n$ pontú teljes gráf élkromatikus számát!
10. A $G_k$ gráf $(k \ge 2)$ egy $(v_1,v_2,\dots,v_{2k})$ Hamilton-körből, valamint a $k$ darab további $\{v_1,v_{k+1}\}, \{v_2,v_{k+2}\}, \dots ,\\ \{v_k, v_{2k} \}$ élből kapjuk.
    1. Határozzuk meg $G_k$ élkromatikus számát.
    2. HF Határozzuk meg $G_k$ kromatikus számát is tetszőleges $k$-ra.
11. Legyen $G''$ egy irányított körmentes gráf. Tetszőleges $u$ és $v$ csúcsra húzzunk be egy $(u,v)$ élt, ha létezik $u$-ból $v$-be vezető irányított út, így nyerjük a $G'$ gráfot. Továbbá $G'$-ből az irányítások elhagyásával kapott gráfot $G$ jelöli.
    1. Mutassuk meg, hogy $\omega(G) \ge m+1$, ahol $m$ a $G''$ egy leghosszabb irányított útjának hosszát (éleinek számát) jelöli!
    2. Bizonyítsuk be, hogy $m+1$ színnel színezhető $G$ !
    3. Igazoljuk, hogy $G$ perfekt!