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

Жоспар

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

3. Қорытынды.
Әдебиеттер тізімі

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 9 бет
Таңдаулыға:

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

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

1. Графтар теориясы - жас ғылым (айталық, геометриямен салыстырғанда). 1736 жылы Санкт-Петербург ғылым академиясында Леонард Эйлердің еңбегі жарық көрді, онда кенигсберг көпірі туралы есеп қарастырылды ("Барлық қала көпірлерінен тек бір реттен өтіп, бастапқы нүктеге қайта оралу мүмкін бе?"). Бұл болашақ графтар теориясы бойынша бірінші жұмыс еді. Бұл - күрделі объектінің байланысы мен қасиеттерін көрсететін, күрделі, сызықты емес көпбайланысты динамикалық структура.
Көпбайланысты структураның қасиеттері:
1. Әрбір элементке (түйін, төбе) саны еркін алынған сілтемелер болуы мүмкін.
2. Әрбір элемент кез келген басқа элементпен кез келген рет байланысады.
3. Әрбір байланыстырушы жасаушының (қабырға, доға) бағыты және салмағы болады. Келесі қасиеттері бар графтарды ағаштар дейді:
- Басқа ешбір элемент сілтемейтін жалғыз элементі (түйін, төбе) бар болса және ол түбір деп аталады.
- Түбірден бастап элементтерде бар белгілі бір көрсеткіштер тізбегі бойымен структураның басқа кез келген элементіне қатынас жасауға болса.
- Түбірден басқа әрбір элементке тек бір ғана сілтеме жасалса, яғни әрбір элементтің жалғыз адресі болса.
2. Граф деп - бейнеленген заттардың екі - екіден жұпталып келген заттардың бір - бірімен қатынасының жүйесін айтады. Графтармен коммуникация жолдарын қолайлы бейнелейді, үздіксіз емес көп қадамды процестерде (бинарлық қатынастардың жүйелерін, химиялық формулалардың
құрылымында, тағы басқа әр түрлі схемалардың диаграммаларында) қолданылады.
Төбелері бірде - бір қырымен инциндентті болмаса, онда ондай қырды бөлектенген қыр деп атаймыз, ал төбесі бір қырымен инциндентті болса, онда оны аяқталған қыр, не ілінген қыр деп атаймыз. Қырдың басы мен соңы біріккен болса, оны ілмек деп атаймыз. Егер екі төбе бір қырға инциндентті болса, ондай төбелерді көршілес, не сыбайлас төбелер деп атайды. Егер екі қыр бір төбеге инциндентті болса, онда ондай қырды сыбайлас деп атаймыз. Қырға сәйкес қойылған екі төбені еселік, не параллель төбелер деп атаймыз.Әртүрлі есептер үшін бір тек сол затқа графтың әртүрлі салыстыруы қажет. Мысалы: жолдар тармағының үзіндісі ретсіз қырмен көрсетіледі де, бір - бірімен қатынастарының аяқталуын бейнелейді (қоныстанған орындарымен, қала көшелерімен, көшенің түйіскен жерімен құралдарындағы бір жақты, не екі жақты қозғалыстар). Бірнеше доғаларымен бөлектеген әрбір бірнеше қозғалысты - қырға қосымша жазылған сандар, оның ұзындығын, енін, епкіштігін және сандар не басқа сипаттамасын көрсетеді.
Қандай графтар ажыратылатын және ажыратылмайтын болып бөлінуін анықтау өте қажет болып табылады, оны тіпті графтардың изоморфизм ұғымымен байланыстырады. Егер инцинденттіктен пайда болған матрица бір мағынада беретін болса, онда матрицаның көршілес төбелері графтың кез - келген бағытсыз қырын қарама - қарсы бағытталған доғалармен сол төбелер сақталып өзгертілуі көрсетіледі. Бірақ графтың үлессіз қырлары үшін графтың берілуі бір мағынада осы матрицамен анықталады да көршілес матрицаның элементі мұндай жағдайда 0 не 1 тең болады. Көрнекілік үшін көрсетуге болады: төбелерге кеңістікте (жазықтықта) әртүрлі бөлінген нүктелер сәйкес келеді де, қырларыныың соңы емес, бөлінген нүктелерден өтпейтін қисық сызықтың кесінділері сәйкес нүктелерге байланыстырады. Графтың төбелерімен қырларының инцинденттілік қатынасына бөлінген нүктелер мен сызықтары бар геометрикалық инцинденттілік сәйкес келеді. Одан басқа ішкі нүктеде қос - қостан қиылыспайды. Графтың мұндай көрінісі орындау (жүзеге асыру) деп аталады.
Мынаны көрсетуге болады, кез - келген шекті (типті саналатын) саны бар
элементтерден тұратын графтік үштік кеңістікте орындалуы, мүмкіндік жағдайда, егер графтың еселік қабырғалары болмаса, онда қырға түзудің кеңістіктері арқылы орындату қажетті.
Тегіс емес графты жазықтықта бейнелеу өте қолайлы, суретте төбелерді оның қырларының қиылысуын ажырата білу керек (мысалы төбелерді дөңгелектермен бейнелейді) қырлардың бағытын стрелкамен көрсетеді. Егер графпен көшенің жолдарының тармақтарын көрсетсе, мұнда көршілес төбелерді байланыстыратын жолдарын кесіндімен бейнелеу көрсетіледі. Алаң және көшенің түйіскен жері - тарап кішкентай ел мекендеген жерлерге графтың тегіс болуы мүмкін, бірақта қала үшін жол өтпелерде, көшелерде транспортардың шешімінде әр деңгейде тегіс граф қолданылады.
2.Эйлер графы
Графта ешбір қыр қалғанша бұл графтың кейбір элементарлық циклге қайта бөлінуі мүмкін. Сонымен, әрбір шекті жұп циклды екені шығады. Егер шекті жұп граф байланысты болса, онда (оның элементарлық циклдерінің саны бойынша және өзіне қиылысатын қыры бойынша) графтың барлық қырларын ұстайтын жай цикл болады. Бұл циклді Эйлер циклі деп атайды, ал оған иелі графты Эйлердің графы деп атайды. Жай циклдің әрбір төбесінде жұп дәреже болады. Онда төмендегі теорема дәлелденеді.
Теорема. Егер шекті байланысты граф Эйлердің графы болу үшін оның жұп болуы қажетті және жеткілікті. Эйлер графының байланысты барлық компоненті шектелген байланыспайтын жұп графында болады. Егер төбеге кіретін доғалардың саны шығатын доғалардың санына тең болса , онда бағытты графтың төбесін тең дәрежелі деп аталады.
Егер графтың барлық төбелері тең дәрежелі болса, онда оны теңдәрежелі граф деп атайды. Эйлердің бағытсыз графының Эйлердің циклі бойынша айналып шығуы графтың әрбір қырын айналып шығуына бағыттайды. Мұндай
бағытауда Эйлердің графы тең дәрежелі болады. Енді тең дәрежелі граф берілсін. Бұрынғы пікірді қайталасақ (циклдердің орнына контурлар жөнінде айтсақ) онда әрбір тең дәрежелі графты қырлары бойынша қосарланып қилыспайтын элементарлық нұсқалардың қосындысы ретінде көрінуі мүмкін (онымен қоса шекті тең дәрежелі графта графтың барлық қырларын ұстайтын жай нұсқа болады). Басқа сөзбен айтқанда Эйлер теоремасы мынаны танытады: граф төбелерінің барлығының жұп болуы әрбір қыры бір рет жүретін графты айналып шыққанға қажетті және
жеткілікті шарт болып табылады.
Жазық графтар
G графы деп V(G) шектеулі төбелер жиыны мен R(G) шектеулі қабырғалар жиыны аталады және әрбір қабырғасының ұштары әртүрлі екі төбе болады. Егер граф төбелері жазықтық нүктелері болса, ал қабырғалары осы жазықтықта сынық сызықтар (кесінділерден құралған) болса, онда граф жазық деп аталады.
Және жазық граф қабырғаларының ұштары өзара қиылыспайтын, басқа өбелерді енгізбейтін ұштармен шектеледі. Жазық графта ілгектер (басы мен ұшы бір төбе болатын қабырғалар) болмауы керек. Жазық граф жазықтықты D(G) қамтылмайтын көпбұрышты облыстар жиынына бөліктейді, облыстардың шектеулі болуы міндет емес. Егер қолданылған түстерді 1, 2, ..., n деп нөмірлесек, картаға сәйкес жазық графта осы сандармен төбелер (астаналар) нөмірленеді. Графтарды бояу есебі G жазық графының дұрыс n-түсті боялуы деп : V(G) {1,2,...,n} бейнесі аталады және егер оның шекарасы 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 = 3D(G)
аламыз, осыдан 2R(G) 3D(G) .Эйлер формуласынан V (G)-2 + D(G) =R(G), осыдан 3 R(G) =3V(G)-6+3 D(G) 3V(G)-6+2R(G) және R(G) 3V (G)-6 (1) шығарылады. Екі еселенген қабырғалар санын басқа да граф сипаттамасымен теңдестіруге болады. ... , n=V(G) граф төбелерінің толық жиынтығы болсын, ал M( ) - j нөмірлі төбеге жинақталаты қабырғалар саны. Бірақ әр қабырға екі төбемен шектеледі, сондықтан 2R(G)=M( ) +M( )+ ... +M( ). Сонымен қатар, (1) теңсіздігінен шығарылатындай, 2 R(G) 6V(G)-12.Ендеше, M( 1) + M( ) +...+ M 6V (G)-12 (2) Соңғы теңсіздіктен бестен артық емес қабырға жинақталатын, ең болмаса, бір төбе болатыны тұжырымдалады. Шынымен, қарсы тұжырымды
қабылдайық, яғни j M( ) 6 болсын. Онда M( )+M( )+...+M( ) 6n = 6V(G), бұл (2)-ге қайшы болады.Төбелерді төбесіне бестен артық емес қабырға жинақталатындай етіп, қайта нөмірлейік. Егер төбесінде төрттен артық емес қабырға жинақталса, онда G \графын қарастырамыз, ол G -дан төбесін және төбеге тірелетін қабырғалардың бәрін аластаудан алынады. G\ графы индукция болжамымен дұрыс 5 ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.