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

1. 
   Граф анықтамасы
   
2. 
   Графтың инциденттік матрицасы дегеніміз не?
   
3. 
   Граф түрлерін атаңыз
   
4. 
   Бөлектенген қыр дегеніміз не?
   
5. 
   Аяқталған қыр дегеніміз не?
   
6. 
   Ілмек дегеніміз не?
   

1. 
   Цикломатиялық сан
   
2. 
   Гамильтон графы
   

1. 
   Цикломатиялық сан
   

Графтың барлық төбелері арқылы өтетін элементарлық жол гамильтондық жол деп аталады да, егер оның басы және соңы бірігіп кетсе, онда оны гамильтондық цикл деп атайды. Белгілі коммивояжер жөніндегі есеп былай тұжырымдалады:

Қосарланған қашықтағы белгілі n қалалар бар. Коммивояжер барлық қалаларға келгендегі жолдың ұзындығының қосындысы өте аз (минималды) болатынды табу керек. Бұл дегеніміз оң сандар жазылған қырлардың ұзындығы n k толық графтағы гамильтон жолының ең аз ұзындығын табу (есептің варианты үшін – айналып шығу арқылы қайтадан бастапқы жолға келу – минималды гамильтондық циклді табу).

G_n граф төбесінің n ! алмастыруға сәйкестенетін, ал қыры екі төбені қосатын көрші элементтерінің өзгешелігі транспозициясында болатын (әрбір төбе n-1 басқа төбелермен қосатын){1,2,…,n} құралған жиынын қарастырамыз.

Сонда көрсетілген тізбек G_n графындағы жолына сәйкес келеді 2.8 а - суретте n =3 кескіні көрсетілген кезкелген графтың екі жұп бөліктерінің қосындысыда жұп граф бөлігі болады.

Егер S₁ және S ₂ H₁ және H ₂ граф бөліктерінің кейбір төбенің дәрежелері болса, ал S₁₂ H₁ ∩H₂ қиылысуындағы оның дәрежесі болса, онда граф бөлігінің δ төбесіндегі S(δ) дәрежесі

S₁ және S₂ жұп болғандықтан S(α) да жұп. Сондықтан жұп граф бөліктері кеңістіктегі барлық граф бөліктерінің кеңістік бөліктерін құрайды, да ілінген элементарлық циклдердің жиыны кеңістік бөлігімен бірігіп кетеді. Осы кеңістік бөліктерінің V - өлшемін анықтаймыз. P қырлардан және b төбелерден тұратын G байланысты граф берілсін. D– оның кейбір тұлғасы. (α,β) – хорда саны. (α,β) әрбір хорда [α,β] D бір элементарлық тізбегімен бірге элементарлық цикл құрайды, бірақ осы циклдердің векторы (әртүрлі хорда үшін) байланыссыз жүйе құрайды, циклдердің әрбіреуі жүйенің қалған циклдерінің ешбіреуінде жатпайтын қырды ұстайды. Басқаша айтқанда, әрбір жұп граф бөлігі, кез келген жай цикл S жүйенің циклі арқылы өрнектеледі. Шынында, H жұп граф бөлігіне S жүйенің циклдерінің H -қа кіретін граф хордасын қосамыз. Алынған қосынды ешқандай хорданы ұстамайды (әрбір хорда қосындыға екі рет кіреді: H граф бөлігі және жүйенің циклдерінің біреуі ретінде) D ағашының кейбір граф бөлігі ретінде. Осыдан құр граф бөлігі, сол себепті қарсы жағдайда жұп граф бөлігі шығар еді (H және циклдерінің қосындысы), D ағашында тұратын элементарлық циклдер. Сондықтан компоненттерімен байланысты базис кеңістігіндегі жұп граф бөліктерінің байланыссыз графы үшін оның байланысты компоненттерінің бірігуімен алынады да, ал қырлары мен төбелерінің сандары қосылады. Сондықтан, егер i -ші компоненттің қыры P_i және b_i төбесі болса, онда

Ағаштар байланысты графтар, оның цикломатиялық саны V=0 .

2-сурет

Теорема. Егер n (і 3) шыңдары бар қарапайым графикте әрбір шыңның жергілікті дәрежесі кемінде болса, онда график Гамильтон болып табылады.