Najmanjše vpeto drevo, ali bolje, iskanje le-tega je znan problem v vedi informatike. Da pa bi razumeli kaj sploh iščemo, potrebujemo najprej spoznati nekaj osnovnih pojmov.
Graf je matematična struktura. Ima vozlišča ter povezava, kjer vsaka povezava povezuje dva vozlišča.