Графтар теориясының негізгі анықтамалары Қолдану мысалдары
жүктеу/скачать 291,42 Kb.
|
23-24 Графтар 1
- Бұл бет үшін навигация:
- Графтар теориясының негізгі анықтамалары Қолдану мысалдары
- Графтар теориясының негізгі анықтамалары Графтар (V, E)
- гамильтонды граф
|
Графтар теориясын білуді қажет ететін белгілі бір есептердің класы болады, мысалы, көлік есептері, желілерде ағындарды тиімдеу есептері, иерархиялық бұтақтар тәрізді құрылымдарда іздестестіру есептері, т.б. Бұтақтар (понятия дерева) мен графтар бір біріне ұқсас болып келеді. Графтар теориясының негізгі анықтамалары Қолдану мысалдары: Қала картасын бағытталған граф көмегімен модельдеуге болады. Қабырғалар - көше ұзындығын, бағыттар – қозғалыс бағытарын сипаттайды. Мәселелер: ең қысқа жолды табу, жолдын барын тексеру, кері қайту жолдарын тексеру. Компьютерлік желілер бағытталмаған граф көмегімен модельдеуге болады, төбелері – желі компьютерлеріне, қабырғалары компьютерлер арасындағы байланыс каналдарына сәйкес келеді. Типтік мәселелер: компьютерлер арасында байланыс мүмкіндігін тексеру, минималды байланыс ағашын іздестіру, Интернетте пакеттердің маршрутизациясы. Аймақтағы өзендер жүйесін бағытталған граф көмегімен модельдеуге болады. Ондағы әрбір өзен бір немесе бірнеше қабырғалардан тұрады. Әрбір тұйін – бір немесе бірнеше өзеннің басқа өзенге ағысын сипаттайды. Типтік мәселелер: әрбір төбе бойынша өтетін судың көлемін есептеу, су тасқынын болжау. Графтар теориясының негізгі анықтамалары Графтар (V, E) жұптар жиыны ретінде анықталады. мұнда V – төбелердің шекті жиыны; E – төбелерді байланыстыратын қабырғалардың шекті жиыны. S= 1) Бір қабырғамен байланысатын төбелер сыбайлас төбелер деп аталады. 2) S қабырғасы және U төбесі (және S қабырғасы мен W төбесі) түйісті (инцидентті) деп аталады. 3) Бір төбеге түйісті (инцидентті) қабырғалар сыбайлас қабырғалар деп аталады. 4) Төбенің дәрежесі оған түйісті (инцидентті) қабырғалардың санына тең. U және K төбелерін байланыстыратын жол – W0,W1, . . . , Wn (n>0), төбелерінің тізбегі, мұнда W0=U, Wn=K, кез келген i (0in-1) үшін Wi және Wi+1 төбелері қабырғалармен байланысқан. W0, . . . ,Wn жолының ұзындығы оның қабырғаларының санына – n тең. Егер жолдың барлық төбелері әртүрлі болса, онда ондай жол қарапайым жол деп аталады. Егер W0=Wn болса, онда ондай жол тұйық жол деп аталады. Барлық қабырғалары әр түрлі, тұйық жолды - цикл деп атайды. Барлық төбелері әр түрлі тұйық жолды контур деп атайды. Екі төбе арасындағы қашықтық – осы төбелерді байланыстыратын ең қысқа жолдың ұзындығы. Егер кез келген төбелер жұбын байланыстыратын жол бар болса, онда ондай граф байланысты граф деп аталады. Егер кез келген екі төбелер қабырғалар арқылы байланыстырылса, онда ондай граф толық граф деп аталады. Бағытталған граф немесе орграфтың қарапайым графтан айырмашылығы - төбелер, қабырғалармен емес, доғалармен (доға дегеніміз - бағыты берілген қабырға) байланысуы. Орграф бойымен орын ауыстыруды тек доға бағытымен ғана орындауға болады. Бір төбеден графтың кез келген төбесіне дейін жол бар болса, онда ондай төбені орграфтың көзі (источником) деп атайды. U төбесінің графтың қалған төбелеріне дейінгі ең үлкен қашықтық U төбесінің эксцентриситеті деп аталады. Төбелердің арасындағы ең үлкен эксцентриситетті графтың диаметрі деп атайды. Төбелердің арасындағы ең кіші эксцентриситетті графтың радиусы деп атайды. Эксцентриситеті графтың радиусына тең төбені графтың медианасы немесе оның центрлік төбесі деп атайды. Егер барлық төбелер (бірақ барлық қабырғалардың кіруі міндетті емес) циклге кіретін болса және осы цикл графта бар болатын болса, онда осы граф гамильтонды граф деп аталады. Егер графтың барлық қабырғалары циклге бір рет қана кіретін болса және осы цикл графта бар болатын болса, онда осы граф Эйлер графы деп аталады. Графтың барлық қабырғаларының бойымен тек бір рет қана жүріп өтетін жолды Эйлер жолы деп атайды. Графты сурет түріндегі қабылданған форма бойынша көрсетуге болады, онда төбелерге шеңберлер, ал қабырғаларға осы шеңберлерді байланыстыратын сызықтар сәйкес келеді. Графтың көрінісі Гамильт циклі жалпақ сызықпен белгіленген. Байланысқан граф арқылы бұтақтардың екі анықтамасын келтірейік. Бұтақтар (дерево) дегеніміз – доғаларының саны төбелерінің санынан бірге кем болатын байланыстырылған граф. Бұтақтар дегеніміз – циклі жоқ байланыстырылған граф. Графты түйістілік матрицасы (матрица инцидентностей) түрінде көрсету. Суретте көрсетілген қарапайым бағытталмаған граф берілсін. Қарапайым бағытталмаған граф Графтар теориясы бойынша ЭЕМ жадысында графты көрсетудің классикалық әдісі ретінде түйістілік матрицасы (матрица инцидентностей) қолданылады. Осындай матрицада жолдардың саны төбелер санына, ал бағаналар саны граф қабырғаларының санына сәйкес болады. Егер төбе мен қабырға түйістілі болса, онда бағана мен жол қиылысында 1 жазылады, әйтпесе 0 жазылады. Түйістілік матрицасы Қарапайым бағытталмаған граф Бағытталған граф Бағытталған графтың түйістілік матрицасы жүктеу/скачать 291,42 Kb. Достарыңызбен бөлісу:
|