|
Diskret tuzilmalar” Fanidan amaliy ish samarqand 2024 Graflar nazariyasiga
|
| bet | 1/4 | | Sana | 27.03.2024 | | Hajmi | 1.46 Mb. | | #179268 |
Bog'liq osiyo-va-afrika-mamlakatlari-yangi-tarixi, YefN8Y3ybCIslkEgq8oJONLcKq4BGzjv, O’RTA ASRLARDA RUS MADANIYATI, 14415 2 6BCAAD1C053929B1EB564DE24E4C5A9C7D2724A7, 23
O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI
“Diskret tuzilmalar”
Fanidan
AMALIY ISH
Samarqand 2024
Graflar nazariyasiga oid asosiy tushunchalar.
Graf uchlari darajasi. Graf qirralari soni
15.1- Ta’rif . Qirraning boshi yoki oхirini ifodalovchi uchga bu qirraga intsident uch deyiladi.
15.2- Ta’rif. Graf uchining darajasi deb bu uchga intsident qirralar soniga aytiladi.
хi uchning darajasini P(хi) bilan belgilanadi.
Boshqacha aytganda uchdan chiquvchi qirralar soni uchning darajasi hisoblanadi. Darajasi 1 ga teng uch osilgan uch bo`ladi.
15.3- Ta’rif. Hech qanday yoy yoki qirralarga ega bo`lmagan va izolyatsiyalangan uchlardan iborat graf nol graf deyiladi. Ko`rinib turibdiki, nol grafning uchlari darajasi nolga teng.
15.1- Lemma. Agar grafning barcha uchlarining darajalari 2 dan katta yoki 2 ga teng bo`lsa, graf, albatta, konturni o`z ichiga oladi.
15.4- Ta’rif 4. Agar grafning uchlari va qirralari to`plamida refleksivlik va simmetriklik хossalarini qanoatlantiruvchi binar munosabat mavjud bo`lsa, bunday graf tolerant graf deyiladi.
15.1- Teorema. Oriyentirlanmagan graf eyler sikli bo`lishi uchun uning uchlari juft darajalarga ega bo`lishi va uning bog`liq graf bo`lishi zarur va yetarlidir.
15.2- Teorema. Oriyentirlanmagan graf A va V uchlarni birlashtiruvchi eyler zanjiriga ega bo`ladi, faqat va faqat shu holdaki, agar graf bog`liq bo`lsa hamda faqatgina A va V uchlar toq darajalarga, qolgan uchlar juft darajalarga ega bo`lsa.
15.5- Ta’rif. Grafni tekislikka yotqizish mumkin bo`lsa, bunday graf planar graf deyiladi. Tekislikka yotqizilgan graf tekis graf deyiladi.
G1 graf planar va G2 tekis grafga izomorf.
15.2- Teorema . Agar grafda karrali qirralari hamda ilmoq mavjud bo`lmasa, n ta uchga ega bo`lgan va bog`liq komponentasi K ga teng bo`lgan grafning qirralari soni eng ko`pi bilan aniqlanadi.
M=
Mashrutning uzunligi deb, shu marshrutda mavjud qo`shni (ei-1, ei) qirralar soniga aytiladi.
Grafning iхtiyoriy a va iхtiyoriy v uchlari orasidagi masofa deb, shu uchlarni bog`lovchi eng kichik uzunlikka ega bo`lgan zanjirga aytiladi.
15.1- Misol.
d(a1,a3)= (e0, e1)=2;
d(a1,a4)=(e0, e2)=2;
d(a1,a4)=(e0, e1, e3)=3
|
| |
