Eng kata daraxt,eng qisqa va eng uzun yo’l Reja

2- m i s о 1. 3- shaklda tasvirlangan graf sinchlaridan birining qirralari berilgan
grafning boshqa qirralariga qaraganda qalinroq chiziqlar vositasida ifodalangan. Endi G sirtmoqsiz va karrali qirralari bo‘lmagan m ta uch, n ta qirra va k ta bog‘lamli komponentlardan tashkil topgan graf bo‘lsin. Agar yuqorida tavsiflangan usul yordamida G grafdan qirralarni ketma-ket olib tashlash amalini qo‘llash natijasida uning har bir komponenti bog'lamliligi buzilmasa, u holda berilgan G grafning sinch o‘rmoni deb ataluvchi grafni hosil qilish mumkin.
Berilgan G grafdan uning sinch o‘rmonini hosil qilish maqsadida olib tashlanishi kerak bo‘lgan qirralar soni bu qirralarni olib tashlash tartibiga bog‘liq emasligi va bo‘lishi ravshandir.
Qaralayotgan G graf uchun m — k < n tengsizlik o‘rinli bo‘lganligidan, bo'ladi. k{G) sonni G grafning siklomatik soni (siklik rangi) deb ataymiz
Grafning siklomatik soni tushunchasi, qandaydir ma’noda, grafning bog'lamlilik darajasini aniqlovchi vositadir. Ravshanki, daraxt uchun bo‘ladi (1- teoremaga qarang).
3- shakl Grafning o ‘rmon bo‘lishi uchun uning siklomatik soni nolga teng bo‘lishi zarur va yetarlidir (2- natijaga qarang). Grafning yagona siklga ega bo'lishi uchun uning siklomatik soni birga teng bo'lishi zarur va yetarlidir. Qirralari soni uchlari sonidan kichik bo‘lmagan graf siklga egadir. Bu tasdiqlar ham 1- teoremaning natijalaridir.
3- m i sol. 3- shaklda tasvirlangan graf (6 ,9 )-graf bo‘lib, uning bog‘lamlilik komponentlari soni birga teng. Bu grafning siklomatik sonini aniqlasak, A = 9 — 6 + 1 = 4 boiadi. Olib tashlangan qirralar 3- shaklda ingichka chiziqlar bilan ifodalangan.

XULOSA:
Xulosa,qilib aytganda daraxtlar nazariya va unga ekvivalent tushunchalar haqida va bundan tashqari eng uzun va eng qisqa daraxt haqida malumotlarga ega bo’ldim.
Unga bog’liq turli xil atamalar haqida, turli xil teoramalarni bilib oldim ,bundan tashqari teoremalarning isboti bilan ham tanishib chiqdim.Daraxtlar haqida amallar bajarish uni amaliyotda qo’llash va shu kabi malumotlar haqida tushunchaga ega bo’ldim.
Masala: A va B to’plam beriladi bu to’plamlarning ayirmasi va kesishmasini aniqlaydigan dastur tuzing.
Dastur kodi:


Dastur natijasi:

Foydalanilgan adabiyotlar:

1.. To ‘rayev H .T. Diskret matematikaning ribem etikaga tatbiqi. Muammoli lektsiyalar kursi. Samarkand, SamDU nashriyoti, 2003.
2.Alzarov T.A va boshqalar.Matematikadan qo’llanma 1990-y.352-bet.
3.T.To’rayev va I.Azizov Matemetik Mantiq va Diskret matematika II-jild. 2011-y,239-bet.