Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Қос жарнақты графтар.
Граф қос жарнақты деп аталады ,егер оның төбелерiнің көпшілігін екi iшкi жиынға бөлшектеуге болып, әр қабырғаның соңдары әр түрлi iшкi жиындарға жататын болса. Бұл iшкi жиындар үлестер деп аталады. Қорыта келгенде, үлестiң әрқайсысымен бос iшкi графты тудырады. Қарапайым байланыс кез-келген үшін: үлестің бiреуі жұп нөмiрмен төбе тудырады, басқасы – тақ қос жарнақты графтың мысалы бола алады. Граф - графтың мысалы , қос жарнақты емес болып табылатын: оның төбесінің көпшілігі кез-келген екi iшкi жиынға бөлiктеуiнде, бұл iшкi жиындардың бiрiнде екi жапсарлас шыңдар пайда болады.
Мысалы, қос жарнақты графы ұғымының қолданбалы мағынасы мұндай граф арқылы екi түрлi объектiлердiң арасындағы қарым-қатынасты пiшiндеумен байланысты, ал мұндай қарым-қатынастар iс жүзiнде жиi ұшырасады.Математикада мұндай қарым-қатынастар сирек емес, олардың түрлерінің кең таралғанының бiрi - инциденттiк қарым-қатынасы. Мейлi - жиын, ал - оның iшкi жиындарының үй-iшiсi. элементі және жиын бiр-бiрiне инцидент , егер болса . Инциденттiктiң қарым-қатынасын қос жарнақты графы көмегімен сипаттауға болады. Төмендегідей :
,
, , ,
3.3-шi сурет инциденттiктiң қарым-қатынасының графы көрсетілген.
Сонымен, әлгi графта әкелiнген мысалдан және жиын үлестері ретiнде алуға болады . Сонымен бiрге, бұл графтың анықтамасында және үлеске "табиғи" бөлiктеу салынып қойылған. Қосымшада пайда болатын қос жарнақты графтар осылай берілген -көптеген төбелермен, бастапқы екi бөлiк тұратын және көптеген қабырғалармен, әрқайсысы әртүрлi бөлiктерден тұратын төбелерді біріктіреді.
Егер үлестерге бөлiктеу берiлмеген болса, онда сұрақ туындайды осы граф қос жарнақты ма?деген. Егер графта төбе болса, онда екi iшкi жиындағы көптеген төбелердiң бөлiктеулерi болады және бұл барлық бөлiктеудің тiкелей тексерiсі өте сыйымды iс болады. Келесi теорема қос жарнақтылықтың белгiсiн бередi, ал оның дәләлдеуінен қос жарнақтылықтың тиiмдi алгоритм тексерiсiн алып шығуға да болады . Мұндай алгоритм толық келесi дәрiсте сипатталады.
5-шi теорема. граф үшiн келесi бекiтулер тең дәрежеде:
• (1 ) - қос жарнақты граф
• (2 ) -де тақ ұзындықтың циклі жоқ
• (3 ) -де тақ ұзындықтың қарапайым циклі жоқ.
Ең көп тәуелсiз жиынды iздеуді рационализациялау.
Суреттелген түпкілікті іздеу стратегиясын қолдануда артықтықты қысқартудың түрлі тәсілдері бар. Олардың бірі келесі зерттеуге негізделген. Ең көп тәуелсiз жиынын табу қажет графында екі және төбелері бар, олардың әр төбесі -дан ажыраған және -ға шектес болғанда, төбесімен де шектес болады. Басқаша айтқанда, . Олай болса төбесі төбесін жабады (сіңіреді, жұтады). Егерекі және төбелері шектес болса, төбесі төбесін шектесе жабады. Бұл жағдайда төбесін шектесе жабушы төбе дейміз. Мәселен 11.1. суреті көрсетілген графта 2 –төбе 1-ші және 3-төбені шектесе жабады. Осы графтағы 5-ші және 6-төбелер де шектесе жабатын төбелер болып табылады.
Сурет. 11.1.1-теорема. Егер төбесі графындағы шектесе жабушы төбе болса,
онда .