Дәріс №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 .

Гамильтон Уильям Роуэн (1805-1865), ирландиялық математик, 1837 жылдан бастап Санкт-Петербург Ғылым академиясының шетелдік корреспондент-мүшесі, 1859 жылы "додекаэдрге саяхат"атты жұмбақ ойлап тапты. Додекаэдр-бұл үш өлшемді фигура, барлық қырлары тұрақты бесбұрыштар болатын көпбұрыш. Додекаэдрде 12 бет, 20 шың және 30 шеттер бар. Гамильтон әр шыңға сол кездегі ең ірі қалалардың бірінің атауын берді: Брюссель, Дели, Франкфурт және т. б. Міндет-қала қабырғаларынан қалаға өту, барлық қалаларды айналып өту, олардың әрқайсысында бір-бірден болу және бастапқы қалаға оралу. Додекаэдрдің барлық шыңдарына тырнақтар соғылды, сондықтан әр жолды жоғарыдан жоғарыға қарай созылған жіппен белгілеуге болады. Ойын ретінде пазл өте іш пыстырды, сондықтан Гамильтон үлкен додекаэдр тиісті графикке(2-сурет) ауыстырғаннан кейін де кең таралмады Бірақ математиктер жұмбаққа қызығушылық танытты және графиктің әр шыңын бір рет қамтитын кез – келген цикл Гамильтон сызығы (Гамильтон циклі), ал Гамильтон сызығы бар график Гамильтон графигі деп аталды. Жабық Гамильтон сызығын жасау үшін графиктің шыңдарын қалай нөмірлеу керектігі көрсетілген Гамильтон циклінің мысалы келтірілген (2-сурет).

2-сурет

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