Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1 сурак
Графтардағы тәуелсіз жиындар. Кликтер
Граф төбесінің тәуелсіз жиыны деп жұп ретінде іргелес болмайтын кез келген жиын, яғни бос ішкі графты туындататын төбелер жиыны. Тәуелсіз жиын максималды деп аталады, егер ол басқа тәуелсіз бір жиынның жеке ішкі жиыны болмайтын болса және ең үлкен деп аталады, егер оның құрамындағы төбелердің саны ең максималды болса. графындағы ең үлкен тәуелсіз жиындағы төбелер саны деп белгіленеді және графтың тәуелсіздік саны деп аталады.
Граф кликі дегеніміз толық ішкі графты тудыратын төбелер жиынын айтады, яғни әрбір екеуі іргелес болатын төбелер жиыны. Ең үлкен мөлшердегі кликтың төбелер саны графтың кликтік саны деп аталады және ретінде белгіленеді.
Графтың төбелік толтыруы – графтың әрбір қабырғасы кемінде бір төбеге инцидентті болатын төбелер жиыны. графының толтыруындағы төбелердің ең кіші саны ретінде белгіленеді және графтың төбелік толтыру саны деп аталады. 9.1 суретіндегі графта ең үлкен тәуелсіз жиын ретінде жиыны алынады, ең үлкен клик - жиыны, ең кіші төбелік толтыруы - жиыны алынады.
9.1 сурет.
Тәуелсіз жиын есептері мен төбелік толтыру есептері арасында келесі дерек негізінде байланыс орнатылған.
1 Теорема. графының төбе жиының ішкі жиыны төбелік толтыру ретінде қабылданады, егер - тәуелсіз жиын шарты орындалатын болса.
2 сурак
Графтар теориясының бастапқы түсініктері
Граф" термині бір қырлы емес,оны әр түрлі кітаптарда келтірілген анықтамаларды салыстыру арқылы оңай байқауға болады. Бірақ осы анықтамалардың барлығында ортақтық бар. Кез келген жағдайда граф екі жиыннан тұрады – төбелер жиыны және доғалар (қырлар) жиыны, әр бір қыр үшін оны қосатын төбелер жұбы көрсетілген. Төбелер мен қырлар граф элементтері деп аталады. Мұнда тек ақырлы графтар, яғни екі жиыны да ақырлы болатын графтар қарастырылады. Графтың белгілі бір типінің толық анықтамасын алу үшін тағы үш кезеңді анықтап алу қажет.
Алдымен, біз және жұптарын әр түрлі деп есептейтін-есептемейтінімізді келісіп алу керек. Егер әр түрлі деп есептесек,онда реттелген жұптар (жұптағы элементтер реті маңызды), кері жағдайда – реттелмеген жұптар болады. Егер қыры төбесімен төбесін қосатын және жұбы реттелген болса, онда бұл қыр бағытталған деп аталады да, төбесі оның басы, төбесі –соңы болады. Егер бқл жұп реттелмеген болса, онда қыр бағытталмаған деп аталады да, екі төбесі-оның ұштары . Көбінесе барлық қырлары бір типтес не бағытталған,не бағытталмаған қырлы графтар қарастырылады. Сәйкесінше барлық графты да бағытталған не бағытталмаған деп атайды. Суретте қырдың бағдарын (басынан соңына дейінгі бағытын) нұсқау (бағытталған) сызық арқылы бейнелейді. 1.1 суретте бағытталмаған графтар, ал 1.2 суретте бағытталған графтар көрсетілген.
Келесі нақтылауды қажет ететін пункт – әр түрлі қырларда бірдей басы мен соңы бола алады ма? Егер болса, онда графта еселі қырлар рұқсат етіледі. Еселі қырлары бар графты мультиграф деп те атайды. 1.2 суретте екі граф бейнеленген, сол жақтағы бағытталған мультиграф, ал оң жақтағы-бағытталған еселі қырлары жоқ граф болып табылады.
жұбы сәйкес қойылған қыр, яғни төбесін -ның өзімен қосатын қыр ілгек деп аталады. Егер ондай қырлар рұқсат етілмесе, онда ілгексіз графтар қарастырылып жатыр делінеді.