Негізгі ұғымдар - Граф G=(V,E) екі жиыннан: төбелері деп аталатын шекті жиын элементтерінен және қабырғалары деп аталатын шекті жиын элементтерінен тұрады.
- G=(V, E) графы
- V={v1, v2, v3, v4, v5} ;
- E={e1, e2, e3, e4, e5, e6, e7}
Негізгі ұғымдар - ek қабырғасын анықтайтын vi және vj төбелері шеткі төбелер деп аталады.
- Шеткі төбелері бірдей болса, онда барлық қабырғалары параллель (e1,e4 ) болып табылады.
- Ілмек- тұйық қабырға (e5) .
- Төбесіне жататын қабырға инцидентті деп аталады (e1 қабырғасы v1 и v2төбелеріне инцидентті).
Негізгі ұғымдар - Оқшауланған төбелері ешқандай қабырғаға инцидентті болмайды (v3).
- Кейбір қабырғалардың шеткі төбелері болатын екі төбелері сыбайлас болып табылады (v1, v4).
- Егер екі қабырғаның ортақ шеткі нүктесі болатын болса, олар сыбайлас деп аталады (e1, e2).
Негізгі ұғымдар - Ішкі граф - өзі граф болып табылатын графтың кез келген бөлігі.
Граф түрлері - G=(V,E) графының ілмегі мен параллель қабырғасы болмаса, онда ол қарапайым граф деп аталады.
- G=(V,E) графы қарапайым және төбелерінің əрбір жұбы сыбайлас болатын болса, оны толық граф деп атаймыз.
Граф түрлері - Нөл-граф – бос қабырғалар жиыны.
- Бірнеше қабырғалы G графы мультиграф деп аталады.
Граф түрлері - Ілмегі мен бірнеше қабырғалары бар G графы псевдограф деп аталады.
Бағытталмаған граф - Қабырғаларының белгілі бір бағыты жоқ G графын бағытталмаған деп атаймыз.
Бағытталған граф - Белгілі бір бағыты бар G графын бағытталған граф деп атаймыз.
- Бағытталған қабырға доға деп аталады.
- Графтың алгебралық жүйе ретіндегі нақты тапсырмасы.
- Графты беру үшін әр қабырғаға екі элементтен тұратын төбелер жиынын көрсету жеткілікті- біз оны қабырғамен анықтаймыз.
- {{a,b},{b,c},{a,c},{c,d}}
Графтарды анықтау тәсілдері Графтарды анықтау тәсілдері - 3) Сыбайлас матрица.
- A сыбайлас матрицасының aij элементтері қарастырылып отырған төбелерін қосатын қабырғалар санына тең.
- Суретте көрсетілген G бағытталмаған графы үшін сыбайлас матрицасы келесідей болады:
Бағытталған графтың сыбайлас матрицасы - Суретте көрсетілген G бағытталған графы үшін сыбайлас матрицасы келесідей болады:
Графтарды анықтау тәсілдері - 4) Инциденттік матрицасы.
- В инциденттік матрицасы - бұл жолдары граф төбелеріне, ал бағандары қабырғаларына сәйкес келетін кесте.
- Матрица элементтері келесідей анықталады:
Графтарды анықтау тәсілдері Бағытталған графтың инциденттік матрицасы - 2) бағытталған граф үшін
- -1, егер ej қабырғасы vi төбесіне жатса;
- 1, егер ej қабырғасы vi төбесінен жатпаса;
- bij= 2, егер ej қабырғасы -vi төбесінің ілмегі болса;
- 0, егер ej мен vi инцидентті болмаса.
Маршрут - G=(V,E) графындағы маршрут – ei, 1 i k қабырғасының шеткі төбесі vi-1 и vi болатын, төбесінен басталатын және аяқталатын төбелері мен қабырғаларының шеткі ауыспалы тізбегі v0, e1, v1, e2,…,vk-1, ek, vk.
Маршрут - Егер шеткі төбелері әртүрлі болса, маршрут ашық деп аталады (v1, e1, v2, e2, v3, e8, v6, e9, v5, e7, v3, e11, v6).
- Егер шеткі төбелері сәйкес келсе, маршрут тұйық деп аталады(v1, e1, v2, e2, v3, e7, v5, e3, v2, e4, v4, e5, v1).
-
Тізбек - Барлық қабырғалары əр түрлі болатын маршрут тізбек деп аталады.
- Егер оның шеткі төбелері әртүрлі болса, тізбек қарапайым деп аталады (v1, e1, v2, e2, v3, e8, v6, e11, v3).
- Егер оның шеткі төбелері сәйкес келсе, тізбек тұйық деп аталады(v1,e1,v2,e2,v3,e7,v5,e3,v2,e4,v4,e5,v1).
Достарыңызбен бөлісу: |
