Promjenjivi podgraf je podgraf koji sadrži sve vrhove originalnog grafa. Razdvojno stablo je razdvojni podgraf koji je često zanimljiv. Ciklus u grafu koji sadrži sve vrhove grafa bi se nazvao razapinjući ciklus.
Koliko ima rasponskih podgrafa?
Postoji 2n induciranih podgrafa (svi podskupovi vrhova) i 2m promjenjivi podgrafi (svi podskupovi ivica).
Kako da pronađem razdvojeni podgraf?
A po definiciji Spanning podgrafa grafa G je podgraf dobijen samo brisanjem rubova. Ako napravimo podskupove ivica brisanjem jedne ivice, dve ivice, tri ivice i tako dalje. Kako ima m ivica, tako postoji 2^m podskupova. Stoga G ima 2^m raspona podgrafa.
Šta znači razapinjuće drvo?
Spanning tree grafa (G) je podskup G koji pokriva sve svoje vrhove koristeći minimalni broj ivica. Neka svojstva razapinjućeg stabla mogu se zaključiti iz ove definicije: Budući da “razapajuće stablo pokriva sve vrhove”, ono se ne može odvojiti.
Šta je teorija rasponskih grafova?
Spanning tree je podskup Grafa G, koji ima sve vrhove pokrivene minimalnim mogućim brojem ivica. Dakle, razapinjuće stablo nema cikluse i ne može se odvojiti.. Ovom definicijom možemo izvući zaključak da svaki povezani i neusmjereni graf G ima barem jedno razapinjuće stablo.
