Kombinatorika va graflar nazariyasi



Download 0,54 Mb.
Pdf ko'rish
bet1/3
Sana28.01.2020
Hajmi0,54 Mb.
#37767
  1   2   3
Bog'liq
6 mavzu komenatorokadan


 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



 

 

 



 

 

 



 

 

Mavzu: 

Graflar  ustida  amallar.  Marshrutlar  va 

zanjirlar

 

 

 

 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Graflar ustida amallar 

 

Graflar  ustida  turli  amallar  bajarish  mumkin,  masalan,  graflarni 

birlashtirish,  biriktirish,  ko‘paytirish,  grafni  qismlarga  ajratish  va 

hokazo. 


Eng  sodda  amallardan  biri  sifatida  grafdan  uchni  olib  tashlash 

amalini keltirsa bo‘ladi. Bu amalni qo‘llash berilgan grafning uchlari 

to‘plamidan  birorta  element  yo‘qotishni  (olib  tashlashni)  anglatadi. 

Natijada  uchlari  soni  bittaga  kamaygan  yangi  graf  hosil  bo‘ladi. 

Albatta, bu amalni uchlari soni ikkitadan kam bo‘lmagan graflar uchun 

qo‘llash  mumkin bo‘lib,  uni  bajarish  jarayonida  olib  tashlanayotgan 

uch  bilan  birgalikda  shu  uchga  insident  bo‘lgan  barcha  qirralar 

(yoylar) ham olib tashlanadi. 

 

 


 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Eng sodda amallar qatoriga grafdan qirrani (yoyniolib tashlash 

amalini  ham  kiritish  mumkin.  Bu  amalga  ko‘ra  berilgan  grafning 

qirralari  (yoylari)  to‘plamidan  birorta  element  yo‘qotiladi  (olib 

tashlanadi). Berilgan grafdan qirrani (yoyni) olib tashlayotganda shu 

qirraga (yoyga) insident uchlarni grafda qoldirish ham yo‘qotish ham 

mumkin. Bu yerda vaziyatga qarab ish yuritiladi. 

( , )

G

V U

 va 



'

( ',


')

G

V U

 graflar berilgan bo‘lsin. Agar 



'

V

V

 va 



G

  grafning  barcha  qirralari  (yoylari) 

'

G

  grafning  ham  qirralari 

(yoylari), ya’ni 

'

U



U

 bo‘lsa, u holda 



G

 graf 


'

G

 grafning qism grafi 

deb ataladi. 

 

 



 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



 

1-  mis o l .  1-  shaklda  Petersen  grafining  qism 

graflaridan biri tasvirlangan. ■ 

 

 

Agar 



G

 graf karrali qirralarga ega bo‘lmasa, u holda 

uchlari 

G

 grafning barcha uchlaridan iborat bo‘lgan shunday yagona 



G

 graf mavjudki, 



G

 grafdagi barcha juft uchlar faqat va faqat 



G

 grafda 


qo‘shni  bo‘lmagandagina  qo‘shnidir.  Bunday 

G

  graf  berilgan 



G

 

grafning to‘ldiruvchi grafi deb ataladi. 



Berilgan  graf  uchun  to‘ldiruvchi  grafni  qurish  jarayonini  ham 

graflar ustida bajariladigan amallar qatoriga kiritish mumkin. 



G

 graf 


uchun to‘ldiruvchi grafni qurish amalini qo‘llash natijasida 

G

 graf 


hosil bo‘ladi. Isbotlash mumkinki, 

G

G

 munosabat o‘rinlidir. 



1- shakl 

 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



2- mis ol . 2- shaklda tasvirlangan graf 1- shaklda ifodalangan graf 

uchun to‘ldiruvchi grafdir. 

Graflar 

ustida 


shunday 

amallarni 

bajarish 

mumkinki,  ular  elementlari  soni  berilgan  grafdagidan 

ko‘proq  bo‘lgan  boshqa  graflarning  hosil  bo‘lishiga 

olib  keladi.  Bunday  amallar  qatoriga  uchni  qo‘shish 



amali  yoki  qirrani  (yoyni)  qo‘shish  amalini  kiritish 

mumkin. 


 

 

2- shakl 



 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Grafga yangi uchni qo‘shish turlicha usul bilan amalga oshirilishi 

mumkin. Masalan, yangi 



v

 uchni berilgan grafga qo‘shish shu grafning 

1

v

  va 


2

v

  uchlariga  insident  bo‘lgan  qandaydir 



u

  qirrasiga  qo‘shish 

orqali quyidagicha ikki bosqichda bajarilishi mumkin: 

1) 


u

 qirra berilgan grafdan olib tashlanadi; 

2)  hosil  bo‘lgan  grafga  ikkita  yangi  qirralar: 

