|
Graflar nazariyasining asosiy tushunchalari. Graflarning ba’zi turlari
|
| Sana | 08.01.2024 | | Hajmi | 2.76 Mb. | | #132649 |
Bog'liq disk 3 primova-m.h.-katta-hajmdagi-malumotlar-bigdatani-qayta-ishlash-vositalarining-qiyosiy-tahlili, 135474, намуна, GCE1Certificate, 56-Boshlang\'ich sinf o\'quvchilarida ijtimoiy kompetensiyalarni shakllantirish, Internet to’lov tizimlari va plastik kartochkalarga asoslangan tizimlar, Социальное содержание рекламы, slayd, Mustaqil ish Mavzu Kiberxafsizlik sohasida mashxur sertifikatla
O'ZBEKISTON RESPUBLIKASI OLIY VA O'RTA MAXSUS TA'LIM VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI
Telekommunikatsiya texnologiyalari va kasb ta'limi fakulteti 22-01-Guruh talabasi
Fan: Diskret tuzilma
MUSTAQIL ISH-1
Mavzu: Graflar nazariyasining asosiy tushunchalari. Graflarning ba’zi turlari
Bajardi: Umirzoqova SH Tekshirdi: Qo’chqorov F
Samarqand-2024-yil
ГРАФЛАР УСТИДА АМАЛЛАР.
2.1 Графлар назарияси Фани чизиклар ва нукталардан тузилган баьзи бир геометрик конфигурациялар тугрисидаги масалаларни ечишда ишлатилади. Бундай масалаларни ечишда, геометрик конфигурацияларда нукталар бир —бири билан тугри чизик ёки ёй билан бирлаштирилганми, буларнинг узунлиги канча каби факторлар эътиборга олинмайди. Энг мухими шундаки, хар бир чизик кандайдир берилган иккита нуктани бирлаштираяпти. Шундай килиб, графнинг таърифини куйидагича бериши мумкин.
Таъриф. Туплам .,ап} ва V тупламдан олинган жуфтликлар ајк)} наборига Граф дейилади.
V тупламдаги т,. . .,ап лар кандайдир объектлар булиб Г графнинг учлари дейилади. Е тупламдаги хар бир (ан, ajl), ајк) жуфтлик Графнинг кирралари дейилади.
Агар (а, ај) кирра берилган булса, у холда а, ва ај учлар бирлаштирилган дейилади.
Мисол. Агар аз аз, щ, аз аб, а7,}ва
бУлсин, у холда V ва Е туплам Г графни хосил килади.
Графнинг учларини тугунлар, 2 та учини бирлаштирувчи чизикни кирралар деб атаймиз.
а4
а5
Графнинг иккита тугуни умумий кирра билан узаро богланган боелса, улар кушни тугунлар дейилади.
Агар Г нинг 2 та кирраси умумий тугунга эга булса, улар кушма кирралар дейилади.
Мисол. (щ ф) кирра ( а2 аз) киррага
кушма, чунки а2 умумий тугунга эга.
аз
Бирорта тугунни узини - узига боглайдиган киррага сиртмок дейилади.
а]
Барча тугунлари ёлгиз тугундан иборат граф ноль
(бУш) граф дейилади. •al
о аз •а4
Агар Г графнинг барча тугунлари узаро богланган булса, бундай граф тулик граф дейилади.
а2 аз
а]
Агар Г графнинг барча кирраларида йУналиш курсатилган бУлса, бундай граф йУналтириган граф дейилади.
а2 аз
а4
Агар Г графнинг кирраларида йУналтириш курсатилмаган булса, у Колда граф йУналтирилмаган граф
дейилади. а2 аз
Г граф Г графнинг кисми дейилади, агар Г! нинг тугунлари туплами Г га тегишли бУлса, яъни Vl 'V булса, хамда Г нинг барча кирралари Г нинг хам кирралар булса,
ЯЪНИ Е С Е
Г Граф Г графнинг тулдирувчиси дийилади, агарда унинг барча тугунлари Г графга тегишли бУлиб, бирорта хам кирраси Г га тегишли булмаса.
4
-тулдирувчи граф.
2.2 кушмалик матрицаси. Бизга Г йУналтирилмаган граф берилган булиб, у чекли булсин. Айтайлик (щ ,ап), Г графнинг кирралари булсин. У холда кушмалик матрицаси llAijll, i=l,m, j=l, п т та катор ва п та устундан иборат бУлади, Aij матрицанинг устунларига Г нинг тугунлари, каторларига Г нинг кирраларини мос куямиз. У
холда
1, агар ерсирра ау. тугунга кушма булса. 0, акс холДа.
ёоидадан фойдаданиб ёоешмалик матрицасини косил биламиз. Мисол.
I -расм
Агар Г йУналтирилган граф булса, у холда
1, агар а — тугун еј — кирранинг бошланиши булса .
агар а — тугун — кирранинг охири булса .
AiJ 0, агар а . — тугун — киррага кушма булмаса .
2, агар а ] — тугун сиртмок булиб киррага кушма булса .
фойдаданиб доешмалик матрицасини Косил
диламиз.
Мисол.
|
аз а4 а5 аб а7
|
|
-1 1 1
|
|
0
|
е2
|
-1 0
|
|
0 0
|
ез
|
|
О
|
О О
|
|
0 о -1
|
1
|
|
|
0 0 -1
|
|
1
|
е6
|
О
|
1
|
|
|
0
|
о О
|
2
|
2 -расм
2.3 Кушнилик матрицаси. Фараз килайлик Г граф йУналтирилмаган булсин. Графнинг КУШНИЛИК матрицасида Aij нинг устунларига хам каторларига хам графнинг тугунларини мос куямиз. У холда
1, агар а г ва а тугунлар кушни булса
0, акс холДа фойдаданиб доешнилик матрицасини Косил
Мисол. 1-расмда келтирилган йУналтирилмаган граф учун матрицаси ёуйидагича боелади.
|
al а2 аз а4а5 аб а7
|
|
|
0 0
|
а2
|
|
1 0
|
аз
|
1 0 0 1
|
|
|
0 1 1 0
|
1 0
|
а5
|
1 0 1 0
|
|
|
0 1 0 1
|
|
|
0 0 0 0 1
|
1 0
|
Г йУналтирилган граф булсин. У холда кушнилик матрицаси Aij нинг устунларига хам сатрларига хам графнинг тугунларини мос куямиз. Ухолда
1, тугун а. тугунинг бошланиши булса
0, агар q тугунај тугунга кушни булмаса вад тугуна тугунинг
ОХИРИ булса доидадан фойдаданиб матрицасини Косил диламиз.
Мисол. 2-расмда келтирилган йУналтирилган граф учун дсшнилик матрицаси дуйидагича бслади.
|
|
а1 а2 аз а4 а5 аб а7
|
|
0 0 0 0
|
а2
|
0 0 0
|
аз
|
0 0 0 0 1 1 1
|
|
0 0 0 0 0 0 0
|
|
0 0 0 0 0 0 0
|
|
0 0 0 0 0 0 0
|
а7
|
0 0 0 0 0 0 1
|
Теорема. Агар графда каррали кирралари хамда сиртмок мавжуд булмаса, п та тугунга эга бУлган ва боглик компонентаси К га тенг бУлган графнинг кирралари сони энг купи билан аниёланади.
Машрутнинг узунлиги деб, шу маршрутда мавжуд кушни (ei-l, е) кирралар сонига айтилади.
Графнинг ихтиёрий а ва ихтиёрий в тугунлари орасидаги масофа деб, шу тугунларни богловчи энг кичик узунлика эга булган занжирга айтилади.
а2 е] аз
М исол.
(eo, el )=2; e2)=2;
AHarvreTPH ae6, 3Hr Karra Y3YHJIHKKa 3ra
6YnraH aiTHJ1aAH.
d(F) = max a,geV
MHC0J1. el, e3)=3.
c rryryH r TyryHH 6YJICHH. x 3ca
TyryHH 6YJICHH. C TYIYH yqyH MaKCVIMaJ1 xmc06naMMH3. Km-Inaünvmp co TYIYH YI-IYH 6y
MaKCHMaJ1 60111Ka TyryHJ1apra HHC6aTaH MHHHMUI 6Ynca, yxonna CO r Mapl€a3H neiHJ1aÅH Ba CO yqyH aHHKJ1aHraH r pannycvr neiHJ1aÅH.
2 5
R(c) = min 18
c,xev
4 7
Бу мисолда марказ З ёки 6 тугунлар булиши мумкин, чунки r(c)=2.
2.4 Эйлер графи. Бизга йУналтирилмаган Г граф берилган булсин. Эйлер цикли шундай циклки, унда графнинг маълум бир тугунидан чикиб, барча кирралардан факат бир марта утиб, яна шу тугунга кайтиб келиши керак. Графда Эйлер цикли мавжуд булиши учун:
а) Граф богланган бУлиши;
б) Графнинг барча тугунларининг локал даражалари жуфт боелиши керак;
Графда Эйлер занжири мавжуд боелиши учун:
а) Граф богланган бУлиши;
б) Графнинг 2 та тугуни(бошланиш ва охирги) локал даражалари тод боелиб, долган барча тугунларининг локал даражалари жуфт боелиши керак.
Агар Г йУналтирилмаган графда Эйлер цикли мавжуд булса, бундай графга Эйлер графи дейилади.
Мисол.
p(q) = 4; р(а2) = 2; р(аз) = 2; Да) =4;
2.5 Гамильтон графи. Агар графда оддий цикл мавжуд
булиб, бу циклда графнинг барча тугунлари катнашса, бундай цикл Гамильтон цикли дейилади.
Оддий занжир Гамилтон занжири дейилади, агар бундай графда тугунларнинг хаммаси иштирок этса. Тугун ва кирралар такрорланмаслиги керак.
Графда Гамильтон цикли мавжуд булса, бу граф
Гамильтон графи дейилади.
Мисол.
а2 el аз
al
Бу графда оддий цикл ео, el, е4 е5, еф
Гамильтон цикли, ео, el, еъ еб) - Гамильтон цикли эмас, чунки а5 тугун катнашмаяпти.
|
| |
