Лекция Ағаштар және оның қасиеттері. Ағаштар. Негізгі ұғымдар және анықтамалар. Ағаштарда вектор-циклдар. Мультиграфтың циклді базисі
жүктеу/скачать 44,07 Kb.
|
13-лекция
| 2. Ағаштарда вектор - циклдар.
Айталық G = (V,X) – мультиграф берілген болсын, бұл жерде X = {x1,…,xm}, m ≥ 1. X қабырға үшін кез келген бағдар енгіземіз, яғни әр бір x = {υ,ω}ÎX қабырғаны не x' = (υ,ω), не x' = (ω,υ) болған х' доғаға аустырамыз. Нәтижеде берілген G = (V,X) мультиграфтан D= (V,X') – бағытталған мультиграф аламыз. Енді G мультиграфтағы кез келген μ = υ1 y1 υ2 y2,…, υk yk υ1 (27) циклды қарастырамыз, бұл жерде yi = {υi , υi+1}ÎX , i=1,2,…,k, k ≥ 2, сонымен υk+1= υ1. (27) жазылу μ циклдың әрбір yi = {υi , υi+1} қабырға арқылы υі төбеден υі+1 төбеге бағыт бойынша қозғалуын білдіреді. Бұл жерде µ циклді yi = {υi , υi+1} таңдалған бағдар бойынша бағытталған қабырға арқылы өтеді деп айтамыз, егер yi' = (υi , υi+1) болса. Басқа жағдайда, яғни yi' = (υi+1 , υi) болса, μ цикл қарама – қарсы таңдалған бағдар бойынша бағытталған қабырға арқылы өтеді деп айтылады. Айталық Zm – бүтін санды координаталы m өлшемді векторлар жиыны және μ – G мультиграфтағы өзіне тиісті қабырға арқылы таңдалған бағыт бойынша өтетін қайсыбір цикл болсын. 13-анықтама. Егер C(μ)Î Zm вектордың Ci(μ) і – ы координатасы Ci+(μ) – Сі-(μ) айырмаға тең болса, онда оны вектор- цикл деп айтылады. Бұл жерде Сі+(μ) – μ циклдағы хі қабырға арқылы таңдаулы бағдарланған бағыт бойынша өту саны, Сі-(µ) – сондай бағдар бйынша қарама – қарсы бағыттағы өту саны. 30 – мысал. Айталық G = (V,X) (29a) – сызбада бейнеленген мультиграф болсын. G мультиграфтың қабырғаларына бағдар енгіземіз. Нәтижеде 29б-сызбада бейнеленген D – бағытталған мультиграф құралады. υ2 υ4 υ2 υ4 х8 х¢8 х1 х2 х6 х7 х¢1 х¢2 х¢6 х¢7 υ1 х3 υ3 υ1 х¢3 υ3 х4 х5 х¢4 х¢5 υ5 υ5 a) б) 29 – сызба. G мультиграфтағы кейбір циклдарды қарастырамыз: μ1 = υ1 x1 υ2 x2 υ3 x3 υ1; μ2 = υ1 x3 υ3 x2 υ2 x8 υ4 x7 υ3 x2 υ2 x1 υ1; μ3 = υ1 x3 υ3 x2 υ2 x1 υ1 x4 υ5 x5 υ3 x2 υ2 x1 υ1; μ4 = υ1 x4 υ5 x4 υ1; μ5 = υ3 x7 υ4 x6 υ3. Онда C(μ1) = (1,1,-1,0,0,0,0,0); C(μ2) = (-1,-2,1,0,0,0,1,1); C(μ3) = (-2,-2,1,-1,-1,0,0,0); C(μ4) = (0,0,0,0,0,0,0,0); C(μ5) = (0,0,0,0,0,-1,-1,0). G мультиграфтағы барлық вектор-циклдар жиынын ZGm арқылы белгілейміз. Егер μ1, μ2 ,..., μк циклдар және α1,α2,...,αк рационал сандар үшін С(μ) = α1 C(μ1) +…+αk C(μk) (28) теңдік орындалса, онда μ цикл μ1,..., μк циклдардың сызықты комбинациясы деп айтылады. Бұл жерде (α1,…,αk) Î Q, Q – рационал сандар жиыны. Кейбір кездерде қолайлық үшін (28) теңдікті μ = α1 μ1 +…+ αk μk (29) ретінді жазу қабылданған. Ō арқылы Zm дегі нөлдік векторды белгілейміз (яғни Ō = (0,0,…,0) Î Zm). Егер {μ1,…, μk} циклдар жүйесіне сәйкес болған вектор-циклдар жүйесі сызықты тәуелсіз болса (яғни, егер кез келген α1,α2,…,αk Î Q үшін α1C(μ1) +…+αk C(μk) = 0 теңдіктен α1 =…=αk = 0 келіп шықса), оны тәуелсіз циклдар жүйесі деп айтамыз. Бұл жерде ZGm Î Qm (Qm – m өлшемді сызықты кеңістік) болғандықтан тәуелсіз циклдар жүйесіндегі элементтердің максимал саны m нен аспаун атап өткен жөн. Тағыда, егер {μ1,…,μe} – тәуелсіз циклдар жүйесі және μе+1 цикл оның сызықты комбинациясы болмаса, онда {μ1,…,μe, μe+1} – тәуелсіз циклдар жүйесі болады. жүктеу/скачать 44,07 Kb. Достарыңызбен бөлісу:
|