Një nëngraf që përfshin është një nëngraf që përmban të gjitha kulmet e grafikut origjinal. Një pemë e shtrirë është një nëngraf që përfshin shpesh që është me interes. Një cikël në një grafik që përmban të gjitha kulmet e grafikut do të quhet një cikël i shtrirë.
Sa nëngrafikë që përfshijnë?
Ka 2n nëngrafë të induktuar (të gjitha nëngrupet e kulmeve) dhe 2m nëngrafikë që përfshijnë (të gjitha nëngrupet e skajeve).
Si mund të gjej një nëngraf që përfshin?
Dhe sipas përkufizimit të nëngrafit të shtrirjes së një grafi G është një nëngraf i marrë vetëm nga fshirja e skajeve. Nëse bëjmë nënbashkësi të skajeve duke fshirë një skaj, dy skaj, tre skaj e kështu me radhë. Meqenëse ka m skaje, ka edhe 2^m nënbashkësi. Prandaj G ka 2^m nëngrafë që përfshijnë.
Çfarë nënkuptohet me pemën që përfshin pemë?
Pema që përfshin një grafik (G) është një nënbashkësi e G që mbulon të gjitha kulmet e tij duke përdorur numrin minimal të skajeve. Disa veti të një peme që shtrihet mund të nxirren nga ky përkufizim: Meqenëse "një pemë që shtrihet mbulon të gjitha kulmet", ajo nuk mund të shkëputet.
Çfarë është teoria e grafikëve që përfshin?
Një pemë e shtrirë është një nëngrup i grafikut G, i cili ka të gjitha kulmet e mbuluara me numrin minimal të mundshëm të skajeve. Prandaj, një pemë që shtrihet nuk ka cikle dhe nuk mund të shkëputet. Nga ky përkufizim, ne mund të nxjerrim një përfundim se çdo Grafik G i lidhur dhe i padrejtuar ka të paktën një pemë që përfshin.
