Vsečni podgraf je podgraf, ki vsebuje vsa oglišča izvirnega grafa. Raztegljivo drevo je raztegljivi podgraf, ki je pogosto zanimiv. Cikel v grafu, ki vsebuje vsa oglišča grafa, bi imenovali raztezni cikel.
Koliko obsegajočih podgrafov je?
Obstaja 2n induciranih podgrafov (vse podmnožice vozlišč) in 2m raztegljivih podgrafov (vse podmnožice robov).
Kako najdem raztegljiv podgraf?
In po definiciji raztegljivega podgrafa grafa G je podgraf, pridobljen samo z brisanjem robov. Če naredimo podmnožice robov tako, da izbrišemo en rob, dva roba, tri robove in tako naprej. Ker je robov m, obstaja 2^m podmnožic. Zato ima G 2^m raztegljive podgrafe.
Kaj pomeni raztegljivo drevo?
Vseljivo drevo grafa (G) je podmnožica G, ki pokriva vsa svoja oglišča z uporabo najmanjšega števila robov. Nekatere lastnosti raztegljivega drevesa je mogoče razbrati iz te definicije: Ker "razsežno drevo pokriva vsa vozlišča", ga ni mogoče prekiniti.
Kaj je teorija razteznih grafov?
Vseljivo drevo je podmnožica grafa G, ki ima vsa oglišča pokrita z najmanjšim možnim številom robov. Zato raztegljivo drevo nima ciklov in ga ni mogoče odklopiti. Po tej definiciji lahko sklepamo, da ima vsak povezan in neusmerjen graf G vsaj eno raztegljivo drevo.
