-Дәріс тақырыбы: Графтар. Қасиеттері. Операциялар

Граф ұғымы. Көптеген қолданбалы есептерде айналамызды қоршаған ортаның әртүрлі объектілер арасындағы байланыстар жүйесі зерттеледі. Объектілер төбелер деп аталып, нүктелер арқылы белгіленеді, ал төбелер арасындағы байланыстар доғалар деп аталып, сәйкес нүктелерді қосатын бағытталған түзулермен белгіленеді. Қала көшелерін граф арқылы кескіндеуге болады: көше қиылысуларын графтардың төбесі деп, ал көшелерді доғалар деп алуға болады;

Графтың төбелерінің қандай сызықтарымен қосылатындығы (түзу әлде қисық), сызықтардың ұзындығы туралы ақпараттар маңызды емес.Төбелердің арасында байланыс бар екендігі және ол байланыс туралы ақпарат R доғалар жиынында екендігі болса болды.Төбелерді қосатын сызықтардың бағыты көрсетілген болуы мүмкін (мысалдағы сияқты). Мұндай граф бағытталған граф деп аталады (оргграф). Оған математикалық түрде мынандай анықтама беруге болады.

графы бағытталған (оргграф) деп аталады, ал R қатынасы симметриялы болса (a,b) R, (b,а) R онда G бағытталмаған (неоргграф) немесе н-граф деп аталады Айталық: a,b-граф төбелері, e=(a,b) оларды қосатын доға болсын. Мұндай жағдайда а, b төбелері мен е доғасы инцидентті деп аталады. b мен e доғасы да инцидентті. Әр доға eE өзі қосатын екі төбеге инцидентті болады. Бір доғамен қосылатын 2 төбе сыбайлас ( бүйірлес) деп аталады.

Анықтама: Төбелердің бір жұбына инцидентті доғалар еселі немесе параллель доғалар деп аталады

Анықтама: Еселі доғалары бар граф мультиграф деп аталады.

Анықтама: Шығатын және кіретін төбесі біреу болатын доға ілгек деп аталады.



Анықтама: Егер (a,b), (b,а) доғалары бір уақытта R қатынасына жатса, онда бұл доғалар туралы ақпаратты [a,b] = {(a,b), (b,a)} жиыны арқылы көрсетуге болады. [a,b] жиыны қабырға деп аталады.

Мысалы,мына суреттегі графтың 4 төбесі, 5 қабырғасы бар.

Төбелері: v₁, v₂, v₃, v₄; Қабырғалары:e₁,e₂, e₃, e₄ e₅; Бұл графтағы v₁ мен v₂; v₂ мен v₃; v₃ пен v₄; v₄ пен v₅ іргелес төбелер, v₁, v₃-сыбайлас емес.

Сол сияқты: e₁,e₂; e₂,e₃; e₃,e₄; e₄,e₁; e₁,e₅; e₂,e₅; e₃,e₅; e₄,e₅;-қабырғалары сыбайлас.e₁,e₃; e₂,e₄;- сыбайлас емес қабырғалар.

Егер G={M,R} орграфындағы әр (a,b)R доғасына, (b,a) жұбын қосса нәтижесінде берілген G графына сәйкес Н-граф шығады, оны F(G) деп белгілейді.

Анықтама: Егер граф элементтерінің (төбелері мен қабырғалары) жиыны ақырлы болса, графта ақырлы деп, ал қабырғалар жиыны бос болса, бос граф деп аталады.

Ілгексіз, әрі еселі қабырғалары жоқ және әрбір төбелер жұбы қабырғамен қосылған граф толық граф деп аталады.

Анықтама: Берілген G графындағыдай төбелері және G графына қосқанда оны толық графқа айналдыра тындай ғана қабырғалары бар графы G-ң толықтауыш графы деп аталады.

Каталог: uploads
uploads -> Сәлім меңдібаев армысың, алтын таң! Журналист жазбалары Қостанай – 2013 ж
uploads -> Тақырыбы: Ғарышты игеру (аудандық семинар)
uploads -> Реферат kz Қазақша рефераттар сайты Талғат Амангелдіұлы Мұсабаев Қазақстанның ұлттық ғарыш агенттігінің төрағасы. Ғарышкер, техника ғылымдарының докторы
uploads -> Ғарыш әлеміне саяхат
uploads -> Сабақ тақырыбы: Шерхан Мұртаза «Ай мен Айша» романы Сабақ мақсаты: ҚР «Білім туралы»
uploads -> Қазақ тілі мен латын тілі кафедрасы Қазақ Әдебиеті пәні бойынша әдістемелік өҢдеу мамандығы: Фельдшер Мейірбике ісі Стамотология Курс: І семестрі: ІІ
uploads -> Ф 7 –007-02 Қазақстан Республикасы Білім және ғылым министрлігі
uploads -> 2011 жылдың 14 мамырында «Жалпы гигиена және экология», «Эпидемиология» кафедрасының ұйымдастыруымен және «Студенттік басқару ұйымының» ұйымдастыруымен Д. Е
uploads -> Сабақтың тақырыбы Бала Мәншүк ( Мәриям Хакімжанова) Сілтеме
uploads -> Ана тілі №2. Тақырыбы: Кел, балалар, оқылық Мақсаты

жүктеу/скачать 21,8 Mb.

Достарыңызбен бөлісу: