Орындаған: Шады А
Графтардың тізбелері, циклдері, жолдары және контурлары
жүктеу/скачать 0.56 Mb.
|
- Бұл бет үшін навигация:
- Ақырлы және шексіз графтар
| Графтардың тізбелері, циклдері, жолдары және контурлары
Бағдарланбаған графтар ішін келесі ұғымдар орынды: Тізбе – қабырғалардың ақырлы немесе шексіз тізбегі, (..., , ,...) S g1 g2 мҧндағы, k g - қабырғасының бір тӛбесі k1 g - қабырғасының тӛбесі, ал екінші тӛбесі k1 g қабырғасының тӛбесі ------------------------- g k-1 g k g k+1 Бұл жағдайда, бір қабырға немесе төбе бірнеше рет кездесуі мүмкін Егер тізбенің барлық қабырғалары әртҥрлі болса, онда оны жай тізбе деп, керісінше жағдайда, құрама немесе күрделі тізбе деп атайды. Жай тізбеде тӛбелер қайталануы мҥмкін. Егер тізбеде бірде бір тӛбелер қайталанбайтын болса, онда ол қарапайым тізбе деп аталады. Цикл деп белгілі бір i x тӛбесінен басталып , сол тӛбемен аяқталатын ақырлы тізбені айтады. Жай, кҥрделі немесе қҧрама циклдер тізбелер деп аталады. Бағдарланған графтар ҥшін келесі қосымша ҧғымдар енгізілген: G(X) графындағы жол деп ( , ...) g1 g2, доғаларының тізбегін айтамыз, мҧндағы әрбір алдыңғы доғаның соңы келесі доғаның басы болып табылады. Жай ,қҧрама (кҥрделі), қарапайым жолдар бар. Графтың контуры деп алғашқы тӛбесі соңғы тӛбемен сәйкес келетін (беттесетін) ақырлы жолды айтады. Жай, қҧрама (кҥрделі), қарапайым контурлар бар. Жолдың ұзындығы – ол осы s жолындағы доғалар тізбегіндегі доғалардың саны L(s) . Жол шексіз болған жағдайда L(s) . Егер кез келген i j x , x ҥшін ( ) i j x G x болғандықтан ( ) j i x G x болса, яғни екі сыбайлас (іргелес) i j x , x тӛбелері әруақытта қарама-қарсы бағдарланған доғалармен қосылған болса, онда графты симметриялы деп атайды. Егер кез келген i j x , x ҥшін ( ) i j x G x болғандықтан ( ) j i x G x болса, яғни сыбайлас (іргелес) қос (екі) төбелері тек қана бірдей бағытта қосылған болса, онда графты антисимметриялы деп атайды. Ақырлы және шексіз графтар Егер графтың тӛбелерінің саны ақырлы болса, онда оны ақырлы граф деп атайды. G(X) графы G ақырлы деп аталады, егер әрбір x X тӛбесі ҥшін G(х) ақырлы жиын болса, және шексіз деп аталады егер оның тӛбелерінің саны шексіз болса. Егер X арқылы X жиынының элементтерінің санын белгілесек, онда 99 а) G(X) графы ақырлы, егер X , болса; b) G(X) графы G – ақырлы, егер x X ҥшін G(x) , болса; с) G(X) графы 1 G – ақырлы, егер x X ҥшін ( ) 1 G x болса. Бір уақытта G және 1 G ақырлы болатын G(X) графын локальды ақырлы граф деп атайды. Әрине, кез келген ақырлы граф локальді ақырлы граф болады. жүктеу/скачать 0.56 Mb. Достарыңызбен бөлісу:
|