v

  va 


1

v

  uchlarga 

insident 

1

u

 qirra hamda 

v

 va 


2

v

 uchlarga insident 

2

u

 qirra qo‘shiladi. 

Bu  jarayon  grafda  qirraga  darajasi  2  bo‘lgan  yangi  uchni 

qo‘shish (kiritish) yoki qirrani ikkiga bo‘lish amali deb ataladi. 

Agar 


G

 graf 


'

G

 grafdan qirrani ikkiga bo‘lish amalini chekli marta 

ketma-ket qo‘llash vositasida hosil qilingan bo‘lsa, u holda 

G

 graf 

'

G



 

grafning bo‘linish grafi deb ataladi. 

 

 



 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Bo‘linish graflari izomorf bo‘lgan graflar gomeomorf graflar deb 

ataladi. 

3-  shaklda  tasvirlangan  graflar  izomorf  emas,  lekin  ular 

gomeomorf,  chunki  bu  graflarning  har  biri  4-  shaklda  tasvirlangan 

bo‘linish grafiga ega. 

 

 

 

3- shakl 

4- shakl 


 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Graflarni  birlashtirish

. 

1

1



1

( ,


)

G

V U

  va 



2

2

2



( ,

)

G



V U

  graflar 



berilgan  bo‘lsin.  Uchlari  to‘plami 

1

2



V

V

V

  va  qirralari  (yoylari) 



korteji 

1

2



U

U

U

  kabi  aniqlangan



1

 

( , )



G

V U

  graf 



1

G

  va 


2

G

 

graflarning  birlashmasi  (uyushmasi)  deb  ataladi  va 

1

2

G



G

G

 



ko‘rinishda belgilanadi. 

 

 

                                                           

1

 Bu yerda birlashma “



” amali 

V

ning to‘plam, 



U

ning esa kortej ekanligini e’tiborga olgan holda amalga oshiriladi. 



 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



3- mis ol . 5- shaklda uchlari to‘plamlari kesishmaydigan 

2

K

 va 

3

K



 

graflarning birlashmasi amali tasvirlangan. ■ 



4-  mis o l .  Uchlari  to‘plamlari  kesishadigan 

graflarning  birlashmasi  amali  6-  shaklda 

tasvirlangan. ■ 

Agar  birlashtirilayotgan  graflarning  uchlari 

to‘plamlari kesishmasa, u holda bu graflarning birlashmasi diz’yunkt 

birlashma  deb  ataladi.  Masalan,  5-  shaklda  tasvirlangan  birlashma 

diz’yunkt, 6- shakldagi birlashma esa – diz’yunkt emas. 



 

 

5- shakl 

1

 

2



 

3

 



4

 

5



 

1

 



2

 

3



 

4

 



5

 

 



 

 

6- shakl 



1

 

2



 

3

 



4

 

5



 

1

 



2

 

3



 

4

 



5

 

4



 

3

 



 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Graflarni biriktirish. 

1

1



1

( ,


)

G

V U

 va 



2

2

2



( ,

)

G



V U

 graflar berilgan 



bo‘lsin. 

1

G

 va 

2

G



 graflar birlashtirilishi hamda 

1

G

 grafning har bir uchi 

2

G

 grafning har bir uchi bilan qirra vositasida tutashtirilishi natijasida 

hosil  bo‘lgan 

( , )

G

V U

  graf 



1

G

  va 


2

G

  graflarning  birikmasi 

(tutashmasi) deb ataladi va 

1

2



G

G

G



 ko‘rinishda belgilanadi. 

5-  mis ol .  Uchta  uy  va  uchta  quduq  haqidagi  boshqotirma 

masalaga  mos  graf  uchlari  to‘plamlari  kesishmaydigan  ikkita  (

3

O

nolgraflarning birikmasidir. ■  



 

 

 shakl 


 

 

 



 

 

 



 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



6- mis ol . 7- shaklda uchlari to‘plamlari kesishmaydigan 

2

K

 va 

3

K



 

graflarning birikmasi amali tasvirlangan. ■ 

Agar  uchlari  to‘plamlari  kesishmasi  bo‘sh  bo‘lmagan  graflarni 

biriktirish  zarur  bo‘lsa,  u  holda  hal  qilinayotgan  masala  xossalarini 

e’tiborga olib ish ko‘rish kerakligini ta’kidlaymiz. 

 

 



 

 

7- shakl 











 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



 

Graflarni ko‘paytirish. 

1

1



1

( ,


)

G

V U

 va 



2

2

2



( ,

)

G



V U

 graflar 



berilgan bo‘lsin. Uchlari to‘plami 

1

2



V

V

V

 


 bo‘lgan 

( , )


G

V U

 



grafning 

qirralari 

(yoylari) 

kortejini 

quyidagicha 

aniqlaymiz:  agar 

1

1

'



''

v

v

  va 



2

2

2



(

',

'')



v

v

U

  yoki 



2

2

'



''

v

v

  va 



1

1

1



( ',

'')


v v

U

  bo‘lsa,  u  holda 



( ', '')

v v

U

  bo‘ladi,  bu  yerda 



1

1

1



',

''

v v



V



2

2

2



',

''

v



v

V



1

2

'



( ',

')

v



v v

V



 va 

1

2



''

( '',


'')

v

v

v

V



. Shunday 

usul bilan hosol qurilgan 

( , )

G

V U

 graf 



1

G

 va 


2

G

 graflarning 



ko‘paytmasi deb ataladi va 

1

2



G

G

G



 kabi belgilanadi. 

 

 



 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Graflarning ko‘paytmasi ta’rifiga asosan berilgan 

1

1



1

( ,


)

G

V U

  va 



2

2

2



( ,

)

G



V U

 graflarning ko‘paytmasi hisoblangan 



G

 grafdagi: 

– uchlar 

1

2



( ,

)

v v

 yoki 

2

1



( , )

v v

 ko‘rinishdagi juftliklardan iboratdir, bu 

yerda 

1

1



v

V



2

2

v



V



– 

1

2



'

( ',


')

v

v v

V



  va 

1

2



''

( '',


'')

v

v

v

V



  uchlar  faqat  va  faqat  shu 

holda qo‘shni bo‘ladilarki, qachonki bu uchlarni (juftliklarni) tashkil 

qiluvchi elementlarning biri unga mos element bilan ustma-ust tushgan 

holda  boshqa  elementlar  o‘z  grafida  qo‘shni  bo‘lishsa,  bu  yerda 

1

1

1



',

''

v v



V



2

2

2



',

''

v



v

V



– 

1

1



|

|

V



m



2

2

|



|

V

m



1

1

|



|

U

n

 va 



2

2

|



|

U

n

 munosabatlardan 



1

2

|



|

V

m m

 



va 

1 2


2 1

|

|



U

m n

m n



 bo‘lishi kelib chiqadi. 

 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



7- mis ol . 8- shaklda uchlari to‘plamlari kesishmaydigan 

2

K

 va 

3

K



 

graflarning ko‘paytmasi amali tasvirlangan. ■ 

 

 



 

 



 

 

 



 

 

 



 

8- shakl 



 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Dekart ko‘paytmalar bilan bog‘liq tuzilmalar ustida bajariladigan 

amallar  boshqalaridan  o‘ziga  xosligi  bilan  ajralib  turadi.  Bu  o‘ziga 

xoslik  graflarni  ko‘paytirish  amalida  namoyon  bo‘ladi.  Aniqrog‘i, 

graflar  ko‘patmasida  qatnashgan  birorta  grafning  qirralari  korteji 

bo‘sh bo‘lsada, ko‘paytirish amalini qo‘llash natijasida hosil bo‘lgan 

grafning qirralari korteji bo‘sh bo‘lmasligi ham mumkin. Haqiqatdan 

ham,  yuqorida  keltirilgan  graflarning  ko‘paytmasi  ta’rifidan  kelib 

chiqadiki, agar 

( , )

G

V U

 graf 



1

1

1



( ,

)

G



V U

 va 



2

2

2



( ,

)

G



V U

 graflarning 



ko‘paytmasi, ya’ni, 

1

2



G

G

G



 bo‘lsa, u holda 

1

2



V

V

V

 


 bo‘ladi va 

U

 

kortej  elementlari  bilan 



1

2

1



2

(

)



(

)

V



U

U

V



  birlashma  elementlari 

orasida  o‘zaro  bir  qiymatli  moslik  mavjud.  Shuning  uchun,  agar, 

masalan, 

1

U

 



2



U

 


 

bo‘lsa, 


holda 


1

2

1



2

1

2



(

)

(



)

V

U

U

V

V

U



 

 


 bo‘ladi, chunki grafning tarifiga ko‘ra 

1

V

 

. Demak, 



U

 


, ya’ni 

1

G

 bo‘sh graf bo‘lsada, 

1

2



G

G

G



 bo‘sh 

bo‘lmagan grafdir. 



 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Graflarni  ko‘paytirish  amalini  takror  qo‘llash  usuli  bilan  graflar 

nazariyasining  muhim  sinfini  tashkil  etuvchi 



n

  o‘lchovli  kublarni 

aniqlash  mumkin. 

n

  o‘lchovli  kub  (

n

Q

)  uchlari  soni  ikkiga  teng 

bo‘lgan  to‘la  graf 

2

K

  yordamida  quyidagi  rekurrent  formula  bilan 

aniqlanadi: 

1

2

Q



K



2

1

n



n

Q

K

Q



Yuqorida graflar ustidagi ba’zi amallar haqida qisqacha ma’lumot 



berildi.  Shuni  ta’kidlash  lozimki,  graflar  ustida  bundan  boshqa  bir 

qator amallar ham bor. 

 

 


 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Marshrutlar va zanjirlar haqida umumiy ma’lumotlar 

 Uchlari 

to‘plami 

1

2



{ ,

,...,


}

m

V

v v

v

 



va 

qirralar 

korteji 

1

2



{ ,

,...,


}

n

U

u u

u

  bo‘lgan  oriyentirlanmagan 



( , )

G

V U

  graf  berilgan 



bo‘lsin. Bu 

G

 grafdagi uchlar va qirralarning har ikki qo‘shni qirralari 

umumiy chetki uchga ega 

1

1



2

2

3



(...,

,

,



,

,

,...)



i

j

i

j

i

v u v u

v

 

ko‘rinishdagi chekli yoki cheksiz ketma-ketligi marshrut deb ataladi. 



Marshrutni  uning  uchlari  ketma-ketligi 

1

2



(...,

,

,...)



i

i

v v

  yoki  qirralari 

ketma-ketligi 

1

2



(...,

,

,...)



j

j

u u

 ko‘rinishda ham belgilash mumkin. 

Agar  marshrutda  qandaydir  uchdan  oldin  uchlar  bo‘lmasa,  bu 

uchni  marshrutning  boshlang‘ich  uchi  deb,  shu  uchdan  keyin 

marshrutga tegishli uchlar bo‘lmaganda esa, uni marshrutning oxirgi 

uchi deb ataydilar. 


 

 

KOMBINATORIKA VA GRAFLAR NAZARIYASI 



Agar marshrutning boshlang‘ich uchi 

p

v

 va oxirgi uchi 



q

v

 bo‘lsa, 

u holda uni 

p

v

 uchdan 

q

v

 uchga yo‘nalgan marshrut yoki chetlari 

p

v

 va 

q

v


Download 0,54 Mb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish