Лекция Ағаштар және оның қасиеттері. Ағаштар. Негізгі ұғымдар және анықтамалар. Ағаштарда вектор-циклдар. Мультиграфтың циклді базисі
жүктеу/скачать 44,07 Kb.
|
13-лекция
- Бұл бет үшін навигация:
- Алгоритм № 7.
| Ескерту. Жалпы айтқанда байланысты графтың бұтақ ағашы тек бірғана әдіс арқылы алынбайды. Байланысты граф бұтақ ағаштарының саны жалпы өте үлкен болуы мүмкін. Мысалы n төбелі толық граф үшін ол nn-2 ге тең.
28 – мысал. № 6 – алгоритм негізінде 25 – сызбада бейнеленген G графтың бұтақ ағашын айырамыз. 26 – сызбада алгоритм негізінде алынған Gi , i=1,2,3,4,5 графтар тізбегі келтірілген. Сонда , n(G) = 5 болғанда G графтың ағаш бұтағы G5 болады. υ2 υ3 υ5 υ2 υ2 υ3 υ2 υ3 υ5 υ5 υ5 υ1 υ1 υ5 υ5 υ1 υ4 υ1 υ1 υ4 υ1 G1 G2 G3 G4 G5 25 – сызба. 26 – сызба. Тиелген графтардың минимал бұтақ ағаштары. Айталық байланысты G = (V,X) графтың әр бір xÎ X қабырғасына ℓ(x) – қабырқа ұзындығы сәйкес қойылған, яғни G тиелген граф болсын. Анықтама. Байланысты тиелген G граф бұтақ ағашының өзінде болған қабырғалар ұзындықтары қосындысы минимал болған ағаш G графтың минимал бұтақ ағашы (МБА) деп айтылады. Енді G граф үшін МБА табу алгоритімін келтіреміз. Алгоритм № 7. (Байланысты тиелген G графтан МБА ны бөлү): 1 – қадам. G графта минимал ұзындықтағы қабырға айырып аламыз. Ол өзіне инцидентті болған төбемен G2 ішграфты құрайды. i = 2 болсын. 2 – қадам. Егер i = n болса (n = n(G)), онда G1 – ізделінген МБА деп қабылданып, мәселе соңына жетеді. Басқа жағдайда 3 – қадамға өтеміз. 3 – қадам. Енді Gi де жатпайтын, Gi графтағы қалайда бір төбеге инцидентті болған және G графтың барлық қабырғалары ішінен таңдалған минимал ұзындықтағы жаңа қабырғаны Gi графқа қосып Gi+1 граф құраймыз. Осы қабырғамен бірге оған инцидентті болған, бірақ Gi де жатпайтын төбеніде Gi+1 ге енгіземіз. i:=i+1 орындап 2 – қадамға өтеміз. 29 – мысал. 27 – сызбада бейнеленген G тиелген графтың МБА сын алгоритм негізінде анықтаймыз. 28 - сызбада алгоритмді орындау нәтижесінде алынған Gi, i = 2, 3,4,5 графтар тізбегі келтірілген. Бұл жерде n(G)=5 болғандықтан G графтың МБАсы G5 болады. υ2 2 υ3 1 u5 4 1 3 5 3 υ1 4 υ4 27- сызба υ2 υ2 υ2 υ3 υ2 υ3 2 2 1 1 1 1 1 1 1 3 υ5 υ5 υ5 υ5 υ1 υ1 υ1 υ4 28 – сызба. жүктеу/скачать 44,07 Kb. Достарыңызбен бөлісу:
|