Графтар мен ағаштар

Жоспар
1.Кіріспе.
2.Негізгі бөлім:
а) Графтар,негізгі анықтамалары,түрлері;
б) Ағаштар, олардың қасиеттері;

3. Қорытынды.
Әдебиеттер тізімі
        
        Графтар мен ағаштар.
Жоспар
1.Кіріспе.
2.Негізгі бөлім:
а) Графтар,негізгі анықтамалары,түрлері;
б) Ағаштар, олардың қасиеттері;
3. Қорытынды.
1. Графтар теориясы - жас ғылым ... ... ... 1736 жылы Санкт-Петербург ғылым академиясында Леонард Эйлердің еңбегі жарық көрді, онда ... ... ... есеп ... ... қала ... тек бір реттен өтіп, бастапқы нүктеге қайта оралу мүмкін бе?"). Бұл ... ... ... ... ... ... еді. Бұл - ... объектінің байланысы мен қасиеттерін көрсететін, күрделі, ... емес ... ... ... ... ... ... Әрбір элементке (түйін, төбе) саны еркін алынған сілтемелер болуы мүмкін.
2. Әрбір элемент кез ... ... ... кез ... рет байланысады.
3. Әрбір байланыстырушы жасаушының (қабырға, доға) бағыты және салмағы ... ... ... бар ... ... дейді:
- Басқа ешбір элемент сілтемейтін жалғыз элементі (түйін, төбе) бар болса және ол ... деп ... ... бастап элементтерде бар белгілі бір көрсеткіштер тізбегі ... ... ... кез ... ... қатынас жасауға болса.
- Түбірден басқа әрбір элементке тек бір ғана сілтеме ... яғни ... ... ... ... ... Граф деп - бейнеленген заттардың екі - екіден жұпталып ... ... бір - ... ... ... ... Графтармен коммуникация жолдарын қолайлы бейнелейді, үздіксіз емес көп ... ... () ... ... - бір ... ... болмаса, онда ондай қырды бөлектенген қыр деп атаймыз, ал төбесі бір ... ... ... онда оны ... қыр, не ... қыр деп ... ... басы мен соңы біріккен болса, оны ілмек деп атаймыз. Егер екі төбе бір қырға инциндентті болса, ... ... ... не ... ... деп ... Егер екі қыр бір төбеге инциндентті болса, онда ондай қырды сыбайлас деп атаймыз. Қырға сәйкес қойылған екі төбені ... не ... ... деп ... ... үшін бір тек сол затқа графтың әртүрлі салыстыруы қажет. Мысалы: жолдар тармағының үзіндісі ретсіз қырмен көрсетіледі де, бір - ... ... ... ... ... ... қала көшелерімен, көшенің түйіскен жерімен құралдарындағы бір жақты, не екі ... ... ... ... ... ... бірнеше қозғалысты - қырға қосымша жазылған сандар, оның ұзындығын, енін, епкіштігін және сандар не ... ... ... ... ... және ... болып бөлінуін анықтау өте қажет болып табылады, оны ... ... ... ... ... Егер ... ... болған матрица бір мағынада беретін болса, онда матрицаның көршілес төбелері графтың кез - ... ... ... қарама - қарсы бағытталған доғалармен сол төбелер сақталып өзгертілуі көрсетіледі. Бірақ графтың үлессіз қырлары үшін графтың ... бір ... осы ... ... да ... ... элементі мұндай жағдайда 0 не 1 тең болады. Көрнекілік үшін көрсетуге болады: төбелерге кеңістікте (жазықтықта) әртүрлі бөлінген нүктелер сәйкес ... де, ... соңы ... ... ... өтпейтін қисық сызықтың кесінділері сәйкес нүктелерге байланыстырады. Графтың төбелерімен қырларының инцинденттілік қатынасына бөлінген нүктелер мен сызықтары бар геометрикалық ... ... ... Одан ... ішкі ... қос - ... ... Графтың мұндай көрінісі орындау (жүзеге асыру) деп аталады.
Мынаны көрсетуге болады, кез - ... ... ... ... саны ... ... ... үштік кеңістікте орындалуы, мүмкіндік жағдайда, егер графтың еселік қабырғалары болмаса, онда қырға түзудің кеңістіктері арқылы орындату қажетті.
Тегіс емес графты ... ... өте ... ... ... оның ... ... ажырата білу керек (мысалы төбелерді дөңгелектермен бейнелейді) қырлардың бағытын стрелкамен көрсетеді. Егер графпен көшенің жолдарының тармақтарын көрсетсе, мұнда көршілес төбелерді ... ... ... ... ... Алаң және ... түйіскен жері - тарап кішкентай ел мекендеген жерлерге графтың тегіс болуы мүмкін, бірақта қала үшін жол өтпелерде, ... ... ... әр деңгейде тегіс граф қолданылады.
2.Эйлер графы
Графта ешбір қыр қалғанша бұл графтың кейбір элементарлық циклге ... ... ... ... ... шекті жұп циклды екені шығады. Егер шекті жұп граф ... ... онда ... ... ... саны ... және өзіне қиылысатын қыры бойынша) графтың барлық қырларын ұстайтын жай цикл болады. Бұл циклді Эйлер циклі деп ... ал оған иелі ... ... ... деп ... Жай циклдің әрбір төбесінде жұп дәреже болады. Онда төмендегі теорема дәлелденеді.
Теорема. Егер шекті байланысты граф ... ... болу үшін оның жұп ... ... және жеткілікті. Эйлер графының байланысты барлық компоненті шектелген байланыспайтын жұп графында болады. Егер төбеге кіретін доғалардың саны шығатын доғалардың санына тең ... , онда ... ... ... тең ... деп ... ... барлық төбелері тең дәрежелі болса, онда оны теңдәрежелі граф деп атайды. Эйлердің бағытсыз графының Эйлердің циклі бойынша айналып шығуы ... ... ... ... ... бағыттайды. Мұндай
бағытауда Эйлердің графы тең дәрежелі болады. Енді тең дәрежелі граф ... ... ... ... ... ... контурлар жөнінде айтсақ) онда әрбір тең дәрежелі графты қырлары бойынша қосарланып қилыспайтын элементарлық нұсқалардың ... ... ... ... ... қоса ... тең ... графта графтың барлық қырларын ұстайтын жай нұсқа болады). Басқа ... ... ... теоремасы мынаны танытады: граф төбелерінің барлығының жұп болуы әрбір қыры бір рет ... ... ... шыққанға қажетті және
жеткілікті шарт болып табылады.
Жазық графтар
G графы деп V(G) шектеулі төбелер жиыны мен R(G) шектеулі қабырғалар жиыны ... және ... ... ... ... екі төбе ... Егер граф төбелері жазықтық нүктелері болса, ал қабырғалары осы жазықтықта сынық сызықтар (кесінділерден құралған) ... онда граф ... деп ... ... граф қабырғаларының ұштары өзара қиылыспайтын, басқа өбелерді енгізбейтін ... ... ... ... ілгектер (басы мен ұшы бір төбе болатын қабырғалар) болмауы керек. Жазық граф жазықтықты D(G) ... ... ... ... ... облыстардың шектеулі болуы міндет емес. Егер қолданылған түстерді 1, 2, ..., n деп нөмірлесек, картаға сәйкес ... ... осы ... төбелер (астаналар) нөмірленеді. Графтарды бояу есебі G ... ... ... ... ... деп : V(G) ... бейнесі аталады және егер оның шекарасы v1 мен v2 ... r R(G) ... бар ... (v1) (v2 ) ... орындалады. Сонымен, төрт бояу проблемасын келесі тұжырым түрінде қорытындылаймыз.
1-теорема. Кез ... ... граф ... 4 ... ... ұйғарады. Осы проблеманы шешу мәселесіне жүз жылдан астам уақыт жұмсалды. Бірақ бір ... ... ... ... ... 5 түсті бояу туралы тұжырым оңай дәлелденеді. Дәлелдеуге төбелер, қабырғалар және облыстар санын байланыстыратын ... ... ... ... M ... жиыны элементтерінің санын білдірсін. Эйлер теоремасы. Кез келген жазық граф үшін |V(G) |+| D(G)|= 2 + |R(G)| .
2- ... Кез ... ... граф 5 ... бояуды ұйғарады. Дәлелдеуі. Алдымен ... ... Егер ... ... жұбын біріктіретін бірнеше қабырғалар бар болса (бұндай жағдай екі елдің бірнеше өзара байланыспайтын шекара тілімдері бар болғанда туындайды, мысалы ... мен ... ... онда тек бір ... ... ... ... графты дұрыс түстеп бояу, ізделінген түстеп бояудың дұрысболуына кепілдік береді. Граф төбелері санымен индукция жүргіземіз. Үш төбесі бар граф үшін ... ... ... ... Бұл тұжырым n-1 төбелі барлық графтар үшін әділ. D1,D2,...,Dm - түгел m =D(G) граф облыстарының толық ... ... ал N(Di ) - ... i - інші облысының шекарасын құратын
қабырғалар саны. Сонымен қатар кез келген i үшін N(D) >3. Кез ... ... ... ... ... ... N(D1) + N(D2 ) +...+ N(Dm) = 2R(G) .
N(Di ) 3 теңсіздігінен 2R(G) = N(D1) + N(D2 ) +...+ N(Dm) 3m = ... ... 2R(G) 3D(G) ... формуласынан |V (G)|-2 + |D(G) |=|R(G)|, осыдан 3| R(G)| =3|V(G)|-6+3 |D(G)| 3|V(G)|-6+2|R(G)| және |R(G)| 3|V (G)|-6 (1) ... Екі ... ... ... басқа да граф сипаттамасымен теңдестіруге болады. ... , n=V(G) граф төбелерінің толық жиынтығы болсын, ал M( ) - j ... ... ... ... ... ... әр қабырға екі төбемен шектеледі, сондықтан 2R(G)=M( ) +M( )+ ... +M( ). ... ... (1) ... шығарылатындай, 2| R(G)| 6|V(G)|-12.Ендеше, M( 1) + M( ) +...+ M 6|V (G)|-12 (2) ... ... ... ... емес ... ... ең ... бір төбе болатыны тұжырымдалады. Шынымен, қарсы тұжырымды
қабылдайық, яғни j M( ) 6 болсын. Онда M( )+M( )+...+M( ) 6n = 6|V(G)|, бұл (2)-ге ... ... ... ... артық емес қабырға жинақталатындай етіп, қайта нөмірлейік. Егер төбесінде төрттен артық емес қабырға жинақталса, онда G ... ... ол G -дан ... және ... ... ... ... аластаудан алынады. G\ графы индукция болжамымен дұрыс 5 түсті бояуды ұйғарады. Ал қабырғалар төбені кіші графтың төрт ... ... - ны ... ... бояу ... ең болмаса, бір түс қалады (бесеуден). Енді - ға бес ... ... Бес ... ... H G ... қарастырайық, оған - дан шығатын және біріктіретін (G-да) қабырғалар келеді. H графында міндетті түрде қабырғалармен біріктірілмейтін екі төбе табылады. Расында да ... ... H ... ... ... (оны ... қиын ... Бірақ (1)-ге сәйкес
|R(H)| 3|V(H)|-6= 3*5-6=9 сөйтіп, қайшылыққа тірелеміз. мен - H -тың ... ... ... болсын. Олар G \ графындада біріктірілмеген. G\ графынан өзгертілумен алынған графын қарастырайық, мен өзгерту нәтижесінде теңестірілген. Бұл жағдайда төбелерін теңестіргеннен ... ... ... G -жазық граф. Бірақ үшін индукция болжамы әділ болады және оған ... 5 ... бояу бар. Бұл ... ... мен ... ... Онда дұрыс 5 түсті бояуды G \ графы да алады, және оған теңдігі әділ ... ... ... мен ... ... боялған, ендеше төбесімен көршілес H графының бес төбесін түстеп бояуға төрттен артық емес түс қолданылады. Қалған түсті ... ... ... және G -дің ... 5 ... ... ... Бір қарағанда төрт бояу проблемасы математиканың басқа тарауларымен және іс жүзіндегі есептермен аз байланысатын ... ... ... ... көрінеді. Шындығында олай емес. Бұл проблеманың алгебра,статикалық механика және жоспарлау есептерімен байланыстыратын 20-дан астам тұжырымы бар. Бұл да ... тән ... таза ... ... есеп ... ... және ... бойынша мүлде әртүрлі болатын объектілер мен процестерді ... ... ... ... бояу ... ... туралы
К. Аппель мен У. Хакен дәлелдеуін математикалық қауымның
қабылдағанына қарамастан, осы уақытқа дейін белгілі бір күдік ... ... ... ... ... ... айтылған сөйлем, әрине, таңдандырады, себебі математикадағы үшінші тұжырым аластатылған: немесеәділ, немесе жоқ ... ... ... - ... ... ... ... Мәселе оңай емес. Дәлелдеу авторлары былай деп жазады: . Турасын айтқанда, дәлелдеудің компьютерлік бөлігін қолмен ... ... ... ал ... дәстүрлі бөлігі өте ұзақ және күрделілігі соншалық, оны толығымен ешкім тексермеген. Сонымен, тексеруге болмайтын дәлелдеу - ... ... ... ... ... ... ... Бірақ бұл арада да бәрі күрделірек. Ұзақ уақыт Евклид тұжырымдамалары мен дәлелдеулері математикалық қаталдық идеалы болып келген, оларда теоремаларды ... ... ... ... ... ... емес тұжырымдарды айқын тұжырымдардан алуға мүмкіндік беретін дедукция әдісі). Бұл қаталдық үлгісі қазіргі ... да ... ... ... қол жетпес үлгі, бірақ жаңа замандағы таза математикаға Евклид стандарттары жеткіліксіз. Евклид, жазықтықты түзу неге екі бөлікке бөлетіні ... ... ... ... ол нені ... деген түсінікті анықтамаған, бұл түсінік онсыз да айқын деп есептеген және т.б. Осындай тұжырымдардың үлкен бөлігі ... жүз ... ғана ... ... аксиоматикасына енгізілген. Жаңа аксиома жүйесінен формалды қорытындылар көне замандағы қорытындыларға
қарағанда өте ұзын орындалған.
Сонымен, төрт бояу теоремасын дәлелдеу мәселесі таза ... ашық ... қала ... ... графты ағаш дейміз. Басқаша айтқанда барлыққырлары ациклділік болатын графты ағаш дейміз. Төмендегі төрт шартты қанағаттандыратын графты ағаш дейміз:
1) ... ... алып ... ... граф ... ... ... саны төбелер санынан біреуі аз болатын байланысты граф.
3) Бір элементарлық тізбекте байланыста болатын граф.
4) Екі ... ... ... қосқаннан кейін пайда болған циклсіз граф.
Ағаштан кезкелген 0 төбені аламыз және оны тамыр , не ноль ... төбе ... ... ... 1-ші ... ... ... i 1 қабаттағы төбені i -ші қабаттағы төбе ... тағы сол ... ... әрбір төбе белгілі бір қабатқа жатады. Қабаттың номері ағаштағы төбелердің ара қашықтығы мен тамырына тура келеді. 3-ші қасиет бойыншы әрбір ... i -ші ... қыр ... i ... ... ... төбемен байланыста болады да, ешқандай i -ші қабаттағы төбемен ... ... ... осындай көрінісі өте қолайлы. Мұндай көрініс, аяқталған ағашта үнемі соңғы төбе болады. (мысалы ... ... ... ... ... ... D ... қарағанда граф бөлігінің барлық қырларын G / D-ді хорда дейміз. Әрбір хорда тұлғаның екі төбесін ... ... ... қыры кем ... бір элементарлық циклге жататын болса, онда ол ... ... ... қыр деп ... ал ... жағдайда ациклділік деп атайды: Ациклділікке мысал ретінде ілінген қырды келтіруге болады. Төменде екі пікір орындалады:
1)Байланысты графтан циклдік қырды шығарғанда, оның ... ... ... ... ... граф ... ... кезкелген тізбек үшін циклдік қырды циклдегі қалған қырлардың тізбегімен өзгертуге болады.
Екіншісі қарсы жолмен ... егер ... ... ... ... онда ... ... соңы элементарлық тізбекпен байланыста болар еді; алынған қырды ... ... онда ... цикл шығар еді, бұл мүмкін емес, себебі бұл қыр ациклді.
Циклсіз байланысқан графты ағаш ... ... ... ... ... ... болатын графты ағаш дейміз.
Төмендегі төрт шартты қанағаттандыратын графты ағаш дейміз:
1) Кезкелген қырды алып тастағанда байланысты граф байланыспайтын болады.
2) ... саны ... ... біреуі аз болатын байланысты граф.
3) Бір элементарлық тізбекте байланыста болатын ... Екі ... ... ... қосқаннан кейін пайда болған циклсіз граф.
2. Ағаштан кезкелген төбені аламыз және оны тамыр , не ноль қабаттағы төбе ... ... ... 1-ші қабаттағы төбе, көрші қабаттағы төбені -ші қабаттағы төбе дейміз, тағы сол сияқты.
Ағаштағы ... төбе ... бір ... ... Қабаттың номері ағаштағы төбелердің ара қашықтығы мен тамырына тура келеді. 3-ші қасиет бойыншы әрбір байланыс -ші қабаттағы қыр арқылы -ші ... ... ... ... ... да, ... -ші қабаттағы төбемен байланысты болмайды. Ағаштың осындай ... өте ... ... ... ... ... ... соңғы төбе болады. (мысалы ақырғы қабаттағы төбе, бірақ 2.5-сурет ... ... ... D ... бөлу оның ... ... ... реттелгенін анықтайдыда, егер және элементарлық тізбек тамырдан төбесінде -ні ... төбе ... ... ... осы ... ... болып табылады, мұнда осы әрбір ағаштың бөлігінде .2.6-сурет
Тамырды ағашында бөлу оның төбелерінің жиынында жартылай ... ... да, егер және ... ... ... төбесінде - ні ұстайды. Әрбір төбеде ағаштың тамырын анықтайды, осы төбелерге іліну болып ... ... . Осы ... ... ... . ... ағаштың бөліктері өзінің бұтақтарынан тамырына желімдеу арқылы пайда болады.
3. байланысты графта біртіндеп барлық циклді қырларды алып тастаймыз. ... ... ... бөлігі сол төбелердің жиынынан тұратын элементарлық циклсіз ағашқа ... ... ... ... бір ... емес ... да, бірақ ациклді қырлары кезкелген тұлғаға кіреді.
тұлғасына қарағанда граф бөлігінің барлық қырларын /-ді ... ... ... ... ... екі төбесін байланыстырады.
2.7-сурет
Кесте2.1
цикл
Шығарылған қыр
[1,9,14]
[6,7,10]
[5,13,14]
[4,12,13]
[8,11,12]
[2,9,14,4,3]
[14,10,11,4]
[16,17,18]
1
6
5
13
8
9
14
16
Қорытынды
Графтың барлық төбелері арқылы өтетін элементарлық жол ... жол деп ... да, егер оның басы және соңы ... ... онда оны ... цикл деп ... Белгілі коммивояжер жөніндегі есеп былай тұжырымдалады: Қосарланған қашықтағы белгілі n қалалар бар. ... ... ... ... жолдың ұзындығының қосындысы өте аз (минималды) болатынды табу керек. Бұл дегеніміз оң сандар жазылған қырлардың ұзындығы n k толық ... ... ... ең аз ... табу ... ... үшін - ... шығу арқылы қайтадан бастапқы жолға келу - минималды ... ... n G граф ... n ! алмастыруға сәйкестенетін, ал қыры екі төбені қосатын көрші ... ... ... ... (әрбір төбе n 1 басқа төбелермен қосатын) {1,2,...,n} құралған жиынын
қарастырамыз. Сонда көрсетілген тізбек n G ... ... ... келеді
Әдебиеттер тізімі:
1. Судоплатов С.В., Овчинников Е.В. Элементы дискретной математики.
Новосибирск.-НГТУ, 2002.
2. Романовский И.В. Дискретный анализ. СП., ... ... Б.Н. ... ... ... и программы. Москва,
2003.
4. Новиков Ф.А., Дискретная математика для программистов. Питер, 2001.
5. Нефедова В.Н., Осипова В.А. Курс дискретной математики. - ... ... ... А.И., ... С.Б. ... математика. - М.:МГТУ
им.Э.Баумана, 2001.
7. Яблонский С.В. ... в ... ... - М.: , ... ... ... Р., Кнут Д., ... О., Конкретная математика. М. 1998.
9. Мальцев А.И., ... и ... ... Гаврилов Г.П. Сборник задач по дискретной математике. М. 1977.

Пән: Информатика
Жұмыс түрі: Реферат
Көлемі: 8 бет
Бұл жұмыстың бағасы: 200 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
Графтар теориясы50 бет
Графтар теориясы және оның элементтері5 бет
Графтардағы Гамильтон циклы мен жолы17 бет
Графтардағы тиімділеу есептерін шешу әдістері15 бет
Жапырақты орман ағаштарының зиянкес жәндіктерінің түрлері және келтіретін зияны66 бет
Жеке ағаштар жиынтығының таксациясы7 бет
Графикалық торлар20 бет
Көрсеткіштік функция, оның қасиеттері және графигі4 бет
Туристік жорықтар, саяхат сұрақ-жауап түрінде51 бет
Ыбырай Алтынсарин қазақ педагогиксының негізін қалаушы7 бет


Исходниктер
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь