Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану



бет16/30
Дата23.12.2021
өлшемі0,66 Mb.
#127967
1   ...   12   13   14   15   16   17   18   19   ...   30
Байланысты:
darismatlogidm

1тұжырымдама. Ағаштың кез келген екі төбесін бір ғана тізбек (жай тізбек)  байланыстырады.

2тұжырымдама. Ағаштың доғаларының саны төбелер санынан бір мәнге кем.

3-тұжырымдама. Мысалға,Gағаш болсын. Онда  G  графының  кез келген 

тізбегі жай тізбек болады.



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

Анықтама. Қисындары, компонеттері ағаш болып табылатын граф орман деп аталады.

Әр түрлі ағаштардың ішінен екі маңызды жағдайды бөліп көрсетуге болады: қарапайым тізбекті құрайтын тізбекті ағаш және жұлдызды ағаш (немесе бұта), бұл жағдай төбелердің бірі (ортасы) басқа барлық төбелермен шектеседі.

V жиыны n төбелерден тұрсын. Осы төбелерді цикл бомайтындай етіп қабырғалармен байланыстырсақ,осы тө-белер жиының жабатын ағаш аламыз. Екі төбе үшін бір ғана ағаш болады – сол төбелердің өзі және оларды байланыстыратын қабырға. n мәнінің өзгеруімен байланысты tnәр түрлі ағаштар саны тез өседі: tn = nn-2.

 

2-сурет


 

Егер ағаштар изоморфты емес болса,  онда ол ағаштар айтарлықтай әр түр-лі деп саналады. Төрт төбелі 16 ғана ағаш бар, олардың ішінде айтарлықтай әр түрлісі тек2;ал алты бөбесі бар ағаштар саны1296, олардың ішіндегі айтарлықтай

әр түрлі ағаштар саны 6. 

Бірақ n=20 болған жағдайда әр түрлі ағаштар саны миллионға жуық болады.

2-суретте төрт және алты төбелі айтарлықтай әр түрлі ағаштардың мысал-дары келтірілген.

n-ші дәрежедегі графтар ішіндегі (n төбелермен) қатарлы қабырғалары

 жоқ граф ең аз қабырғаға ие, ал ағашы – ең кіші болып табылады. Ағаш

 минималды қабырғаға ие бола алады, ол үшін граф орамды болуы жеткілікті.



Теорема 1.  Әр n төбелі ағаш n-1 қабырғаға ие болады.

Расында да, екі төбе бір қабырға арқылы байланысады, сол төбелердің біреуін жаңа қосылған төбемен байланыстыру үшін тағы бір жаңа қабырға қажет. Ал егер екі қабырға қосатын болсақ, яғни жаңа төбені алғашқы екі төбенінің екеуімен де байланыстырсақ, онда міндетті түрде цикл пайда болады. Сәйкесінше, п төбелердің минималды орамдылығы үшін n-1 қабырға қажетті және жеткілікті.





Достарыңызбен бөлісу:
1   ...   12   13   14   15   16   17   18   19   ...   30




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет