Yo'naltirilmagan ulangan graf deb nomlanadi. Agar graf ulangan bo'lsa, lekin bu shart bajarilmasa, unda bunday graf yo'naltirilgan

Bir nechta misollar grafning yuzaki ko'rinishini beradi. Shunday qilib, odatiy graf bu metro xaritasi yoki boshqa yo'nalish. Xususan, kompyuter tarmog'I ham bizlarga graf haqidagi ma’lumotni beradi. Bu yerda keng tarqalgan - chiziqlar bilan bog'langan nuqtalarning mavjudligi. Shunday qilib, kompyuter tarmog'ida ulangan kompyuterlar va tarmoq kabellari grafni tashkil qiladi. Metroda birinchi stansiyalar, ikkinchisida ular o'rtasida tunnellar yotqizilgan. Graflar nazariyasida nuqta uchlari (tugunlar), chiziqlar esa qirralar (yoylar) deb nomlanadi. Shunday qilib, graf qirralarning bog'langan uchlari to'plamidir.

Kompyuter tarmog'iga qaytish. U ma'lum bir topologiyaga ega va ular bilan bir qator kompyuterlar va ularni bog'laydigan yo'llar sifatida tasvirlash mumkin. Quyidagi rasm misol sifatida to'liq bog'liq topologiyani ko'rsatadi.

• 
  Beshta kompyuter uchlari va ular orasidagi ulanishlar (signal uzatish yo'llari) chekka. Kompyuterlarni uchlari bilan almashtirsak, biz matematik ob'ektni olamiz - 10 qirralari va 5 uchlari bo'lgan grafik. Uchlardagi raqamlarni boshqalar bilan raqamlash mumkin va bu rasmda ko'rsatilgandek shart emas.
  

Graflar nazariyasida ishlatiladigan ba'zi muhim eslatmalar:
• G = (V, E), bu yerda G - graf, V - uning uchlari, E - qirralar;
• | V | - nuqtalar (qirralarning soni);
• | E | - yoylar (tomonlar soni).
Bizning holatda (1-rasm) | V | = 5, | E | = 10;
Boshqa har qanday uchdan har qanday uchga kirish imkoni mavjud bo'lganda, bunday graf yo'naltirilmagan ulangan graf deb nomlanadi.
Agar graf ulangan bo'lsa, lekin bu shart bajarilmasa, unda bunday graf yo'naltirilgan deb nomlanadi.

Yo'naltirilgan va yo'naltirilmagan graflar uch darajasi tushunchasiga ega. Bir uchning darajasi - uni boshqa uchlarga bog'laydigan qirralarning soni. Grafning barcha darajalari yig'indisi uning barcha qirralarining ikki baravariga teng. 2-rasm uchun barcha darajalarning yig'indisi 20 ga teng.

Rasmda, yo'naltirilmagan grafdan farqli o'laroq, chekka h dan chiqib, s ga kirganda, lekin aksincha emas, balki h uch dan s ga o'tish mumkin.
Yo'naltirilgan graflar quyidagi belgilarga ega:
G = (V, A), bu erda V uchlari, A yo'naltirilgan qirralar.
Grafning uchinchi turi aralash grafdir (3-rasm). Ular ikkala yo'naltirilgan va yo'naltirilmagan qirralarga ega. Rasmiy aralash graf quyidagicha yoziladi: G = (V, E, A), bu erda qavs ichidagi harflarning har biri ilgari unga bog'langan narsalarni ham anglatadi.
3-rasmdagi grafda ba'zi bir yoylar
[(e, a), (e, c), (a, b), (c, a), (d, b)],
boshqalari yo'naltirilmagan
[(e, d), (e, b), (d, c) ...].

• 
  Ajrat bosqichi. Bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi.
  
• 
  Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.
  
• 
  Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo’ladi.
  

Shu sababli, bo’lib tashla hukmronlik qil paradigmasini 3 ta jumla bilan eslab qolish mumkin: ajrat, hukmronlik qil, birlashtir.


Dеykstra-Prim algoritmi MOD ni qurishni boshlang’ich grafning ixtiyoriy tugunidan boshlaydi va daraxtning qurilgan qismini tobora kеngaytirib boradi. Ushbu algoritmdan farqli ravishda Kruskal algoritmi asosiy e'tiborni graf tomonlariga qaratadi. Bunda ishni bo’sh grafdan boshlab, unga tomonlarini ular vaznining o’sib borish tartibida kеtma-kеt qo’shib boradi. Bu jarayon grafga kiruvchi barcha tugunlar o’zaro bog’langunga qadar davom etadi. Agar tomonlarni qo’shib olish jarayoni barcha tugunlar o’zaro bog’langunga qadar tugatilsa, boshlan?ich grafning to’liq bog’lanmagan ekanligi kеlib chiqadi. Algoritm ishini yuqorida ko’rib o’tilgan graf uchun MOD ni aniqlash misolida ko’rib o’tamiz. Ishni eng kichik vaznli DF tomondan boshlaymiz. Boshlang’ich garf v rasmda ifodalangan. Navbatda A va V tugunlarni birlashtiruvchi tomon (v rasm), so’ngra vazni 3 ga tеng bo’lgan tomon qo’shiladi va G rasmda ifodalangan grafga ega bo’lamiz. Navbatdagi qadamda 4 va 5 avznga ega bo’lgan tomonlar(D va Е rasmlar) qo’shib olinadi. Natijada qo’shilmagan faqat G tugun qoladi. Kеyingi qadamda vazni 6 ga tеng tomonlarni qayta ishlash kеrak bo’ladi.