Yoʻn altirilgan va yoʻn altirilmagan grafik
Grafik - bu uchlari va qirralari toʻplamidan tashkil topgan matematik struktura. Grafik ba'zi bir havolalar (qirralar bilan ifodalangan) orqali bog'langan ob'ektlar to'plamini (cho'qqilar bilan ifodalangan) ifodalaydi. Matematik belgilar yordamida grafikni G bilan ifodalash mumkin, bunda G=(V, E) va V cho‘qqilar to‘plami, E esa qirralar to‘plamidir. Yo'n altirilmagan grafikda cho'qqilarni bog'laydigan qirralar bilan bog'langan yo'nalish yo'q. Yo'n altirilgan grafikda cho'qqilarni bog'laydigan qirralar bilan bog'langan yo'nalish mavjud.
Yo'n altirilmagan grafik
Avval aytib o'tganimizdek, yo'n altirilmagan grafik - bu grafikdagi cho'qqilarni bog'laydigan qirralarning yo'nalishi bo'lmagan grafik.1-rasmda V={V1, V2, V3} uchlari toʻplamiga ega boʻlgan yoʻn altirilmagan grafik tasvirlangan. Yuqoridagi grafikdagi qirralar to'plamini V={(V1, V2), (V2, V3), (V1, V3)} shaklida yozish mumkin. Shuni ham ta'kidlash mumkinki, qirralar to'plamini V={(V2, V1), (V3, V2), (V3, V1)} sifatida yozishga hech narsa to'sqinlik qilmaydi, chunki qirralarning yo'nalishi yo'q. Shuning uchun yo'n altirilmagan grafikdagi qirralar tartibli juftlar emas. Bu yo'n altirilmagan grafikning asosiy xarakteristikasi. Yo'n altirilmagan grafiklar cho'qqilar bilan ifodalangan ob'ektlar orasidagi simmetrik munosabatlarni ifodalash uchun ishlatilishi mumkin. Masalan, shaharlar to'plamini bog'laydigan ikki tomonlama yo'l tarmog'ini yo'n altirilmagan grafik yordamida tasvirlash mumkin. Shaharlar grafikdagi cho'qqilar bilan, chekkalari esa shaharlarni bog'laydigan ikki tomonlama yo'llarni ifodalaydi.
Yoʻn altirilgan grafik
Yo’n altirilgan grafik - bu grafikdagi cho’qqilarni bog’lovchi qirralari yo’nalishga ega bo’lgan grafik. 2-rasmda V={V1, V2, V3} uchlari to'plamiga ega bo'lgan yo'n altirilgan grafik tasvirlangan. Yuqoridagi grafikdagi qirralar to'plamini V={(V1, V2), (V2, V3), (V1, V3)} shaklida yozish mumkin. Yo'n altirilmagan grafikning qirralari tartiblangan juftliklardir. Rasmiy ravishda yo'n altirilgan grafikdagi e chekkasi tartiblangan juft e=(x, y) bilan ifodalanishi mumkin, bu erda x - e chekkasining boshlang'ich nuqtasi, manbai yoki boshlang'ich nuqtasi deb ataladigan cho'qqi, y tepasi esa oxiri deb ataladi., tugatish cho'qqisi yoki terminal nuqtasi. Masalan, bir tomonlama yo'llar yordamida shaharlar to'plamini bog'laydigan yo'l tarmog'i yo'n altirilmagan grafik yordamida tasvirlanishi mumkin. Shaharlar grafikdagi cho'qqilar bilan ifodalanishi mumkin, yo'n altirilgan qirralar esa yo'lda harakatlanish yo'nalishini hisobga olgan holda shaharlarni bog'laydigan yo'llarni ifodalaydi.
Yo'n altirilgan grafik va yo'n altirilmagan grafik o'rtasidagi farq nima?
Yo’n altirilgan grafikda chekka tartiblangan juftlik bo’lib, bunda tartiblangan juftlik ikki cho’qqini bog’laydigan chekka yo’nalishini ifodalaydi. Boshqa tomondan, yo'n altirilmagan grafikda chekka tartibsiz juftlikdir, chunki chekka bilan bog'liq yo'nalish yo'q. Yo'n altirilmagan grafiklar ob'ektlar orasidagi simmetrik munosabatlarni ifodalash uchun ishlatilishi mumkin. Yo'n altirilmagan grafikdagi har bir tugunning daraja va tashqi darajalari teng, ammo bu yo'n altirilgan grafik uchun to'g'ri emas. Yo'n altirilmagan grafikni ifodalash uchun matritsadan foydalanilganda, matritsa har doim simmetrik grafikga aylanadi, ammo bu yo'n altirilgan grafiklar uchun to'g'ri kelmaydi. Yo'n altirilmagan grafikni har bir chekkani qarama-qarshi yo'nalishda ketadigan ikkita yo'n altirilgan qirralar bilan almashtirish orqali yo'n altirilgan grafikga aylantirish mumkin. Biroq, yo‘n altirilgan grafikni yo‘n altirilmagan grafikga aylantirish mumkin emas.
