13

---

Grafová úloha

Chceme najít graf

• stejný počet vrcholů
• souvislý
• acyklický (v grafu nejsou mezi dvěma vrcholy dvě různé cesty)
• s minimálním ohodnocením

Taková úloha se nazývá úloha nalezení minimální kostry grafu.

Kostra grafu

Kostra grafu je podgraf, který obsahuje všechny vrcholy původního grafu a který je souvislý a neobsahuje žádný cyklus.

Všimněte si

Kostra

• vždy existuje (u souvislého grafu)
• má n-1 hran

---

13