Лекция Ағаштар және оның қасиеттері. Ағаштар. Негізгі ұғымдар және анықтамалар. Ағаштарда вектор-циклдар. Мультиграфтың циклді базисі
жүктеу/скачать 44,07 Kb.
|
13-лекция
- Бұл бет үшін навигация:
- 39 – тұжырым.
- Алгоритм № 6.
| 37 – тұжырым. Айталық, G = (V,X) m қабырғалы, n төбелі байланысты граф және сонымен m = n-1 теңдік орындалатын болсын. Онда G ағаш болады.
38 – тұжырым. G – ағаш болса, онда G дағы кез келген тізбек жәй тізбек болады. 39 – тұжырым. (a) тұжырымның ақиқат болуы үшін (d) тұжырымның орындалуы қажет және жеткілікті. 40 – тұжырым. (a) тұжырымның ақиқат болуы үшін (e) тұжырымның орындалуы қажет және жеткілікті. Байланысты графтың бұтақ ағашы. 12-анықтама. Барлық төбелері G графтың төбелерінен құралған және ағаш болатын кез келген ішграф G байланысты графтың бұтақ ағашы деп айтылады. Егер G байланысты граф болса, онда 35 – тұжырымға сәйкес G графтың бұтақ ағашы (егер ол бар болса) n(G) – 1 қабырғадан құралған болуы қажет. Сондықтан G графтың кез келген бұтақ ағашы G дан дәл m(G) – (n(G) – 1) = m(G) – n(G)+1 қабырғаны қашықтату нәтижесі болады. Осы m(G) – n(G)+1 сан байланысты G графтың цикломатикалық саны деп айтылады және ν(G) арқылы белгіленеді. Енді кез келген байланысты G = (V,X) псевдограф үшін бұтақ ағаштың бар екендігін көрсетеміз. Алгоритм № 6. 1 – қадам. G псевдографтың ішграфы және ағаш болған G1 ді құрайтын G дағы кез келген u1 төбені таңдаймыз. Айталық i=1 болсын. 2 – қадам. Егер i=n болса, бұл жерде n=n(G), онда Gi – ізделінген G ағаш бұтағы болып есептеледі. Басқа жағдайда 3 – қадамға өтеміз. 3 – қадам. Айталық G псевдографтың ішграфы және u1,…,ui (1 ≤ i ≤ n-1) төбелерге ие болған Gi ағаш құрылған болсын. Енді Gi графқа ui+1 Î V жаңа төбе және {ui+1, uj} жаңа қабырғаны қосып Gi+1 граф құрамыз, бұл жерде ui+1 төбе Gi графтағы uj төбеге іргелес. 36 – тұжырымға сәйкес Gi+1 граф ағаш болады. i: = i+1 амалды орындап 2 – қадамға өтеміз. жүктеу/скачать 44,07 Kb. Достарыңызбен бөлісу:
|