Iloji boricha to'liq grafik tuzing. Xususiyatlari asosida grafiklar tuzish

Grafik nazariyasi- diskret matematikaning iqtisodiy va boshqaruv masalalarini hal qilishda, dasturlash, kimyo, elektr zanjirlarini loyihalash va o'rganish, aloqa, psixologiya, psixologiya, sotsiologiya, tilshunoslik va boshqa bilim sohalarida keng qo'llaniladigan eng keng tarqalgan bo'limlaridan biri. Grafik nazariyasi nuqtalar to‘plamidan va shu nuqtalar orasidagi bog‘lanishlarni ifodalovchi chiziqlar to‘plamidan iborat deyish mumkin bo‘lgan grafiklarning xossalarini tizimli va izchil o‘rganadi. Grafiklar nazariyasining asoschisi Leonhard Eyler (1707-1882) hisoblanadi, u 1736 yilda o'sha paytdagi taniqli Kenigsberg ko'prigi muammosini hal qilgan.

Grafiklar qurilgan to'plamlarda munosabatlarni ko'rsatish uchun. Misol uchun, to'plam bo'lsin A = {a1 , a 2 , ... a n)- juda ko'p odamlar va har bir element nuqta sifatida ko'rsatiladi. Bir guruh B = {b1 , b 2 , ... b m)- ko'plab ulanishlar (to'g'ri chiziqlar, yoylar, segmentlar - bu hali muhim emas). To'plamda A bu to'plamdan odamlar o'rtasidagi tanishuv munosabatlari berilgan. Grafik yaratish nuqta va bog‘lovchilardan. Havolalar bir-birini biladigan juftliklarni bog'laydi. Tabiiyki, ba'zi odamlarning tanishlari soni boshqa odamlarning tanishlari sonidan farq qilishi mumkin, ba'zilari esa hech kimni tanimasligi mumkin (bunday elementlar boshqasiga bog'liq bo'lmagan nuqtalar bo'ladi). Shunday qilib, bizda grafik bor!

Biz birinchi marta "nuqtalar" deb atagan narsalarni grafikning cho'qqilari deb atash kerak va biz "bog'lanish" deb atagan narsalarni grafik qirralari deb atash kerak.

