Лекция Ағаштар және оның қасиеттері. Ағаштар. Негізгі ұғымдар және анықтамалар. Ағаштарда вектор-циклдар. Мультиграфтың циклді базисі
жүктеу/скачать 44,07 Kb.
|
13-лекция
- Бұл бет үшін навигация:
- 41 – тұжырым.
| 3. Мультиграфтың циклді базисы.
G мультиграфтан алынған кез келген цикл сызықты комбинациялы болса {μ1,…, μk} тәуелсіз циклдар жүйесі G мультиграфтың циклды базисы деп айтылады. Енді G мультиграфта циклді базистің бар болу мәселесін қарастырамыз. G мультиграф ациклдық деп айтылады, егер не m=0, не ZGm = {0}, яғни G да жәй циклдар жоқ болса. Осыдан ациклдық мультиграфта циклдік базистер жоқ екендігін көрү мүмкін. 41 – тұжырым. Егер G мультиграф циклді болса, онда G құрамында циклді базис болады. Кез келген мультиграфтың циклді базисін табу мәселесі: Алгоритм № 8. Айталық G байланысты мультиграф болсын. Егер ν(G) = 0 болса, онда G – ациклды мультиграф болады, демек циклды базис жоқ . Енді ν(G) > 0 болсын. Онда G мультиграфтан Т бұтақ ағаш айырып аламыз. Айталық n = n(G), m = m(G), x1,…,xn-1 – Т дағы қабырғалар, ал xn,…,xm – G мультиграфтың басқа қабырғалары болсын. Бұл жерде ν(G) > 0 болғандықтан n ≥ 2, m ≥ n теңсіздіктер орындалатындығын байқау қиын емес. Сонғы қабырғалар саны m – n + 1 ге тең, яғни ν(G) сәйкес келеді. Енді Т ағашқа кез келген бір xi i=n,…,m, қабырғаны қосу арқылы G мультиграфтан қосылған хі қабырғадан өтетін және μі-(n-1) – жәй цикл болған ішграф айырып аламыз. Осындай тәсілмен {μ1,…,μm-n+1} жәй циклдар жиынын табамыз. Осы жүйенің әр бір циклында басқа циклдарда болмаған қабырға қатысқандықтан табылған циклдар жүйесі тәуелсіз болады. Демек, біз G мультиграфтың циклді базисі болған ν(G) элементті тәуелсіз циклдар жүйесін таптық. 31 – мысал. № 8 алгоритм негізінде 31а – сызбада бейнеленген G мультиграфтың циклді базисін табамыз. Мынаған иеміз: ν(G) = m(G) – n(G) + p(G) = 8-4+1 = 5 > 0, яғни G мультиграф ішінде циклді базис бар. G мультиграфтан кез келген Т ағаш бұтағын айырып аламыз. 31б – сызбада Т бұтақ ағашын айырып алуда G мультиграфтағы қашықтатылған қабырғалар пунктирлік сызықтар арқылы көрсетілген. υ2 υ2 х2 х3 х2 х3 х5 х5 υ 1 х7_ _х8 υ4 υ1 х7- -х8 υ4 х6 х1 х6 х4 х1 х4 υ3 υ3 a) б) 31 – сызба Т бұтақ ағашын айырып алуда G байланысты мультиграфтан барлығы ν(G) = 5 қабырға, яғни х3,х4,х6,х7,х8 қабырғалар қашықтатылған. Осы қабырғаларды Т ға біртіндеп қосу арқылы G мультиграфтың циклді базисын құрайтын жәй циклдерге ие боламыз: μ1 = υ1x2υ2x3υ4x5υ1; μ2 = υ1x5υ4x4υ3x1υ1; μ3 = υ1x5υ4x6υ1; μ4 = υ1x2υ2x7υ3x1υ1; μ5 = υ1x2υ2x8υ3x1υ1. Осы алгоритмнің сипаттамасынан алгоритм нәтижесінде алынған G мультиграфтың циклді базисі барлық уақыт жәй циклдардан құралатындығын көру мүмкін . жүктеу/скачать 44,07 Kb. Достарыңызбен бөлісу:
|