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

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

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

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

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

2-сурет

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

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

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

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

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

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

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

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