Лаборатория2

2.2 Қўшмалик матрицаси. Бизга Г йўналтирилмаган граф берилган бўлиб, у чекли бўлсин. Айтайлик (а₁,…,а_n) Г графнинг қирралари бўлсин. У ҳолда қўшмалик матрицаси ||A_ij|| ( i=1,m, j=1, n) m та қатор ва n та устундан иборат бўлади. A_ij матрицанинг устунларига Г нинг тугунлари ва қаторларига Г нинг қирраларини мос қўямиз. У ҳолда
A_ij=
š оидадан фойдаданиб šœшмалик матрицасини ќосил šиламиз. Мисол.

	a1	A2	a3	a4	a5	a6	a7
e1	1	1	0	0	0	0	0
e2	1	0	1	0	0	0	0
e3	0	1	0	1	0	0	0
e4	1	0	0	0	1	0	0
e5	0	1	0	0	0	1	0
e6	0	0	1	1	0	0	0
e7	0	0	1	0	1	0	0
e8	0	0	0	1	0	1	0
e9	0	0	0	0	1	0	1
e10	0	0	0	0	0	1	1

Агар Г йўналтирилган граф бўлса, у ҳолда
A_ij=
šоидадан фойдаданиб šœшмалик матрицасини ќосил šиламиз.
Мисол.

	а1 а2 а3 а4 а5 а6 а7
е1	-1 1 1 0 0 0 0
е2	-1 0 0 0 0 0 0
е3	0 -1 0 1 0 0 0
е4	0 0 -1 0 1 0 0
е5	0 0 -1 0 0 1 0
е6	0 0 -1 1 0 0 1
е7	0 0 0 0 0 0 2

2.3 Қўшнилик матрицаси. Фараз қилайлик Г йўналтирилмаган граф бўлсин. Графнинг қўшнилик матрицасида A_ij нинг устунларига ҳам қаторларига ҳам графнинг тугунларини мос қўямиз. У холда
A_ij=
šоидадан фойдаланиб šœшнилик матрицасини ќосил šиламиз.
Мисол. 2.1-расмда келтирилган йўналтирилмаган граф учун šœшнилик матрицаси šуйидагича бœлади.

	а1 а2 а3 а4 а5 а6 а7
а1	0 1 1 0 1 0 0
а2	1 0 0 1 0 1 0
а3	1 0 0 1 1 0 0
а4	0 1 1 0 0 1 0
а5	1 0 1 0 0 0 1
а6	0 1 0 1 0 0 1
а7	0 0 0 0 1 1 0

Г йўналтирилган граф бўлсин. У ҳолда қўшнилик матрицаси A_ij нинг устунларига ҳам сатрларига ҳам графнинг тугунларини мос қўямиз.
У ҳолда

šоидадан фойдаданиб šœшнилик матрицасини ќосил šиламиз.

Мисол. 2.2-расмда келтирилган йўналтирилган граф учун šœшнилик матрицаси šуйидагича бœлади.

	а1 а2 а3 а4 а5 а6 а7
а1	0 1 1 0 0 0 0
а2	0 0 0 1 0 0 0
а3	0 0 0 0 1 1 1
а4	0 0 0 0 0 0 0
а5	0 0 0 0 0 0 0
а6	0 0 0 0 0 0 0
а7	0 0 0 0 0 0 1

Теорема. Агар графда каррали қирралари ҳамда сиртмоқ мавжуд бўлмаса, n та тугунга эга бўлган ва боғлиқ компонентаси К га тенг бўлган графнинг қирралари сони энг кўпи билан М= аниšланади.
Машрутнинг узунлиги деб, шу маршрутда мавжуд қўшни (е_i-1, e_i) қирралар сонига айтилади.
Графнинг ихтиёрий а ва ихтиёрий в тугунлари орасидаги масофа деб, шу тугунларни боғловчи энг кичик узунлика эга бўлган занжирга айтилади.

Мисол.

d(a₁,a₃)= (е₀, е₁)=2;
d(a₁,a₄)=(е₀, е₂)=2;
d(a₁,a₄)=(е₀, е₁, е₃)=3
Графнинг диаметри деб, энг катта узунликка эга бўлган масофага айтилади.

