АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Байланысты графтар

Анықтама. және () төбелері байланысты деп аталады, егер осы төбелерді байланыстыратын бағыт(жол) табылса. Кері жағдайда байланыссыз деп аталады..

Кез келген төбе өз-өзімен байланысты болады.

Анықтама. Кез келген төбелер жұбы байланысты болатын графты байланысты граф деп атайды. Кері жағдайда граф байланыссыз болады. Ал оның максимал байланысты болатын ішкі графтарын графтың байланыс компоненталары деп атайды.

Теорема. Егер графтың тура екі төбесінің дәрежелері тақ болса, онда олар байланысты болады.

Есеп. Газетте пәтерлер айырбастау туралы 21 хабарлау бар. Олардың әрбіреуінің 10-нан кем емес тұрғындармен айырбастауы мүмкін екені белгілі. Кез келген екі тұрғыны өзара пәтерлерді айырбастайтындығын дәлелдеу керек.

Бұл есепті жалпылап, графтар теориясының тілінде жазайық.

Теорема. Егер графтың төбесінің минимал дәрежесі болса,онда байланысты граф болады.

Есеп. Мемлекетте қала бар. Кез келген екі қаланың арасында ұшақ немесе поезд қатынасады (екі көліктің біреуі). Көліктің біреуімен бір қаладан екінші қалаға баруға болатынын дәлелде.

Бұл сөйлемнің әділеттілігі келесі теоремадан шығады.

Теорема. Егер графы байланыссыз болса, онда оның толықтауышы графы байланысты болады, және оның кез келген екі төбесінің ұзындығы екіден аспайтын тізбегімен байланысты.

Теорема. төбелік байланысты графтың қабырғаларының ең кіші саны тең.

Есеп. Жергілікті аймақта тұрғындардың саны -ға тең. жұптар бір-бірімен таныс. Біреуіне айтылған кез келген жаңалықтың барлығына да мәлім болатынын дәлелдеу керек. Егер жаңалықты естіген әрбіреуі, оны өз таныстарына жайатын болса. Бұл есепті шешу үшін келесі сөйлемді дәлелдеу жеткілікті.

Теорема. төбелі байланыссыз графтың қабырғаларының ең үлкен саны тең.

Ағаштар. Орман.

Анықтама. Циклы жоқ байланысты графты ағаш дейміз.

Ағаштармен байланысты есептерді шығару үшін келесі тұжырымдарды қолданамыз.

Теорема. төбесі және қабырғасы бар графы үшін келесі тұжырымдар эквивалентті болады:

1) - ағаш;

2) - графтың қабырғаларының ең кіші санымен, төбесімен байланысты граф;

3) - байланысты графжәне ;

4) - байланысты граф,толық емес, бірақ кез келген қабырғаны қосқан сайын бір цикл пайда болады;

5) - байланысты граф, кез келген қабырғаны алып тастағанда екі байланыс компонентасы пайда болады;

6) - кез келген екі төбесі жалғыз жай тізбекпен байланысқан граф;

7) - графтың циклдары жоқ, бірақ кез келген қабырғаны қосқан сайын цикл пайда болады.

Теорема. Кез келген ағаштың кем дегенде екі аспалы төбесі болады және олардың саны -ден аспайды. Мұндағы - ағаштың төбелерінің саны.

Анықтама. Әрбір байланыс компонентасы ағаш болатын графты орман дейміз.

Теорема. Егер төбелік орманның қабырғасы болса, онда ормандағы ағаштар саны k -ға тең болады.

ДС 3. Екі бөлікті графтар. Эйлер графтар

Анықтама. графы екі бөлікті деп аталады, егер оның төбелер жиынын және бөліктерге бөлінетіндей бөлінуі табылса, және бұл графтың кез келген қабырғасы екі әр түрлі бөліктерінің төбелерін қосады.

Анықтама. Егер екі бөлікті графті әр түрлі кез келген төбелер жұбы сыбайлас болса, онда екі бөлікті толық граф деп аталады, және толық деп белгіленеді, мұндағы - бөліктегі төбелер саны.

Екі бөлікті графтарды анықтаған кезде проблема пайда болады. Бұл проблема Бұл проблеманы Д. Кёнигом математигі 1936 жылы шешті.

Теорема (Кёниг) 1. Граф екі бөлікті болу үшін, оның ішінде тақ ұзындықты циклдары болмайтыны қажетті және жеткілікті.

Теореманы қолдану мысалы ретінде келесі есепті қарастыруға болады.

Дата добавления: 2015-09-27 | Просмотры: 1325 | Нарушение авторских прав