Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану

жүктеу/скачать 1,12 Mb.

бет	8/15
Дата	12.09.2020
өлшемі	1,12 Mb.
	#78187

1 ... 4 5 6 7 8 9 10 11 ... 15

Байланысты:
Лекция дискретка каз

Дәріс №7-8. Графтар саны. Графтармен орындалатын операциялар

Қолданылған әдебиеттер

[1], [2], [3], [5], [16], [18].

Бақылау сұрақтары:

1.Граф дегеніміз не?

2.Инциденттік матрица қалай анықталады?

3.Толық граф дегеніміз қандай граф?

Ілмек деген не?

5.Графтың қандай түрлері бар?
Дәріс №7-8. Графтар саны. Графтармен орындалатын операциялар
Дәріс мақсаты:Графтармен орындалатын операциялармен таныстыру.

Кілттік сөздер:граф,цикломатиялық сан,Гамильтон графы,.
Цикломатиялық сан. Графтың барлық төбелері арқылы өтетінэлементарлық жол гамильтондық жол деп аталады да, егер оның басы және соңы бірігіп кетсе, онда оны гамильтондық цикл деп атайды.
Белгілі коммивояжер жөніндегі есеп былай тұжырымдалады: Қосарланған қашықтағы белгілі n қалалар бар. Коммивояжер барлық қалаларға келгендегі жолдың ұзындығының қосындысы өте аз (минималды) болатынды табу керек.
Бұл дегеніміз оң сандар жазылған қырлардың ұзындығы ^kn толық графтағы гамильтон жолының ең аз ұзындығын табу (есептің варианты үшін – айналып

( , )

[,] _D
шығу арқылы қайтадан бастапқы жолға келу – минималды гамильтондық циклді табу).
^Gn граф төбесініңn!алмастыруға сәйкестенетін,ал қыры екі төбеніқосатын көрші элементтерінің өзгешелігі транспозициясында болатын (әрбір
төбе ⁿ¹ басқа төбелермен қосатын) {1,2,…,n} құралған жиынын қарастырамыз.
Сонда көрсетілген тізбек ^Gn графындағы жолына сәйкес келеді 2.8 а - суретте n =3 кескіні көрсетілген кезкелген графтың екі жұп бөліктерінің қосындысыда жұп граф бөлігі болады.
Егер ^S1 және ^S2^H1 және ^H2 граф бөліктерінің кейбір төбенің дәрежелері болса, ал ^S12^H1^H2 қиылысуындағы оның дәрежесі болса, онда ^H1^H2 граф бөлігінің төбесіндегі ^S^{( )} дәрежесі ^H1^H2⁽^S1^S12^{) (}^S2^S12⁾^S1^S2²^S12 .

321

312 ₂₃₁

213

132

123
1-сурет
^S1 және^S2 жұп болғандықтан онда^S⁽ ⁾-де жұп.
Сондықтан жұп граф бөліктері кеңістіктегі барлық граф бөліктерінің кеңістік бөліктерін құрайды, да ілінген элементарлық циклдердің жиыны кеңістік бөлігімен бірігіп кетеді.

Осы кеңістік бөліктерінің ^V - өлшемін анықтаймыз. P қырлардан және

^b төбелерден тұратын ^Gбайланысты граф берілсін.D–оның кейбір
тұлғасы. ^{P b}¹ – хорда саны. әрбір хорда бір элементарлық
тізбегімен бірге элементарлық цикл құрайды, бірақ осы циклдердің векторы

(әртүрлі хорда үшін) байланыссыз жүйе құрайды, циклдердің әрбіреуі жүйенің қалған циклдерінің ешбіреуінде жатпайтын қырды ұстайды.

Осыдан ^V ^P ^b ¹.
Басқаша айтқанда, әрбір жұп граф бөлігі, кез келген жай цикл жүйенің циклі арқылы өрнектеледі.
Шынында, H жұп граф бөлігіне жүйенің циклдерінің H -қа кіретін граф хордасын қосамыз. Алынған қосынды ешқандай хорданы ұстамайды (әрбір

хорда қосындыға екі рет кіреді: H граф бөлігі және жүйенің циклдерінің біреуі ретінде) D ағашының кейбір граф бөлігі ретінде. Осыдан құр граф бөлігі, сол себепті қарсы жағдайда жұп граф бөлігі шығар еді ( H және циклдерінің қосындысы), D ағашында тұратын элементарлық циклдер.

Сондықтан ^{V P b}¹. K компоненттерімен байланысты базис кеңістігіндегі жұп граф бөліктерінің байланыссыз графы үшін оның байланысты компоненттерінің бірігуімен алынады да, ал қырлары мен

төбелерінің сандары қосылады. Сондықтан,	егер		ⁱ -ші компоненттің қыры
	K		K
PP_i		,	bb_i	, ^V саны графтың
^Pi _және^bi _{төбесі болса,онда}Vp b K _,	i 1	,	i 1	, ^V саны графтың

цикломатиялық саны деп аталады.^V ⁰болғандықтан,кез келген граф үшін

b p_.

Ағаштар байланысты графтар, оның цикломатиялық саны ^V ⁰.

Мысал 1. ^K5толық граф үшін (5 төбе,	C²	5!	3!4 5 ₁₀
	5	2!3!	2!3!	қыр

цикломатиялық сан ^V ¹⁰ ^{5 1} ⁶.

жүктеу/скачать 1,12 Mb.

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

1 ... 4 5 6 7 8 9 10 11 ... 15