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

3. gyakorlat, 2005. március 4.

                                       Koblinger Egmont <egmont@cs.bme.hu>

Perfekt gráfok; Élszínezés; Pert módszer

32. Mutassunk olyan nem perfekt gráfot, amelyre χ(G) = ω(G).

33. Legyenek egy gráf csúcsai a számok 1-től n-ig, és két (különböző) csúcs akkor legyen összekötve, ha ez egyik osztója a másiknak. Bizonyítsuk be, hogy az így kapott gráf minden n-re perfekt!

34. Adott a síkon néhány körvonal, ezekhez rendeljük a következő G gráfot. G csúcsai feleljenek meg egy-egy adott körvonalnak, és kettő akkor legyen összekötve, ha a két megfelelő körvonal egyike teljesen a másik belsejében halad. Bizonyítsuk be, hogy az így megadott G gráf perfekt.

35. Bizonyítsuk be, hogy az összehasonlítási gráf perfekt.

36. Bizonyítsuk be, hogy egy intervallumgráf komplementere összehasonlítási gráf.

37. Mennyi a Petersen-gráf élkromatikus száma?

38. Határozzuk meg K_{n} élkromatikus számát. Mutassunk is egy jó élszínezést.

39. n csapat körmérkőzést szeretne játszani (mindegyik csapat mindegyikkel egy meccset). Legalább hány forduló szükséges ennek lebonyolításához? (Egy fordulóban több pályán is folyhat párhuzamosan mérkőzés.)

40. Legyen G olyan gráf, melyre χ(G) = k. Bizonyítsuk be, hogy G élei irányíthatóak úgy, hogy a leghosszabb irányított út legfeljebb k pontot tartalmazzon.

41. Állapítsuk meg a feladat elvégzéséhez minimálisan szükséges idő hosszát az alábbi PERT diagramon:

42. Állapítsuk meg, hogy a p paraméter függvényében mennyi a feladat elvégzéséhez minimálisan szükséges idő az alábbi PERT diagram által leírt munkafolyamatnál! Melyek a kritikus tevékenységek?

43. A G irányított gráf csúcsai legyenek egy n elemű halmaz összes részhalmazai. Az A részhalmazból akkor vezessen egy irányított él a B részhalmazba, ha A ⊂ B, de A ≠ B. Az A-ból B-be vezető élhez rendeljük hozzá az |A| + |B| értéket. Határozzuk meg az így kapott PERT feladatban a szükséges időt és a kritikus tevékenységeket!