Лекция Ағаштар және оның қасиеттері. Ағаштар. Негізгі ұғымдар және анықтамалар. Ағаштарда вектор-циклдар. Мультиграфтың циклді базисі



бет5/6
Дата12.01.2023
өлшемі44,07 Kb.
#165429
түріЛекция
1   2   3   4   5   6
Байланысты:
13-лекция

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 қабырға, яғни х34678 қабырғалар қашықтатылған. Осы қабырғаларды Т ға біртіндеп қосу арқылы 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 мультиграфтың циклді базисі барлық уақыт жәй циклдардан құралатындығын көру мүмкін .


Достарыңызбен бөлісу:
1   2   3   4   5   6




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет