Grafik vertikal va qirralardan iborat. Tepaliklar ma'lum bir xususiyatga ko'ra qirralar bilan bog'langan - qirralarning to'plamini belgilaydigan tushish munosabati. Bunday holda, ilmoqlar va izolyatsiya qilingan tepalar paydo bo'lishi mumkin.
Ko'rsatmalar
1-qadam
Grafik qirralarining to'plami berilsin va bir tepadan ikkinchisiga chekka chizish mumkin bo'lgan munosabatlar berilgan. Masalan, {1, 2, 3, 4, 5, 6, 7, 8} tepaliklar to'plami, ikkita tepalik x va y x + y <8 nisbatda.
2-qadam
Tepalikka ulashgan matritsani yarating. Buning uchun kvadrat jadval tuzing, jadvaldagi qatorlar va ustunlar soni tepalar soniga to'g'ri keladi. Keyin i va j tepalari berilgan nisbatni qondiradigan bo'lsa, i-chi satr va j-ustunning kesishmasiga 1 qo'ying. Agar mos keladigan elementlarning nisbati bajarilmasa, i-chi satr va j-ustunning kesishmasiga 0 qo'ying.
Bizning misolimizda birinchi satr quyidagicha to'ldirilgan:
1 + 1 <8, shuning uchun 1-qator va 1-ustun chorrahasida 1 bo'ladi
1 + 2 <8, yana 1
1 + 3 <8, yana 1
1 + 7 <8, noto'g'ri tengsizlik, shuning uchun jadvalning ushbu elementi 0 ga teng bo'ladi
1 + 8 <8, yana 0
3-qadam
Qirralarning sonini bilish uchun chekkalarini takrorlamasdan qo'shni matritsadagi sonlarini hisoblang.
Misolda nosimmetrik matritsa olingan, shuning uchun avval matritsaning asosiy diagonalidan yuqorisini (ko'k bilan belgilangan), so'ngra asosiy diagonalidan (qizil bilan belgilangan) sanadik. Umumiy qovurg'alar soni 12 ta.
4-qadam
Voqealar matritsasini (qirralarini) yarating. Buning uchun jadval chizamiz, undagi qatorlar soni grafadagi tepalar soniga, ustunlar soni qirralarning soniga teng. Chegaralar bilan bog'lanadigan chiziqlarga birliklarni qo'ying. Tepalikdan unga olib boruvchi qirralar halqalar deb nomlanadi va matritsaning oxiriga qo'shiladi. Ichaklarga mos keladigan ustunlarda, qolgan qirralardan farqli o'laroq, faqat bitta birlik mavjud.
5-qadam
Endi grafik chizish. Qanday qilib vertikallarni qog'ozga qo'ying va qurilgan jadvallar yordamida ularni qirralar bilan ulang. Qirralar bilan bog'lanmagan vertikallar ajratilgan deb nomlanadi.