Grafik nazariyasi to'plamlarning o'ziga xos xususiyatini hisobga olmaydi A Va B. Juda ko'p turli xil o'ziga xos muammolar mavjud, ularni hal qilishda to'plamlarning o'ziga xos tarkibi va ularning elementlarini vaqtincha unutish mumkin. Ushbu o'ziga xoslik, uning qiyinligidan qat'i nazar, muammoni hal qilish jarayoniga hech qanday ta'sir ko'rsatmaydi! Misol uchun, bir nuqtadan mumkinmi yoki yo'qligini hal qilishda a nuqtaga keling e, faqat nuqtalarni bog'laydigan chiziqlar bo'ylab harakatlanayotganda, biz odamlar, shaharlar, raqamlar va boshqalar bilan shug'ullanamizmi, muhim emas. Ammo, muammo hal qilinganda, biz grafik sifatida modellashtirilgan har qanday tarkib uchun to'g'ri bo'lgan yechimni olamiz. Shuning uchun grafik nazariyasi sun'iy intellektni yaratishda eng mashhur vositalardan biri ekanligi ajablanarli emas: sun'iy intellekt suhbatdoshi bilan sevgi, musiqa yoki sport masalalari va turli muammolarni hal qilish masalalarini muhokama qilishi mumkin. , va buni hech qanday o'tish (o'tish)siz amalga oshiradi , bu holda odam bunday hollarda qilolmaydi.

Va endi grafikning qat'iy matematik ta'riflari.

Ta'rif 1.U grafik deb ataladi ixtiyoriy tabiatdagi ob'ektlar tizimi (cho'qqilar) va ushbu ob'ektlarning ba'zi juftlarini bog'lovchi zvenolar (qirralar).

Ta'rif 2. Mayli V– (bo‘sh bo‘lmagan) cho‘qqilar, elementlar to‘plami v∈V- cho'qqilar. Grafik G = G(V) ko'p uchlari bilan V shaklning ma'lum bir juftlik oilasi mavjud: e = (a, b) , Qayerda a,b∈V , qaysi uchlari bog'langanligini ko'rsatadi. Har bir juftlik e = (a, b) - grafikning cheti. Bir guruh U- ko'p qirralar e grafik. Cho'qqilar a Va b– chekkaning oxirgi nuqtalari e .

Grafiklar ma'lumotlar strukturasi sifatida. Grafiklar nazariyasining informatika va axborot texnologiyalarida keng qo‘llanilishi yuqoridagi ta’riflarga ma’lumotlar strukturasi sifatida grafik tushunchasining qo‘shilishi bilan bog‘liq. Informatika va axborot texnologiyalarida grafik chiziqli bo'lmagan ma'lumotlar strukturasi sifatida aniqlanadi. Chiziqli ma'lumotlar strukturasi nima va grafiklar ulardan qanday farq qiladi? Chiziqli ma'lumotlar tuzilmalari elementlarni "oddiy qo'shnichilik" tipidagi munosabatlar orqali bog'lashi bilan tavsiflanadi. Chiziqli ma'lumotlar tuzilmalari, masalan, massivlar, jadvallar, ro'yxatlar, navbatlar, steklar, satrlardir. Bundan farqli o'laroq, chiziqli bo'lmagan ma'lumotlar tuzilmalari - bu elementlar ierarxiyaning turli darajalarida joylashgan va uch turga bo'lingan: original, yaratilgan va shunga o'xshash. Demak, grafik chiziqli bo'lmagan ma'lumotlar strukturasidir.

Grafik so'zi yunoncha "yozaman", "tasvirlayman" so'zlaridan kelib chiqqan. Ushbu maqolaning boshidan biz grafik aniq nimani tasvirlashini bilamiz: u munosabatlarni tasvirlaydi. Ya'ni, har qanday grafik munosabatlarni tasvirlaydi. Va aksincha: har qanday munosabatni grafik sifatida tasvirlash mumkin.

Grafiklar nazariyasining asosiy tushunchalari

Insidans tushunchasi grafiklar bilan ko'plab amaliy masalalarni echish algoritmlarini ishlab chiqishda ham zarurdir. Misol uchun, siz dasturiy ta'minotni amalga oshirish bilan tanishishingiz mumkin insidans matritsasi bilan ifodalangan grafikning chuqurlik-birinchi o'tishi. Fikr oddiy: siz faqat qirralar bilan bog'langan cho'qqilar orqali harakat qilishingiz mumkin. Va agar qirralarga ba'zi qiymatlar tayinlangan bo'lsa ("tarozi", ko'pincha raqamlar ko'rinishida, bunday grafiklar vaznli yoki etiketli deb ataladi), unda murakkab amaliy muammolarni hal qilish mumkin, ularning ba'zilari oxirgi xatboshida eslatib o'tilgan. ushbu darsdan.

Grafiklar nazariyasining klassik muammolari va ularning yechimlari

Grafiklar nazariyasi va grafiklarni qo'llash bo'yicha ishlarning birinchi nashr etilgan namunalaridan biri 18-asrning taniqli matematigi Leonhard Eyler tomonidan yozilgan "Königsberg ko'prigi muammosi" (1736) bo'yicha ishdir. Muammo daryo, bu daryo tomonidan yuvilgan orollar va bir nechta ko'priklarni o'z ichiga oladi. Muammoning savoli: ma'lum bir nuqtadan chiqqandan keyin har bir ko'prikdan faqat bir marta o'tib, boshlang'ich nuqtasiga qaytish mumkinmi? (pastdagi rasm)

Muammoni quyidagicha modellashtirish mumkin: har bir quruqlik maydoniga bitta nuqta biriktirilgan va ikkita nuqta chiziq bilan bog'langan, agar tegishli er uchastkalari ko'prik bilan bog'langan bo'lsa (quyidagi rasm, tutashtiruvchi chiziqlar nuqtali chiziqlar bilan chizilgan) . Shunday qilib, grafik tuziladi.

Muammoli savolga Eylerning javobi quyidagicha. Agar bu masala ijobiy yechimga ega bo'lsa, natijada olingan grafikda qirralar bo'ylab o'tadigan va har bir chekka faqat bir marta o'z ichiga olgan yopiq yo'l bo'ladi. Agar shunday yo'l mavjud bo'lsa, unda har bir cho'qqi faqat juft sonli qirralarga ega bo'lishi kerak. Ammo natijada olingan grafikda toq sonli qirralarga ega bo'lgan uchlari mavjud. Shuning uchun muammo ijobiy yechimga ega emas.

O'rnatilgan an'anaga ko'ra, Eyler grafigi - bu barcha cho'qqilarni kesib o'tish va bir vaqtning o'zida bir chekkadan faqat bir marta o'tish mumkin bo'lgan grafik. Unda har bir cho'qqi faqat juft sonli qirralarga ega bo'lishi kerak. Eyler grafiklari bo'yicha o'rtacha qiyinchilik muammosi "Grafiklarning asosiy turlari" materialida.

1847 yilda Kirxgof chiziqli algebraik tenglamalarning bir vaqtning o'zida tizimini echish uchun daraxtlar nazariyasini ishlab chiqdi, bu har bir o'tkazgichda (yoyda) va elektr zanjirining har bir pallasida tokning qiymatini topish imkonini beradi. Qarshilik, kondansatör, indüktans va hokazolarni o'z ichiga olgan elektr zanjirlari va zanjirlaridan ajratib, u faqat tepaliklar va ulanishlarni (qirralar yoki yoylar) o'z ichiga olgan mos keladigan kombinatsion tuzilmalarni ko'rib chiqdi va ulanishlar uchun qanday turdagi elektr elementlarni hisobga olishning hojati yo'q. ga mos keladi. Shunday qilib, Kirchhoff har bir elektr zanjirini mos keladigan grafik bilan almashtirdi va tenglamalar tizimini echish uchun elektr zanjiri grafigining har bir tsiklini alohida ko'rib chiqish kerak emasligini ko'rsatdi.

Kayli 1858 yilda organik kimyoda sof amaliy masalalar ustida ishlaganda, daraxtlar deb ataladigan muhim grafik sinfini kashf etdi. U to'yingan uglevodorodlarning ma'lum miqdordagi uglerod atomlari bilan izomerlarini sanab o'tishga harakat qildi. Cayley birinchi navbatda muammoni mavhum shaklda tuzdi: barcha daraxtlar sonini toping p U har birining 1 va 4 darajali cho'qqilariga ega. U bu masalani darhol hal qila olmadi va uning formulasini shunday o'zgartira boshladiki, yangi sanash masalasini hal qilish mumkin bo'ladi:

ildiz otgan daraxtlar (uning cho'qqilaridan biri tanlangan);
barcha daraxtlar;
tepalik darajalari 4 dan oshmaydigan daraxtlar;
tepalik darajalari 1 va 4 bo'lgan daraxtlar (kimyodan masala bayoni).

Asosiy tushunchalarni mustahkamlash uchun grafik masalalar

1-misol. Mayli A- 1, 2, 3 raqamlar to'plami: A= (1, 2, 3) . O'zaro munosabatlarni ko'rsatish uchun grafik tuzing "

Yechim. Shubhasiz, 1, 2, 3 raqamlari grafikning uchlari sifatida ifodalanishi kerak. Keyin har bir juft cho'qqi bir chekka bilan bog'langan bo'lishi kerak. Ushbu muammoni hal qilish orqali biz grafik nazariyasining asosiy tushunchalariga keldik yo'naltirilgan va yo'naltirilmagan grafiklar. Yo'naltirilmagan grafiklar qirralari yo'nalishi bo'lmagan grafiklardir. Yoki, ular tez-tez aytganidek, chekkaning ikki uchining tartibi muhim emas. Darhaqiqat, ushbu darsning boshida tuzilgan va odamlar o'rtasidagi tanishuv munosabatlarini aks ettiruvchi grafik chekka yo'nalishlarga muhtoj emas, chunki "1-raqamli shaxs" "2-raqamli shaxs" bilan bir xil darajada tanish, deb bahslashish mumkin. "1-sonli shaxs" bilan "2-sonli shaxs" sifatida. Hozirgi misolimizda bitta raqam boshqasidan kichik, lekin aksincha emas. Shuning uchun, grafikning mos keladigan chekkasi qaysi raqam boshqasidan kichik ekanligini ko'rsatadigan yo'nalishga ega bo'lishi kerak. Ya'ni, chekka uchlari tartibi muhim. Bunday grafik (qirralari yo'nalishga ega) yo'naltirilgan grafik yoki digraf deb ataladi.

Shunday qilib, bizning ko'pchiligimizda A 1-raqam 2-raqam va 3-raqamdan kichik, 2-raqam esa 3-raqamdan kichikdir. Biz quyidagi grafikni olamiz:

2-misol. Mayli A- 2, 4, 6, 14 raqamlar to'plami: A= (2, 4, 6, 14) . Ushbu to‘plamdagi “bo‘linish” munosabatini ko‘rsatish uchun grafik tuzing.

Yechim. Bu misolda ba'zi qirralarning yo'nalishi bo'ladi, ba'zilari esa yo'q, ya'ni biz qurmoqdamiz aralash grafik. To'plamdagi munosabatlarni sanab o'tamiz: 4 2 ga, 6 2 ga, 14 2 ga bo'linadi va bu to'plamdagi har bir son o'ziga bo'linadi. Bu munosabat, ya'ni son o'z-o'zidan bo'linadigan bo'lsa, cho'qqini o'zi bilan bog'laydigan qirralar ko'rinishida ko'rsatiladi. Bunday qirralar deyiladi halqalar. Bunday holda, pastadirga yo'nalish berishning hojati yo'q. Shunday qilib, bizning misolimizda uchta muntazam yo'naltirilgan qirralar va to'rtta halqa mavjud. Biz quyidagi grafikni olamiz:

3-misol. Berilgan to'plamlarga ruxsat bering A= (a, b, g) va B= (a, b, c) . “To‘plamlarning kartezian mahsuloti” munosabatini ko‘rsatish uchun grafik tuzing.

Yechim. Ta'rifdan ma'lumki To'plamlarning dekart mahsuloti, bir xil to'plam elementlarining tartiblangan to'plamlari mavjud emas. Ya'ni, bizning misolimizda siz yunoncha harflarni yunoncha va lotinni lotin bilan birlashtira olmaysiz. Bu fakt sifatida ko'rsatiladi ikki tomonlama grafik, ya'ni bir qismga tegishli bo'lgan uchlari bir-biriga bog'lanmasligi uchun uchlari ikki qismga bo'lingan. Biz quyidagi grafikni olamiz:

4-misol. Ko'chmas mulk agentligida menejerlar Igor, Sergey va Piter ishlaydi. O1, O2, O3, O4, O5, O6, O7, O8 obyektlariga xizmat koʻrsatiladi. "Igor O4, O7 ob'ektlari bilan ishlaydi", "Sergey O1, O2, O3, O5, O6 ob'ektlari bilan ishlaydi", "Piter O8 ob'ekti bilan ishlaydi" munosabatlarini aks ettirish uchun grafik tuzing.

Yechim. Ushbu munosabatlarni aks ettiruvchi grafik ham ikki tomonlama bo'ladi, chunki menejer menejer bilan ishlamaydi va ob'ekt ob'ekt bilan ishlamaydi. Biroq, oldingi misoldan farqli o'laroq, grafik yo'naltiriladi. Aslida, masalan, Igor O4 ob'ekti bilan ishlaydi, lekin O4 ob'ekti Igor bilan ishlamaydi. Ko'pincha, munosabatlarning bunday xususiyati aniq bo'lsa, qirralarga yo'nalish berish zarurati "matematik ahmoqlik" kabi ko'rinishi mumkin. Ammo baribir, va bu matematikaning qat'iy tabiatidan kelib chiqadi, agar munosabatlar bir tomonlama bo'lsa, unda qirralarga yo'nalish berish kerak. Relyatsion ilovalarda bu qat'iylik, masalan, rejalashtirish uchun mo'ljallangan dasturlarda to'lanadi, bu erda grafiklar ham qo'llaniladi va cho'qqilar va qirralar bo'ylab marshrut qat'iy ma'lum bir yo'nalishda o'tishi kerak. Shunday qilib, biz quyidagi yo'naltirilgan ikki tomonlama grafikni olamiz:

Va yana raqamlar bilan misollar uchun.

5-misol. To'plam berilsin C = {2, 3, 5, 6, 15, 18} . Barcha son juftlarini aniqlovchi munosabatni amalga oshiradigan grafik tuzing a Va b ko'pchilikdan C, bunda ikkinchi elementni birinchisiga bo'lishda biz 1 dan katta butun son bo'lgan qismni olamiz.

Yechim. Ushbu munosabatlarni aks ettiruvchi grafik yo'naltirilgan bo'ladi, chunki shart ikkinchi va birinchi elementlarning eslatmasini o'z ichiga oladi, ya'ni chekka birinchi elementdan ikkinchisiga yo'naltiriladi. Bundan qaysi element birinchi va qaysi element ikkinchi ekanligi aniq ko'rinadi. Keling, yana bir qancha terminologiyani qo'shamiz: yo'naltirilgan qirralar odatda yoylar deb ataladi. Grafikimizda 7 ta yoy bo'ladi: e1 = (3, 15) , e2 = (3, 18) , e3 = (5, 15) , e4 = (3, 6) , e5 = (2, 18) , e6 = (6, 18) , e7 = (2, 6) . Ushbu misolda grafikning qirralari (yoylari) oddiygina raqamlangan, ammo seriya raqamlari yoyga tayinlanishi mumkin bo'lgan yagona narsa emas. Yoyga shuningdek, masalan, yukni bir nuqtadan boshqasiga jo'natish narxini anglatuvchi tarozilar ham berilishi mumkin. Ammo biz kamon og'irliklari bilan keyinroq va batafsilroq tanishamiz. Shunday qilib, biz quyidagi yo'naltirilgan grafikni olamiz:

Nazariy kirish qismidan allaqachon ma'lumki, grafiklar nazariyasi to'plamlarning o'ziga xos xususiyatini hisobga olmaydi va xuddi shu grafik yordamida mazmuni juda xilma-xil bo'lgan to'plamlardagi munosabatlarni aniqlash mumkin. Ya'ni, vazifani modellashtirishda aynan shu tarkibni mavhumlash mumkin. Keling, grafiklar nazariyasining ushbu ajoyib xususiyatini ko'rsatadigan misollarga o'tamiz.

6-misol. 3 X 3 o'lchamdagi shaxmat taxtasi bo'lagida quyidagi rasmda ko'rsatilganidek, ikkita oq ritsarlar va ikkita qora ritsarlar joylashtirilgan.

Ritsarlarni quyidagi rasmda ko'rsatilgan holatga ko'chirish mumkinmi, ikkita bo'lak bir kvadratda bo'lolmasligini esdan chiqarmaydi?

Yechim. Tuzilgan grafikda cho'qqi juftlari "ritsar harakati" munosabati bilan bog'lanadi. Ya'ni, bir cho'qqi - ritsar ketgan, ikkinchisi - u kelgan va "r" harfining oraliq katakchasi bu munosabatdan tashqarida bo'ladi. Biz quyidagi grafikni olamiz:

Va shunga qaramay, dizayn noqulay bo'lib chiqdi. Unda shaxmat taxtasining kataklari ko'rinadi va grafikning ko'pgina qirralari kesishadi. Shaxmat taxtasining tashqi ko'rinishidan mavhum bo'lib, munosabatlarni soddaroq tasavvur qilish mumkinmi? Bu mumkin ekan. Yangi grafikda qo'shni cho'qqilar shaxmat taxtasida qo'shnilar emas, balki "ritsar harakati" munosabati bilan bog'langanlar bo'ladi (quyidagi rasm).

Endi bu muammoning savoliga javob salbiy ekanligini ko'rish oson. Dastlabki holatda ikkita oq ritsar o'rtasida qora ritsar yo'q, lekin oxirgi holatda bu qora ritsar bo'lishi kerak. Grafikning chetlari ikkita qo'shni ritsarlar bir-biridan sakrab o'tolmasligi uchun joylashtirilgan.

7-misol. Bo'ri, echki va karam haqidagi muammo. Daryoning bir qirgʻogʻida odam (H), qayiq, boʻri (V), echki (Kz) va karam (Kp) bor. Qayiqda bir vaqtning o'zida bir kishi va bir nechta tashiladigan narsalar bo'lishi mumkin. Biror kishi shartga rioya qilgan holda barcha narsalarni boshqa tomonga olib borishi kerak: bo'rini echki bilan, echkini karam bilan qarovsiz qoldirmaslik kerak.

Yechim. Tuzilgan grafikda cho'qqilar konfiguratsiyalar, qirralar esa konfiguratsiyalar orasidagi "bitta qayiqda ulanish" munosabatidir. Konfiguratsiya deganda ob'ektlarning asl qirg'og'ida va qarama-qarshi qirg'og'ida joylashishi tushuniladi. Har bir konfiguratsiya ( A|B), Qayerda A- asl qirg'oqda joylashgan ob'ektlar va B- qarama-qarshi qirg'oqda joylashgan ob'ektlar. Shunday qilib, dastlabki konfiguratsiya - (PMCpKz| ) . Misol uchun, echkini boshqa tomonga olib o'tgandan so'ng, konfiguratsiya bo'ladi (VKp|ChKz) . Yakuniy konfiguratsiya har doim ( |PMCpKz) . Endi biz cho'qqilar va qirralar nimani anglatishini bilib, grafik yaratishimiz mumkin:

Grafikning uchlarini chetlari kesishmasligi uchun joylashtiramiz, qo‘shni cho‘qqilar esa grafikdagi munosabat bilan bog‘langan cho‘qqilardir. Keyin munosabatlarni ko'rish ancha oson bo'ladi (rasmni kattalashtirish uchun sichqonchaning chap tugmasi bilan bosing):

Ko'rib turganimizdek, dastlabki konfiguratsiyadan oxirgi konfiguratsiyaga qadar ikki xil uzluksiz yo'nalish mavjud. Shuning uchun muammoning ikki xil echimi bor (va ikkalasi ham to'g'ri).

Grafik nazariyasi va eng muhim zamonaviy amaliy masalalar

Grafiklar nazariyasiga asoslanib, juda murakkab tizimlar grafik shaklida modellashtirilgan amaliy masalalarni yechish usullari ishlab chiqilgan. Ushbu modellarda tugunlar alohida komponentlarni o'z ichiga oladi va qirralar komponentlar orasidagi aloqalarni ifodalaydi. Odatda, vaznli grafiklar transport tarmoqlarini, navbat tizimlarini va tarmoqni rejalashtirishni modellashtirish uchun ishlatiladi. Biz ular haqida allaqachon gapirgan edik, bular yoylarga og'irliklar tayinlangan grafiklardir.

Daraxt grafiklari, masalan, qurish uchun ishlatiladi qaror daraxtlari(xavfni tahlil qilish, noaniqlik sharoitida mumkin bo'lgan daromad va yo'qotishlarni tahlil qilish uchun xizmat qiladi). Grafik nazariyasidan foydalanib, ishlab chiqilgan va boshqa ko'plab matematik modellar muayyan mavzulardagi muammolarni hal qilish.

Grafiklar va oqim muammosi

Muammoni shakllantirish. Quyidagi rasmdagi grafik bilan ifodalangan suv quvurlari tizimi mavjud.

Grafikning har bir yoyi quvurni ifodalaydi. Yoylar (tarozi) ustidagi raqamlar quvur quvvati hisoblanadi. Tugunlar quvurlarni ulash joylari. Suv quvurlar orqali faqat bitta yo'nalishda oqadi. Tugun S- suv manbai, tugun T- Aksiya. Manbadan drenajga oqadigan suv hajmini maksimal darajada oshirish talab qilinadi.

Oqim muammosini hal qilish uchun siz Ford-Fulkerson usulidan foydalanishingiz mumkin. Usulning g'oyasi: maksimal oqimni qidirish bosqichma-bosqich amalga oshiriladi. Algoritmning boshida oqim nolga o'rnatiladi. Har bir keyingi bosqichda oqimning qiymati oshadi, buning uchun qo'shimcha oqim keladigan qo'shimcha yo'l izlanadi. Qo'shimcha yo'llar mavjud ekan, bu qadamlar takrorlanadi. Muammo turli taqsimlangan tizimlarda muvaffaqiyatli qo'llanildi: elektr ta'minoti tizimi, aloqa tarmog'i, temir yo'l tizimi va boshqalar.

Grafiklar va tarmoqni rejalashtirish

Ba'zilari parallel, ba'zilari ketma-ket bajariladigan ko'plab ishlardan iborat murakkab jarayonlarni rejalashtirish muammolari PERT tarmoqlari deb nomlanuvchi og'irlikli grafiklardan keng qo'llanila boshlandi.

PERT - Dasturni (loyihani) baholash va ko'rib chiqish texnikasi - loyihalarni boshqarishda qo'llaniladigan dasturlarni (loyihalarni) baholash va tahlil qilish texnikasi.

PERT tarmog'i vaznli asiklik yo'naltirilgan grafik bo'lib, unda har bir yoy ishni (harakat, operatsiya) ifodalaydi va yoyning og'irligi uni bajarish uchun zarur bo'lgan vaqtdir.

Agar tarmoqda yoylar bo'lsa ( a, b) va ( b, c), keyin yoy bilan ifodalangan ish ( a, b) yoy bilan ifodalangan ishdan oldin bajarilishi kerak ( b, c). Har bir cho'qqi ( vi) cho'qqisida tugaydigan yoylar bilan belgilangan barcha ishlarning vaqt nuqtasini ifodalaydi ( vi).

Bunday ustunda:

o'tmishdoshlari bo'lmagan bitta cho'qqi ishning boshlanish vaqtini belgilaydi;
izdoshlari bo'lmagan bir cho'qqi ishlar to'plami tugallangan vaqtga to'g'ri keladi.

Grafikning ushbu cho'qqilari orasidagi maksimal uzunlikdagi yo'l (ish jarayonining boshidan oxirigacha) kritik yo'l deb ataladi. Butun ish kompleksini bajarish uchun zarur bo'lgan vaqtni qisqartirish uchun, masalan, qo'shimcha ijrochilar, mexanizmlar va yangi texnologiyalarni jalb qilish orqali muhim yo'lda yotadigan ishni topish va uning davomiyligini qisqartirish kerak.

"Grafik nazariyasi" to'liq bloki

Kalit so‘zlar:

grafik ob'ekt
kompyuter grafikasi
rastr grafikasi
Vektor grafika
grafik fayl formatlari

Chizmalar, rasmlar, chizmalar, fotosuratlar va boshqa grafik tasvirlar grafik ob'ektlar deb ataladi.

3.2.1. Kompyuter grafikasini qo'llash sohalari

Kompyuter grafikasi bizning kundalik hayotimizda mustahkam o'rin oldi. U amal qiladi:

o'lchovlar va kuzatishlar natijalarini vizual taqdim etish uchun (masalan, uzoq vaqt davomida iqlim o'zgarishi to'g'risidagi ma'lumotlar, hayvonlar populyatsiyasining dinamikasi, turli mintaqalarning ekologik holati va boshqalar), sotsiologik so'rovlar natijalari, rejalashtirilgan ko'rsatkichlar, statistik ma'lumotlar, tibbiyotda ultratovush tekshiruvi natijalari va boshqalar;
interyer va landshaft dizaynini ishlab chiqishda, yangi binolar, texnik qurilmalar va boshqa mahsulotlarni loyihalashda;
simulyatorlarda va kompyuter o'yinlarida yuzaga keladigan turli xil vaziyatlarni taqlid qilish uchun, masalan, samolyot yoki kosmik kemaning parvozi, avtomobil harakati va boshqalar;
kino sanoatida barcha turdagi maxsus effektlarni yaratishda;
dasturiy ta'minot va tarmoq axborot resurslari uchun zamonaviy foydalanuvchi interfeyslarini ishlab chiqishda;
insonning ijodiy ifodasi uchun (raqamli fotosurat, raqamli rasm, kompyuter animatsiyasi va boshqalar).

Kompyuter grafikasiga misollar rasmda ko'rsatilgan. 3.5.

Guruch. 3.5.
Kompyuter grafikasi misollar

http://snowflakes.barkleyus.com/ - kompyuter vositalaridan foydalanib, siz har qanday qor parchasini "kesib olishingiz" mumkin;
http://www.pimptheface.com/create/ - lablar, ko'zlar, qoshlar, soch turmagi va boshqa qismlarning katta kutubxonasidan foydalanib, yuz yaratishingiz mumkin;
http://www.ikea.com/ms_RU/rooms_ideas/yoth/index.html - xonangiz uchun yangi mebel va pardozlash materiallarini tanlashga harakat qiling.

3.2.2. Raqamli grafikani yaratish usullari

Kompyuter yordamida yaratilgan yoki ishlov berilgan grafik ob'ektlar kompyuter muhitida saqlanadi; agar kerak bo'lsa, ular qog'ozga yoki boshqa mos vositalarga (plyonka, karton, mato va boshqalar) chop etilishi mumkin.

Kompyuter muhitidagi grafik ob'ektlarni raqamli grafik ob'ektlar deb ataymiz.

Raqamli grafik ob'ektlarni olishning bir necha usullari mavjud.

raqamli kameradan, tashqi xotira qurilmalaridan tayyor tasvirlarni nusxalash yoki ularni Internetdan "yuklab olish";
skaner yordamida qog'ozda mavjud grafik tasvirlarni kiritish;
dasturiy ta'minot yordamida yangi grafikalar yaratish.

Skanerning ishlash printsipi qog'ozda mavjud bo'lgan tasvirni mayda kvadratlarga - piksellarga bo'lish, har bir pikselning rangini aniqlash va uni kompyuter xotirasida ikkilik kodda saqlashdir.

Skanerlash natijasida olingan tasvirning sifati piksel o'lchamiga bog'liq: piksel qanchalik kichik bo'lsa, asl tasvir shunchalik ko'p piksellarga bo'linadi va tasvir haqida to'liqroq ma'lumot kompyuterga uzatiladi.

Piksel o'lchamlari skanerning o'lchamlariga bog'liq bo'lib, u odatda dpi (dyuymdagi nuqta - 1 dyuymdagi nuqta) bilan ifodalanadi va bir juft raqamlar bilan belgilanadi (masalan, 600 x 1200 dpi). Birinchi raqam skaner tomonidan 1 dyuym uzunlikdagi tasvir chizig'ida chiqarilishi mumkin bo'lgan piksellar soni. Ikkinchi raqam - 1 dyuymli balandlikdagi tasvir chizig'ini bo'lish mumkin bo'lgan chiziqlar soni.

1 dyuym - ingliz o'lchovlar tizimidagi uzunlik birligi, 2,54 sm ga teng.

Vazifa. 10 x 10 sm o'lchamdagi rangli tasvir skanerlanadi. Skanerning o'lchamlari 1200 x 1200 dpi, rang chuqurligi 24 bit. Olingan grafik fayl qanday axborot hajmiga ega bo'ladi?

Yechim. Skanerlangan tasvir taxminan 4 x 4 dyuymni o'lchaydi. Skanerning o'lchamlarini hisobga olgan holda, butun tasvir 4 4 1200 1200 pikselga bo'linadi.

Javob: taxminan 66 MB.

Raqamli ta'lim resurslarining yagona to'plamida (http://school-collection.edu.ru/) joylashtirilgan "Skanerlar: ishlashning umumiy tamoyillari", "Skannerlar: tekis skaner" animatsiyalarini tomosha qilishingizni tavsiya qilamiz. Ushbu manbalar skanerlash jarayoni qanday ishlashini yaxshiroq tushunishga yordam beradi. "Raqamli kamera" resursi raqamli fotosuratlar qanday olinishini ko'rsatadi (3.6-rasm).

Guruch. 3.6.
Flatbed skaner va raqamli kamera

3.2.3. Rastr va vektor grafika

Grafik tasvirni yaratish usuliga qarab rastr, vektor va fraktal grafiklar farqlanadi.

Rastr grafikasi

Rastrli grafikada tasvir rastr ko'rinishida - satr va ustunlarni tashkil etuvchi nuqtalar (piksellar) yig'indisi shaklida shakllanadi. Har bir piksel millionlab ranglarni o'z ichiga olgan palitradan istalgan rangni olishi mumkin. Rangning aniqligi rastrli grafikaning asosiy afzalligi hisoblanadi. Rastr tasvir kompyuter xotirasida saqlanganida, unga kiritilgan har bir pikselning rangi haqidagi ma'lumotlar saqlanadi.

Rastr tasvirining sifati tasvirdagi piksellar soni va palitradagi ranglar soni ortib boradi. Shu bilan birga, butun tasvirning axborot hajmi ortadi. Axborot hajmining kattaligi rastrli tasvirlarning asosiy kamchiliklaridan biridir.

Rastrli tasvirlarning navbatdagi kamchiligi ularni masshtablashda ba'zi qiyinchiliklar bilan bog'liq. Shunday qilib, rastrli tasvir kichraytirilganda, bir nechta qo'shni piksellar bittaga aylanadi, bu esa tasvirning kichik detallarida tiniqlikning yo'qolishiga olib keladi. Rastrli tasvir kattalashtirilganda unga yangi piksellar qo'shiladi, qo'shni piksellar esa bir xil rangga ega bo'ladi va qadam effekti paydo bo'ladi (3.7-rasm).

Guruch. 3.7.
Rastr tasviri va uning kattalashtirilgan qismi

Rastr grafiklari kamdan-kam hollarda qo'lda yaratiladi. Ko'pincha ular rassomlar tomonidan tayyorlangan rasmlar yoki fotosuratlarni skanerlash orqali olinadi; So'nggi paytlarda raqamli kameralar rastrli tasvirlarni kompyuterga kiritish uchun keng qo'llanilmoqda.

Vektor grafika

Ko'pgina grafik tasvirlarni segmentlar, doiralar, yoylar, to'rtburchaklar va boshqa geometrik shakllar to'plami sifatida taqdim etish mumkin. Masalan, rasmdagi rasm. 3.8 doiralar, segmentlar va to'rtburchaklardan iborat.

Guruch. 3.8.
Doiralar, segmentlar va to'rtburchaklardan iborat tasvir

Ushbu raqamlarning har birini matematik tarzda tasvirlash mumkin: segmentlar va to'rtburchaklar - ularning uchlari koordinatalari bo'yicha, doiralar - markazlari va radiuslari koordinatalari bo'yicha. Bundan tashqari, siz chiziqlar qalinligi va rangini, to'ldirish rangini va geometrik shakllarning boshqa xususiyatlarini belgilashingiz mumkin. Vektorli grafikada tasvirlar grafik ob'ektlar va ularni qurish formulalarini tavsiflovchi shunday ma'lumotlar to'plami (vektorlar) asosida shakllanadi. Vektorli tasvirni saqlashda uni tashkil etuvchi eng oddiy geometrik ob'ektlar haqidagi ma'lumotlar kompyuter xotirasiga kiritiladi.

Vektorli tasvirlarning axborot hajmlari rastrli tasvirlarning axborot hajmlaridan sezilarli darajada kamroq. Masalan, aylanani rastrli grafik yordamida tasvirlash uchun doira chizilgan kvadrat maydonining barcha piksellari haqida ma’lumot kerak; Aylanani vektor grafikasi yordamida tasvirlash uchun faqat bitta nuqta (markaz) va radiusning koordinatalari talab qilinadi.

Vektorli tasvirlarning yana bir afzalligi ularning sifatini yo'qotmasdan masshtablash imkoniyatidir (3.9-rasm). Buning sababi shundaki, vektor ob'ektining har bir o'zgarishi bilan eski rasm o'chiriladi va uning o'rniga mavjud formulalar yordamida, lekin o'zgartirilgan ma'lumotlarni hisobga olgan holda yangisi quriladi.

Guruch. 3.9.
Vektorli tasvir, uning aylantirilgan qismi va bu fragment "yig'ilgan" eng oddiy geometrik shakllar

Shu bilan birga, har bir tasvirni oddiy geometrik shakllar to'plami sifatida ifodalash mumkin emas. Taqdimotning ushbu usuli chizmalar, diagrammalar, biznes grafikalari va tasvirlarning aniq va aniq konturlarini saqlash alohida ahamiyatga ega bo'lgan boshqa holatlar uchun yaxshi.

Fraktal grafika ham vektor grafikasi kabi matematik hisob-kitoblarga asoslanadi. Ammo, vektor grafikasidan farqli o'laroq, kompyuter xotirasi tasvirni tashkil etuvchi geometrik shakllarning tavsiflarini emas, balki tasvirni qurish uchun ishlatiladigan matematik formulani (tenglamani) o'zini saqlaydi. Fraktal tasvirlar xilma-xil va g'alati (3.10-rasm).

Guruch. 3.10.
Fraktal grafika

Ushbu masala bo'yicha to'liqroq ma'lumotni Internetda topishingiz mumkin (masalan, http://ru.wikipedia.org/wiki/Fractal saytida).

3.2.4. Grafik fayl formatlari

Grafik fayl formati tashqi muhitda grafik ma'lumotlarni aks ettirish usulidir. Grafik fayllarning rastr va vektor formatlari mavjud bo'lib, ular orasida o'z navbatida universal grafik formatlar va grafik ilovalarning xususiy (original) formatlari mavjud.

Universal grafik formatlar rastr (vektor) grafikalar bilan ishlaydigan barcha ilovalar tomonidan “tushuniladi”.

Umumjahon rastr grafik formati BMP formatidir. Ushbu formatdagi grafik fayllar katta ma'lumot hajmiga ega, chunki ular har bir pikselning rangi haqidagi ma'lumotlarni saqlash uchun 24 bit ajratadi.

GIF universal bitmap formatida saqlangan chizmalar faqat 256 xil rangdan foydalanishi mumkin. Ushbu palitra oddiy rasmlar va piktogrammalar uchun javob beradi. Ushbu formatdagi grafik fayllar kichik ma'lumot hajmiga ega. Bu, ayniqsa, World Wide Web-da qo'llaniladigan grafikalar uchun juda muhimdir, bu erda foydalanuvchilar o'zlari so'ragan ma'lumotlar ekranda iloji boricha tezroq paydo bo'lishini xohlashadi.

JPEG universal rastr formati fotografik sifatli tasvirlarni samarali saqlash uchun maxsus ishlab chiqilgan. Zamonaviy kompyuterlar 16 milliondan ortiq rangni qayta ishlab chiqarishi mumkin, ularning aksariyati inson ko'zi uchun oddiygina farq qilmaydi. JPEG formati inson idroki uchun "ortiqcha" bo'lgan qo'shni piksellarning rang-barang ranglaridan voz kechishga imkon beradi. Asl ma'lumotlarning bir qismi yo'qoladi, ammo bu grafik faylning axborot hajmini (siqishni) kamaytirishni ta'minlaydi. Foydalanuvchiga faylni siqish darajasini aniqlash imkoniyati beriladi. Agar saqlangan rasm katta formatli varaqda chop etilishi kerak bo'lgan fotosurat bo'lsa, unda ma'lumot yo'qolishi istalmagan. Agar ushbu fotosurat veb-sahifaga joylashtirilgan bo'lsa, uni o'nlab marta xavfsiz tarzda siqish mumkin: qolgan ma'lumotlar tasvirni monitor ekranida ko'paytirish uchun etarli bo'ladi.

Universal vektor grafik formatlari Microsoft rasmlari to'plamini saqlash uchun ishlatiladigan WMF formatini o'z ichiga oladi (http://office.microsoft.com/ru-ru/clipart).

Umumjahon EPS formati rastr va vektor grafiklari haqidagi ma'lumotlarni saqlash imkonini beradi. Ko'pincha 2 ta faylni chop etish dasturlariga import qilish uchun ishlatiladi.

2 Faylni u yaratilmagan dasturda ochish jarayoni.

Siz o'zingizning formatlaringiz bilan bevosita grafik ilovalar bilan ishlash jarayonida tanishasiz. Ular tasvir sifati va fayl ma'lumotlari hajmining eng yaxshi nisbatini ta'minlaydi, lekin faqat faylni yaratuvchi dasturning o'zi tomonidan qo'llab-quvvatlanadi (ya'ni tan olinadi va ijro etiladi).

Muammo 1. Bitta pikselni kodlash uchun 3 bayt ishlatiladi. 2048 x 1536 piksel o'lchamdagi fotosurat siqilmagan fayl sifatida saqlangan. Olingan fayl hajmini aniqlang.

Yechim.

Javob: 9 MB.

Muammo 2. Siqilmagan 128 x 128 pikselli bitmap tasviri 2 KB xotirani egallaydi. Rasmlar palitrasidagi ranglarning maksimal mumkin bo'lgan soni qancha?

Yechim.

Javob: 2 rang - qora va oq.

Eng asosiysi

Kompyuter grafikasi keng tushuncha bo'lib, u: 1) kompyuterlar yordamida yaratilgan yoki qayta ishlanadigan har xil turdagi grafik ob'ektlarni; 2) kompyuterlar grafik ob'ektlarni yaratish va qayta ishlash vositalari sifatida foydalaniladigan faoliyat sohasi.

Grafik tasvirni yaratish usuliga qarab rastrli va vektorli grafiklar farqlanadi.

Rastrli grafikada tasvir rastr ko'rinishida - satr va ustunlarni tashkil etuvchi nuqtalar (piksellar) yig'indisi shaklida shakllanadi. Rastr tasvir kompyuter xotirasida saqlanganida, unga kiritilgan har bir pikselning rangi haqidagi ma'lumotlar saqlanadi.

Vektorli grafikada tasvirlar ma'lum bir grafik ob'ektni tavsiflovchi ma'lumotlar to'plamlari (vektorlar) va ularni qurish formulalari asosida shakllanadi. Vektorli tasvirni saqlashda uni tashkil etuvchi eng oddiy geometrik ob'ektlar haqidagi ma'lumotlar kompyuter xotirasiga kiritiladi.

Savol va topshiriqlar

Kompyuter grafikasi nima?
Kompyuter grafikasini qo‘llashning asosiy sohalarini sanab o‘ting.
Raqamli grafiklarni qanday ishlab chiqarish mumkin?
10 x 15 sm o'lchamdagi rangli tasvir skanerlanadi. Skanerning o'lchamlari 600 x 600 dpi, rang chuqurligi 3 bayt. Olingan grafik fayl qanday axborot hajmiga ega bo'ladi?
Rasmni tasvirlashning rastr va vektor usullari o'rtasidagi farq nima?
Nega rastrli tasvirlar rangni juda aniq etkazadi, deb ishoniladi?
Rastrli tasvirni aylantirishning qaysi operatsiyasi uning sifatini eng katta yo'qotishiga olib keladi - qisqartirish yoki kattalashtirish? Buni qanday tushuntira olasiz?
Nega masshtablash vektor tasvir sifatiga ta'sir qilmaydi?
Grafik fayl formatlarining xilma-xilligini qanday tushuntirish mumkin?
Universal grafik formatlar va xususiy grafik dastur formatlari o'rtasidagi asosiy farq nima?
3.2.4-bo'limdagi tushunchalar uchun iloji boricha to'liq grafik tuzing.
Rastr va vektor tasvirlarning batafsil tavsifini keltiring, unda quyidagilar ko'rsatiladi:
1024 x 512 pikselli chizma siqilmagan 1,5 MB fayl sifatida saqlangan. Piksel rangini kodlash uchun qancha ma'lumot ishlatilgan? Ushbu rang chuqurligiga mos keladigan palitradagi ranglarning maksimal mumkin bo'lgan soni qancha?
Siqilmagan 256 x 128 pikselli bitmap tasvir 16 KB xotirani egallaydi. Rasmlar palitrasidagi ranglarning maksimal mumkin bo'lgan soni qancha?

Universal grafik formatlar rastr (vektor) grafikalar bilan ishlaydigan barcha ilovalar tomonidan “tushuniladi”.

Umumjahon rastr grafik formati BMR formatidir. Ushbu formatdagi grafik fayllar katta ma'lumot hajmiga ega, chunki ular har bir pikselning rangi haqidagi ma'lumotlarni saqlash uchun 24 bit ajratadi.

foydalanuvchilari o'zlari so'ragan ma'lumotlarning imkon qadar tezroq ekranda paydo bo'lishini xohlashadi.

JPEG universal rastr formati fotografik sifatli tasvirlarni samarali saqlash uchun maxsus ishlab chiqilgan. Zamonaviy kompyuterlar 16 milliondan ortiq rangni qayta ishlab chiqarishi mumkin, ularning aksariyati inson ko'zi uchun oddiygina farq qilmaydi. JPEG formati inson idroki uchun "ortiqcha" bo'lgan qo'shni piksellarning rang-barang ranglaridan voz kechishga imkon beradi. Asl ma'lumotlarning bir qismi yo'qoladi, ammo bu grafik faylning axborot hajmini (siqishni) kamaytirishni ta'minlaydi. Foydalanuvchiga faylni siqish darajasini aniqlash imkoniyati beriladi. Agar saqlangan rasm katta formatli varaqda chop etilishi kerak bo'lgan fotosurat bo'lsa, unda ma'lumot yo'qolishi istalmagan. Agar ushbu fotosurat XL sahifasiga joylashtirilgan bo'lsa, uni o'nlab marta xavfsiz tarzda siqish mumkin: qolgan ma'lumotlar tasvirni monitor ekranida ko'paytirish uchun etarli bo'ladi.

Universal vektor grafik formatlari Microsoft rasmlari to'plamini saqlash uchun ishlatiladigan WMF formatini o'z ichiga oladi (http://office.microsoft.com/ru-ru/clipart).

Umumjahon EPS formati rastr va vektor grafiklari haqidagi ma'lumotlarni saqlash imkonini beradi. Ko'pincha import uchun ishlatiladi! fayllarni bosma mahsulotlarni tayyorlash uchun dasturlarga kiriting.

Muammo 1. Bitta pikselni kodlash uchun 3 bayt ishlatiladi. 2048 x 1536 piksel o'lchamdagi fotosurat siqilmagan fayl sifatida saqlangan. Olingan fayl hajmini aniqlang. Yechim.

I-k.i i-I/k

i-2. 1024 8/(128. 128) =

2 2 10 2 3 /(2 7 2 7) = 2 1 + 10 + 3 /2 7 + 7 2 14 /2 14 = 1 (bit). LG-21-2.

Javob: 2 rang - qora va oq.

ENG ASOSIYSI

Grafik tasvirni yaratish usuliga qarab rastrli va vektorli grafiklar farqlanadi.

Rastrli grafikada tasvir satr va ustunlarni tashkil etuvchi nuqtalar (piksellar) to'plamining rastri sifatida shakllanadi. Rastr tasvir kompyuter xotirasida saqlanganida, unga kiritilgan har bir pikselning rangi haqidagi ma'lumotlar saqlanadi.

Vektorli grafikada tasvirlar ma'lum bir grafik ob'ektni tavsiflovchi ma'lumotlar to'plami (vektorlar) va ularni qurish formulalari asosida shakllanadi. Vektorli tasvirni saqlashda uni tashkil etuvchi eng oddiy geometrik ob'ektlar haqidagi ma'lumotlar kompyuter xotirasiga kiritiladi.

a Savol va topshiriqlar

1. Kompyuter grafikasi nima?

2. Kompyuter grafikasining asosiy qo‘llanish sohalarini sanab o‘ting.

H. Raqamli grafiklarni qanday ishlab chiqarish mumkin?

4. 10 x 15 sm o'lchamdagi rangli tasvir skanerdan o'tkaziladi Skanerning ruxsati 600 x 600 dpi, rang chuqurligi - 3 bayt. Olingan grafik fayl qanday axborot hajmiga ega bo'ladi?

5. Tasvirni tasvirlashning rastr va vektor usullarining farqi nimada?

b. Nega rastrli tasvirlar rangni juda aniq etkazadi, deb ishoniladi?

7. Rastrli tasvirni o'zgartirishning qaysi operatsiyasi uning sifatini eng katta yo'qotishiga olib keladi - kichraytirish yoki kattalashtirish? Buni qanday tushuntira olasiz?

8. Nima uchun masshtablash vektor tasvir sifatiga ta'sir qilmaydi?

9. Grafik fayl formatlarining xilma-xilligini qanday tushuntirish mumkin?

Kompyuter grafikasi

10. Umumjahon grafik formatlari va xususiy grafik dastur formatlarining asosiy farqi nimada?

11. 3.2.4-bo'limdagi tushunchalar uchun iloji boricha to'liq grafik tuzing.

12. Quyidagilarni ko'rsatgan holda rastrli va vektorli tasvirlarga batafsil tavsif bering:

a) tasvir qaysi elementlardan qurilganligi;

b) tashqi xotirada tasvir haqidagi qanday ma'lumotlar saqlanadi;

c) grafik tasvirni o'z ichiga olgan fayl hajmi qanday aniqlanadi;

d) masshtablashda tasvir sifati qanday o'zgaradi;

e) rastrli (vektorli) tasvirlarning asosiy afzalliklari va kamchiliklari qanday.

13. 1024 x 512 piksel o'lchamdagi chizma 1,5 MB hajmdagi siqilmagan fayl sifatida saqlangan. Piksel rangini kodlash uchun qancha ma'lumot ishlatilgan? Ushbu rang chuqurligiga mos keladigan palitradagi ranglarning maksimal mumkin bo'lgan soni qancha?

14. 256 x 128 pikselli siqilmagan rastrli tasvir 16 KB xotirani egallaydi. Rasmlar palitrasidagi ranglarning maksimal mumkin bo'lgan soni qancha?

Nazariy ma'lumotlar

E'tibor bering, qurilish masalalarida yechimni oddiy yo'naltirilmagan grafiklar (ya'ni, bir nechta qirrali va halqasiz grafiklar) orasidan izlash kerak. Afsuski, berilgan xususiyatlarga ega bo'lgan grafikni qurish mumkinligini aniq aniqlashga imkon beradigan universal texnika yo'q.

Shuni yodda tutish kerakki, har qanday grafikda uning barcha uchlari darajalari yig'indisi juft son bo'lib, grafik qirralari sonining ikki barobariga teng, chunki har bir chekka bu yig'indida to'liq ikki marta ishtirok etadi. 200 yil oldin Eylerga ma'lum bo'lgan bu natija ko'pincha qo'l siqish lemmasi deb ataladi. Bundan kelib chiqadiki, agar bir necha kishi qo'l siqishsa, qo'l siqishlarning umumiy soni shartli ravishda teng bo'ladi, chunki har bir qo'l siqishda ikkita qo'l ishtirok etadi (har bir qo'l qo'l siqishda qancha marta qatnashgan bo'lsa, shuncha marta hisobga olinadi). Bundan kelib chiqadiki:

har qanday grafikdagi toq darajali uchlari soni juft;
bilan har qanday grafikda P cho'qqilari qaerda P> 2, har doim bir xil darajaga ega bo'lgan kamida ikkita cho'qqi bor;
cho'qqilari bo'lgan grafikda bo'lsa p> 2 ta toʻliq ikkita choʻqqi bir xil darajaga ega boʻlsa, bu grafikda har doim yo 0 darajali toʻliq bitta choʻqqi yoki aniq bir daraja choʻqqisi boʻladi. (P - 1).

Muammolarni hal qilishda siz shartlarni diqqat bilan o'qib chiqishingiz kerak, chunki grafikning xususiyatlarini tavsiflovchi ko'plab sifatlar raqamli ekvivalentlarga ega. Muammolarni shakllantirishda eng ko'p uchraydigan bunday yozishmalar jadvalini taqdim etamiz (2.9-jadval).

Barcha kerakli raqamlar olingandan so'ng, siz grafikning etishmayotgan xususiyatlarini hisoblashga harakat qilishingiz kerak. Ba'zan shart barcha yoki bir nechta cho'qqilarning darajalarini beradi. Bunday holda, grafikning har bir chekkasi o'zining umumiy darajasiga aniq ikkita burchak qo'shishiga asoslanib, biz formuladan foydalanishimiz mumkin.

X 5 (y /) =2t'

Qayerda T - cho'qqilar soni va yig'ish 1 dan barcha cho'qqilar bo'ylab amalga oshiriladi P.

Vazifalar

Muammo 2.42. Sakkizta cho'qqi bo'yicha quyidagi cho'qqi darajalari taqsimotiga ega bo'lgan grafik tuzing: 4-darajali ikkita cho'qqi; 3-darajali uchta cho'qqi; 2-darajali ikkita cho'qqi; 1-darajaning bir cho'qqisi.

Yechim.

Barcha cho'qqilarning umumiy darajasi 2-4 + 3- 3 + 2- 2+1 1=22, ya'ni jami 11 ta qirralar mavjud. Grafiklarni katta darajali cho'qqilardan boshlab darajalar vektoriga asoslangan holda qurish osonroq. Ver-

2.9-jadval

Grafik tavsifi va uning xossalari o'rtasidagi muvofiqlik

Sifatlovchi	Raqamli	Bu nima degani
		Grafikda aynan bitta bog'langan komponent mavjud
Muvofiq emas		Grafikda bir nechta komponentlar mavjud, uning diametri cheksizdir
Muntazam	5(U;) = SOSHI	Barcha cho'qqilarning darajalari tengdir
Doimiy daraja	z(Uі)=U	Barcha cho'qqilarning darajalari tengdir u. Agar ma'lum bo'lsa P(cho'qqilar soni), keyin darhol hisoblashingiz mumkin T(qovurg'alar soni): y-p? y/2 (P yoki da juft raqam bo'lishi kerak)
Asiklik	y= t-p + k = 0	Tsiklomatik raqam nolga teng, grafikda tsikllar yo'q, u daraxt yoki o'rmon (bog'lanishga qarab), bunday grafiklar har doim ikkita rangda bo'yalgan bo'lishi mumkin. Agar uchta o'zgaruvchidan ikkitasi ma'lum bo'lsa ( P, t, k), keyin formuladan foydalanib, qolganini topishingiz mumkin
Daraxt (yoki asiklik bog'langan grafik)	y= t- n + 1 = 0, qaerdan T- n - 1	Tsiklomatik raqam nolga teng, grafikda tsikllar yo'q, bu daraxt, bunday grafiklarni har doim ikkita rangda bo'yash mumkin. Agar ikkita o'zgaruvchidan biri ma'lum bo'lsa ( P yoki T), keyin formuladan foydalanib, ikkinchisini topishingiz mumkin
Bikromatik		Grafikning xromatik raqami ikkitadir, bunday grafiklar har doim ikkita rangda bo'yalgan bo'lishi mumkin, bu ikki tomonlama grafiklar, grafik jihatdan ular asiklik grafiklar yoki barcha tsikllar teng uzunlikka ega bo'lgan grafiklardir.

Chizmaning grafik tasvirida avtobuslarni iloji boricha kamroq qirralar va yoylar kesishishi va cho'qqilarning o'zlari qandaydir o'xshashlik mezoniga ko'ra guruhlanganligi uchun joylashtirish yaxshiroqdir. Variantlardan biri rasmda ko'rsatilgan. 2.8.

Muammo 2.43. Oltita cho'qqi bo'yicha quyidagi cho'qqi darajalari taqsimotiga ega bo'lgan grafik tuzing: 3-darajali ikkita cho'qqi;

Guruch. 2.8.

2-darajali ikkita cho'qqi; 1-darajali bir cho'qqi; bir tepalik ixtiyoriy darajaga ega.

Yechim.

Cho'qqilarning umumiy darajasi 11 ga teng, shuning uchun qolgan tepalik g'alati darajaga ega bo'lishi kerak, ya'ni. 1,3 yoki 5. Shunday qilib, uch xil grafikni qurish mumkin (2.9-rasm).

Guruch. 2.9.

Muammo 2.44. Quyidagi vektorli cho'qqi darajalari bilan grafik tuzing: 5 = (1, 2, 2, 3, 4, 4, 5).

Yechim.

Umumiy daraja 5 + 8 + 3 + 4+1=21. Bu teoremaga zid bo'lgan toq son bo'lgani uchun (qirralar soni bu raqamning yarmini tashkil qiladi, lekin 21 2 ga teng bo'linmaydi).

Javob. Bunday grafik mavjud emas.

Muammo 2.45. Quyidagi vektorli cho'qqi darajalari bilan grafik tuzing: 5 = (1, 1,2, 2, 2, 4, 4, 4, 4).

Muammo 2.46. Quyidagi vektorli cho'qqi darajalari bilan grafik tuzing: 5 = (5, 5, 6, 6, 6, 6, 6).

Muammo 2.47. Quyidagi vektorli cho'qqi darajalari bilan grafik tuzing: 5 = (1, 1, 1,2, 3, 3, 3, 3, 5, 5, 5).

Muammo 2.48. Vertex darajalarining quyidagi vektori bilan grafik tuzing: 5 = (3, 3, 3, 3, 3, 3, 3, 7).

Muammo 2.49. Oltita cho‘qqi bo‘yicha grafa tuzing, unda quyidagi cho‘qqi darajalari taqsimoti bo‘ladi: uchta cho‘qqi 5-darajali, qolgan uchtasi noma’lum darajali.

Muammo 2.50. O'nta cho'qqi ustida, qirralari cho'qqilardan ikki barobar ko'p bo'lgan va cho'qqi graduslarining quyidagi taqsimoti bo'yicha grafik tuzing: 6-darajali ikkita cho'qqi; 5-darajali to'rtta burchak; 4-darajali ikkita cho'qqi; ixtiyoriy darajadagi ikkita cho'qqi - yoki bunday grafikni qurish mumkin emasligini oqlaydi.

Muammo 2.51. O'nta cho'qqi bo'yicha quyidagi cho'qqi darajalari taqsimotiga ega bo'lgan grafik tuzing: 7 darajali bir cho'qqi; 6 darajali ikkita cho'qqi; 5-darajali ikkita cho'qqi; 4-darajali ikkita cho'qqi; 3-darajali ikkita cho'qqi; 2-darajali bir cho'qqi - yoki bunday grafikni qurishning iloji yo'qligini asoslang.

Muammo 2.52. 11 ta cho’qqi bo’yicha quyidagi cho’qqi darajalari taqsimotiga ega bo’lgan grafik tuzing: 7 darajali bir cho’qqi; 6 darajali ikkita cho'qqi; 5-darajali ikkita cho'qqi; 4-darajali ikkita cho'qqi; 3-darajali ikkita cho'qqi; 2-darajali bir cho'qqi - yoki bunday grafikni qurishning iloji yo'qligini asoslang.

1736 yil, Koenigsberg. Shahar bo'ylab Pregelya daryosi oqib o'tadi. Yuqoridagi rasmda ko'rsatilganidek, shaharda ettita ko'prik mavjud. Qadim zamonlardan beri Königsberg aholisi jumboq bilan kurashib kelishgan: har bir ko'prikdan faqat bir marta o'tish mumkinmi? Bu muammo nazariy jihatdan ham, qog'ozda ham, amalda ham, yurishlarda - aynan shu ko'priklar bo'ylab o'tib hal qilindi. Hech kim bu mumkin emasligini isbotlay olmadi, lekin hech kim ko'priklar bo'ylab bunday "sirli" yurish qila olmadi.

Mashhur matematik Leonhard Eyler muammoni hal qilishga muvaffaq bo'ldi. Bundan tashqari, u nafaqat ushbu aniq muammoni hal qildi, balki shunga o'xshash muammolarni hal qilishning umumiy usulini ham o'ylab topdi. Königsberg ko'priklari muammosini hal qilishda Eyler shunday yo'l tutdi: u erni nuqtalarga "siqdi" va ko'priklarni chiziqlarga "cho'zdi". Ushbu nuqtalarni bog'laydigan nuqtalar va chiziqlardan iborat bunday raqam deyiladi COUNT.

Grafik - bu bo'sh bo'lmagan cho'qqilar to'plami va cho'qqilar orasidagi bog'lanishlar to'plami. Doiralar grafikning cho'qqilari, o'qlari bor chiziqlar yoylar, o'qlari bo'lmagan chiziqlar esa qirralar deb ataladi.

Grafik turlari:

1. Yo'naltirilgan grafik(qisqacha digraf) - qirralariga yo'nalish berilgan.

2. Yo'naltirilmagan grafik chiziqlar yo'nalishi bo'lmagan grafikdir.

3. Vaznli grafik- yoylar yoki qirralarning og'irligi bor (qo'shimcha ma'lumot).

Grafiklar yordamida masalalarni yechish:

Vazifa 1.

Yechish: Olimlarni grafikning uchlari deb belgilaymiz va har bir cho‘qqidan to‘rtta boshqa cho‘qqigacha chiziqlar chizamiz. Biz 10 qatorni olamiz, ular qo'l siqish deb hisoblanadi.

Vazifa 2.

Maktab hududida 8 ta daraxt o'sadi: olma, terak, qayin, rovon, eman, chinor, lichinka va qarag'ay. Rowan lichinkadan baland, olma daraxti chinordan baland, eman qayindan past, lekin qarag'aydan baland, qarag'ay navbatdan baland, qayin terakdan past, lichinka olma daraxtidan baland. Daraxtlarni eng qisqadan eng balandgacha joylashtiring.

Yechim:

Grafikning uchlari daraxt nomining birinchi harfi bilan ko'rsatilgan daraxtlardir. Bu vazifada ikkita munosabat mavjud: "past bo'lish" va "yuqori bo'lish". "Pastroq bo'lish" munosabatini ko'rib chiqing va pastki daraxtdan yuqoriroqqa o'qlarni torting. Agar muammo tog 'kulining lichinkadan balandroq ekanligini aytsa, biz lichinkadan tog 'kuliga o'q qo'yamiz va hokazo. Biz eng qisqa daraxt chinor ekanligini, undan keyin olma, lichinka, rowan, qarag'ay, eman, qayin va terak ekanligini ko'rsatadigan grafikni olamiz.

Vazifa 3.

Natashaning 2 ta konverti bor: oddiy va havo, va 3 ta marka: to'rtburchaklar, kvadrat va uchburchak. Natasha xat yuborish uchun konvert va shtampni necha usulda tanlashi mumkin?

Yechim:

Quyida vazifalarning taqsimoti keltirilgan.

O'qish foydali bo'lishi mumkin: