Ашық сызба - бұл бастапқы графиктің барлық шыңдарын қамтитын ішкі граф. Ағаш - бұл жиі қызығушылық тудыратын кеңейтілген субграф. Графиктің барлық шыңдарын қамтитын цикл ауқымды цикл деп аталады.
Қанша тармақша бар?
2n индукцияланған субграфтар (төбелердің барлық ішкі жиындары) және 2м аралық тармақшалар (шеттердің барлық ішкі жиындары) бар.
Ашық тармақшаны қалай табуға болады?
Ал G графының Spanning тармақшасының анықтамасы бойынша тек жиегін жою арқылы алынған ішкі граф болып табылады. Бір жиекті, екі жиекті, үш жиекті және т.б. жою арқылы жиектердің ішкі жиындарын жасасақ. m жиектер болғандықтан, 2^m ішкі жиындар бар. Демек, G-де 2^м тармақшалар бар.
Жалпы ағаш деген нені білдіреді?
Графиктің таралу ағашы (G) жиектердің ең аз санын пайдаланып оның барлық шыңдарын қамтитын G жиыны. Ашық ағаштың кейбір қасиеттерін осы анықтамадан шығаруға болады: «Аралау ағашы барлық шыңдарды қамтитындықтан», оны ажырату мүмкін емес.
График теориясы дегеніміз не?
Жалпы ағаш - барлық шыңдары шеттердің ең аз ықтимал санымен жабылған сызбасының G ішкі жиыны. Демек, таралатын ағашта циклдар болмайды және оны ажырату мүмкін емес.. Осы анықтама бойынша біз әрбір қосылған және бағытталмаған G графигінде кемінде бір тарау ағашы бар деген қорытынды жасауға болады.
