13-лекция
Ағаштар және оның қасиеттері.
Ағаштар. Негізгі ұғымдар және анықтамалар.
Ағаштарда вектор-циклдар.
Мультиграфтың циклді базисі.
Цикломатикалық матрица.
_________________________________________________
Ағаштар. Негізгі ұғымдар және анықтамалар.
Егер G граф байланысты, бірақ цикл болмаса оны ағаш деп айтамыз.
Барлық байланыс компоненталары ағаш болған G граф орман деп айтылады.
27 – мысал: 23 – сызбада бейнеленген G граф ағаш болады.
23 – сызба .
Ағаштардың қасиеттері.
Кезектегі тұжырымдар ақиқат:
Сызбадағы G граф ағаш болады ;
G граф – байланысты және жәй циклға ие емес ;
G граф байланысты және оның қабырғалары төбелер санынан дәл бір санға кем ;
G графтың кез келген екі төбесін тек жалғыз бір тізбек арқылы жалғастыру мүмкін ;
G графта цикл жоқ, бірақта оған кез келген бір қабырға қосу арқылы дәл бір ғана жәй цикл (қосылған қабырға арқылы өтетін) алу мүмкін.
33 – тұжырым. Егер G ағаштың кемінде бір қабырғасы болса, бұл ағашта аспалы төбе әлбетте табылады.
34 – тұжырым. Айталық, G байланысты граф, υ – осы графтағы аспалы төбе, G1 – G графтан υ төбе және оған инцидент болған қабырғаны қашықтату арқылы алынған граф болсын. Онда G1 – байланысты граф болады.
Ескерту. 34 – тұжырым кез келген G псевдограф үшын өз күшін сақтайды.
35 – тұжырым. Айталық G – n төбелі және m қабырғалы ағаш болсын. Онда m = n-1.
36 – тұжырым. Айталық G1 – граф ағаш болсын. Егер G граф G1 графқа жаңа υ төбені және {υ,ω} қабырғаны, бұл жерде ω – G1 графтан алынған төбе, қосу нәтижесінде алынған болса, онда G – ағаш болады.
Достарыңызбен бөлісу: |