Мисол. d(a₁,a₄)=(е₀, е₁, е₃)=3.
с тугун Г графнинг фиксирланган тугуни бўлсин. х эса графнинг ихтиёрий тугуни бўлсин. с тугун учун максимал масофани ҳисоблаймиз. Қандайдир с₀ тугун учун бу максимал масофа бошқа тугунларга нисбатан минимал бўлса, уҳолда с₀ Г графнинг маркази дейилади ва с₀ учун аниқланган масофа Г графнинг радиуси дейилади.

Бу мисолда марказ 3 ёки 6 тугунлар бўлиши мумкин, чунки r(c)=2.
2.4 Эйлер графи. Бизга йўналтирилмаган Г граф берилган бўлсин. Эйлер цикли шундай циклки, унда графнинг маълум бир тугунидан чиқиб, барча қирралардан фақат бир марта ўтиб, яна шу тугунга қайтиб келиши керак.
Графда Эйлер цикли мавжуд бœлиши учун:
а) Граф богланган бўлиши;
б) Графнинг барча тугунларининг локал даражалари жуфт
бœлиши керак;
Графда Эйлер занжири мавжуд бœлиши учун:
а) Граф богланган бўлиши;
б) Графнинг 2 та тугуни(бошланиш ва охирги) локал даражалари тоš бœлиб, šолган барча тугунларининг локал даражалари жуфт бœлиши керак.
Агар Г йўналтирилмаган графда Эйлер цикли мавжуд бўлса, бундай графга Эйлер графи дейилади.
Мисол.



2.5. Гамильтон графи. Агар графда оддий цикл мавжуд бўлиб, бу циклда графнинг барча тугунлари қатнашса, бундай цикл Гамильтон цикли дейилади.
Оддий занжир Гамильтон занжири дейилади, агар бундай графда тугунларнинг ќаммаси иштирок этса. Тугун ва қирралар такрорланмаслиги керак.
Графда Гамильтон цикли мавжуд бўлса, бу граф Гамильтон графи дейилади.
Мисол.
Бу графда оддий цикл S₁=(е₀, е₁, е₄ е₅, е₆) – Гамильтон цикли, S₂=( е₀, е₁, е₇, е₆) - Гамильтон цикли эмас, чунки а₅ тугун қатнашмаяпти.
2.6.Топшириš вариантлари.
Šуйидаги келтирилган йуналтирилган ва йœналтирилмаган графлар учун:
1) Графни тœлдирувчисини топинг.
2) Графни šисм графини топинг.
3) Šœшмалик матрицани тузинг.
4) Šœшнилик матрицани тузинг.
5) Графни марказини топинг.
6) Графни диаметрини топинг.
7) Графни радиусини топинг.
8) Графда Эйлер цикли мавжудлигини текширинг.
9) Графда Гамильтон цикли мавжудлигини текширинг.
10) Графни цикломатик сонини топинг.
11) Графни šирралар сонини тугунларнинг локал даражалари ва šœшнилик матрицаси орšали аниšланг.














Адабиётлар

1. 
   Т.П. Лихтарников, Д.Л.Сукачева. Математическая логика. Сант-Петербург,1999 г.
   
2. 
   С. Яблонский. Введение в дискретной математики. 1979. М. 261-с.
   
3. 
   Гаврилов Г.П., Сапоженко А.А.Сборник задач по дискретной математики.М.Наука,1977. 2002. 271 с.
   
4. 
   Х.Т.Тураев. Математик мантик ва дискрет математика. Укув кулланма. Т-2004. 456 б.
   
5. 
   Х.Т.Тўраев, И.А.Азизов, Отақулов С.О. Комбинаторика ва графлар назарияси. СамДУ нашр-матбаа маркази.2006. 267 бет.
   

МУНДАРИЖА

Бет

	Мустақил ишларни бажариш қоидалари	3
1-МАВЗУ	ФУНКЦИЯЛАР СИСТЕМАСИНИНГ ТЎЛИҚЛИГИНИ АНИҚЛАШ	5
1.1	Функционал ёпиš синфлар	5
1.2	Пост теоремаси	10
1.3	Берилган мисол ёрдамида амалий кўрсатмалар	14
1.4	Топшириš вариантлари	18
2-МАВЗУ	ГРАФЛАР УСТИДА АМАЛЛАР	20
2.1	Графлар назариясининг асосий тушунчалари	20
2.2	Қўшмалик матрицаси	23
2.3	Қўшнилик матрицаси	24
2.4	Эйлер графи	27
2.5	Гамильтон графи	28
2.6	Топшириš вариантлари	29
	Адабиётлар	35