Негізгі анықтамалар
жүктеу/скачать 289,71 Kb.
|
13-15АПТАдәрістері
- Бұл бет үшін навигация:
- Негізгі анықтамалар
|
13-15 АПТА ДӘРІСТЕРІ. ГРАФТАР ТЕОРИЯСЫНЫҢ АНЫҚТАМАЛАРЫ МЕН НЕГІЗГІ ҰҒЫМДАРЫ, МЫСАЛДАР. ОРГРАФТАР, МУЛЬТИГРАФТАР. ІШКІ ГРАФТАР. ӨЛШЕНЕТІН ГРАФ. ҚЫСҚА ЖОЛДАР. ЭЕМ-ДА ГРАФТАРДЫҢ БЕРІЛУІ (МАТРИЦАЛЫҚ ЖӘНЕ БАСҚА ТҮРЛЕРІ) ҚЫСҚА ЖОЛДАР. ИЗОМОРФТЫ ГРАФТАР. АҒАШТАР. АНЫҚТАМАЛАР. ОСТТАРДЫҢ ӘРТҮРЛІ АНЫҚТАМАЛАРЫНЫҢ ЭКВИВАЛЕНТТІГІ Негізгі анықтамалар Табиғаттың кез-келген объектісінен алынған төбелер деп аталатын V – жиыны (оларды жазықтықта нүктелер түрінде көрсетуге болады) және қабырға деп аталатын, ei=(vi1, vi2), vijV, төбелер жұбының жиыны (оларды доғалармен, немесе екі төбе арасындағы бағыттармен көрсетеді) - E болатын екі жиыннан тұратын G = (V,E) жұбы граф деп аталады. V –төбелер жиыны, E –қабырғалар жиыны деп аталады. Егер ei қабырғасын беретін төбелер ретінің мәні болса, онда граф бағдарланған (ориентирациялы) граф қысқаша – орграф деп деп аталады. Бұл жағдайда графтың доғасына (қабырғасына) бағыт көрсетеді және бір төбесін басы екіншісін –соңы деп айтады. Қарсы жағдайда граф бағдарланбаған (ориентирациясыз, бағдарсыз) деп аталады. Алдағы жағдайларда бағдарланғандығы көрсетілмеген, нақтыланбаған «граф» сөзін бағдарланбаған граф деп есептейміз. Қарапайым графтың ілгегі және еселі қабырғасы болмайды. Қарапайым графты жай граф деп те айтады. Оларды еселі қабырғалары бар графтардан ажырату үшін еселі қабырғасы бар графтарды мультиграф деп айтады. Ары қарай тек ақырлы графтарды ғана қарастырамыз. 5.1.2. G = (V,E) –графы толық болады, егер кез-келген екі төбесі бір қабырғамен түйіскен (бір ғана қабырғамен байланысқан) болса, яғни, кез-келген төбелер жұбы сыбайлас (қандайда бір қабырғамен байланысқан) болатын бағдарсыз граф. Kp деп белгіленеді, мұндағы р = |V| - төбелер саны, мұнда қабырғалар саны |Е| = p(p-1)/2 –ге тең болады. Қабырғасы жоқ G = (V,E) – графы бос деп аталады, Е = [белгіленуі - Nm]. Байланысты граф деп кез-келген төбелер жұбынан бір-біріне өтуге болса, яғни кез-келген төбеден екінші төбеге өтетін жол (маршрут) болса. Граф байланысты болады, сонда және тек қана сонда, егер оның төбелер жиынын әр қабырғасының екі шеткі нүктелері бір жиында қалатындай екі бос емес жиындарға бөлуге болса. 6.1 теорема. Байланысты графтардың қасиеттері. а) байланысты граф бір қабырғасын жойғаннан кейін де байланысты болып қала береді, егер бұл қабырға циклде болса. б) К төбесі бар байланысты графтың К-1-ден аз емес қабырғасы болады. в) байланысты графта кез-келген максималды ұзындықты қарапайым екі тізбесінің тым болмаса бір ортақ төбесі болады. г) N төбесі бар және К байламдық компоненттері бар графтың қабырғалар саны 1/2(N-K)(N-K+1)-ден артпайды. Байланысты графтың екі төбесінің ара қашықтағы деп осы төбелерді қосатын ең қысқа тізбенің (жолдың, маршруттың) ұзындығын айтамыз, яғни қысқа жолдағы қабырғалар саны. Мысалы, 6.1 суретте көрсетілген G1 графының А төбесінен D, E және F т өбелеріне дейінгі қашықтық 1-ге тең ал, В және С төбелеріне дейінгі қашықтық 2-ге тең: r(A,D) = r(A,E) = r(A,F) = 1, r(A,B) = r(A,C) = 2. Графтың төбесінің эксцентриситеті деп берілген төбеден басқа төбелерге дейінгі қашықтықтардың ең үлкенін айтамыз. G1 графы үшін А төбесінің эксцентриситеті 2-ге тең: е(А) = 2, басқа төбелердің де эксцентриситетін табу қиын емес: е(В) = е(С) = е(D) = e(E) = e(F) = 2. Графтың радиусы ретінде төбелерінің эксцентриситеттерінің ең кішісін алады, ал диаметрі – максималды эксцентриситет. G1 графында радиус пен диаметр беттеседі: R(G1) = D(G1) = 2. 5.1.3. Графтың төбесінің дәрежесі деп осы төбеге тиісті болатын (түйіскен) қабырғалар санын айтамыз. Графтың төбелерінің дәрежелерінің өсу ретімен немесе кемі ретімен берілген тізімі вектор-дәрежесі деп аталады. Мысалы, G1 графында ол (3,3,4,4,4,4) –ге тең, 6.2 –суретте көрсетілген G2 графында ол (1,2,2,2,3). Дәлелдеуі өте қарапайым. 6.2 теорема. Графтың барлық төбелерінің дәрежелерінің қосындысы қабырғаларының екі еселенген санына тең. G2 графын 6.2 суреттен басқа етіп, мысалы 6.3 суреттегідей салуға болады. Бұған көз жеткізу үшін G2 графтың А1 төбесіне- 6.3 суреттегі графтың А төбесін сәйкес қоюға болады, А2 төбесіне–D төбесін А3 төбесіне – Е төбесін, А4 төбесіне –В төбесін, А5 төбесіне –С төбесін сәйкес қоюға болады. Нәтижесінде, екі графтың төбелерінде өзара бірмәнді сәйкестік орнады. . Мұндай жағдайда бұл суреттердегі графтарды өзара изоморфты деп те айтады. Изоморфты графтардың вектор-дәрежесі бірдей. Кері тұжырым дұрыс емес. Мысалы, 6.4 суреттегі G4 пен G5 изоморфты емес, себебі G4 графында ұзындығы 3-ке тең цикл жоқ, ал G5 графында ол бар, А1А2А3-ке тең. Бірақ, бұл графтарда вектор–дәрежелері тең: (2,2,2,2,3,3). 5.1.5 Граф жазық деп аталады, егер жазықтықта оның қабырғалары тек төбелерде ғана қиылысса. Граф планарлы деп аталады, егер оның жазық кескіні болса. 6.3 және 6.4 суреттерде –жазық графтар, 6.2 суретте планарлы граф, себебі оның изоморфты жазық кескіні бар, ол G3 графы. Ал 6.1 суреттегі граф планарлы да болмайды. Оны келесі теоремадан көруге болады. 6.3 теорема. Граф планарлы болмайды,сонда және тек қана сонда егер келесі шарттардың бірі орындалса: а) (Понтрягин-Куратовский) Графтың толық бес төбелі К5 немесе К3,3 графына (төменде айтылады) гомеоморфты болатын ішкі графы болады; б) (Харари-Татта) Графты қабырғасын созу арқылы немесе кейбір элементтерін жою арқылы К5 немесе К3,3 графтарына гомеоморфты графқа айналдыруға болады. Графтар гомеоморфты болады, егер біреуі екіншісінен қабырғаларын желімдеу немесе бөлу операцияларының көмегімен алынатын болса (6.6 сурет). АВ қабырғасын созу, АВ қабырғасы жойылады, А және В төбелері бір төбеге айналады және осы жаңа төбе А және В төбелерімен сыбайлас болған барлық төбелермен жалғасады (6.7 суретті қараңыз). жүктеу/скачать 289,71 Kb. Достарыңызбен бөлісу:
|