Жол, цикл - Ашық тізбек жол деп аталады, егер оның барлық төбелері әр түрлі болса (v1, e1, v2, e2, v3).
- Цикл – бұл тұйық тізбек(егер тізбек қарапайым болса, цикл қарапайым ) (v1,e1,v2,e3,v5,e6,v4,e5,v1).
- Жолдағы қабырғалар саны жол ұзындығы деп аталады. Цикл ұзындығы да дәл осылай анықталады.
- Жолдың әр шеткі емес төбелер дәрежесі 2-ге тең, шеткі төбелер дәрежесі 1-ге тең.
- Циклдің әрбір төбесі 2 дәрежеге немесе басқа жұп дәрежеге ие. Бұл тұжырымнан, атап айтқанда, әрбір төбелері жұп дәрежелі болатын ішкі графтың қабырғалары қате цикл құрайтынын аламыз.
- 3. Жолдағы төбелер саны бір қабырғалар санына артық, онда циклдегідей қабырғалар саны төбелер санына тең.
Граф байланыстығы, байланыстық компоненті - vi мен vj екі төбелері G графында байланысқан деп аталады, егер онда vi—vj жолы болса. Төбелері өзімен байланысқан.
- Егер әр жұп төбелерінің арасында жол болса, граф байланыс деп аталады.
- Байланыстық компоненті – ішкі графтың графпен максималды байланысы.
- 1 байланыс компоненті : {v1, v2, v3, e1, e2, e3}
- 2 байланыс компоненті : {v4, v5, v6, e4, e5, e6}
- 3 байланыс компоненті : {v7, v8, e7}
- 4 байланыс компоненті : {v9}
Төбелер дәрежесі - vj төбесінің deg(vj) дәрежесі деп оған инцидентті қабырғалар, яғни оның айналасындағы төбелер саны айтылады.
- G графының төбелерінің максималды және минималды дәрежелері (G) және (G) белгілерімен белгіленеді, сәйкесінше:
- (G)= (G)=
-
- Егер барлық төбелерінің дәрежелері бірдей болса, G=(V,E) графы тұрақты немесе біртекті (r дәрежелі) деп аталады. Тұрақты графтың дәрежесі оның төбелерінің дәрежесі деп аталады.
Достарыңызбен бөлісу: |
