Axborot tizimlari va texnologiyalari

6-mavzu: Yo’naltirilgan va yo’naltirilmagan graflar
Reja:

1. Graflar nazariyasi

2. Yo'naltirilgan va yo'naltirilmagan grafiklar

Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler 
tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan
Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. 
Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar 
joylashuvi 1-shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 
5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini
o‘sha davrda to‘rtta A, B, C va D qismlarga bo‘lgan. Shaharning ixtiyoriy
qismida joylashgan uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida
Kyonigsberg (Königsberg) – bu shahar 1255 yilda asoslangan bo‘lib, Sharqiy Prussiyadagi Pregel daryosi qirg‘oqlarida joylashgan. 1946 yildan boshlab 
Kaliningrad, hozir Rossiya Federatsiyasi tarkibida. 

marshrut Eyler sikli nomi bilan yuritiladi, ushbu bobning 5- paragrafiga qarang) 

mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy
ishning birinchi sahifasi 
2-shaklda keltirilgan. L. Eylerning bu maqolasi yuz yildan ko‘p vaqt 
mobaynida graflar nazariyasi bo‘yicha yagona ilmiy ish bo‘lib keldi. 

Qulay grafika

Hisoblash mitti deyiladi Agar uning verislarining to'plami ikkita pastki qismga bo'linsa, bu er ostidagi vertikallarning uchlarini bog'lab bo'lmaydi.
1-misol.Qurmoq to'la Fedromar grafi.
To'liq bipolyy grafigi yana bir to'plamning tepalari bilan bog'langan har xil havolalar va har xil havolalardan iborat (quyida keltirilgan rasm).