6-ma’ruza. Graflar nazariyasi elementlari va o'tish algoritmlari

7- misol. 8- shaklda uchlari to‘plamlari kesishmaydigan va graflarning ko‘paytmasi amali tasvirlangan. ■
I bobning 4- paragrafida ta’kidlanganidek, Dekart ko‘paytmalar bilan bog‘liq tuzilmalar ustida bajariladigan amallar boshqalaridan o‘ziga xosligi bilan ajralib turadi. Bu o‘ziga xoslik graflarni ko‘paytirish amalida namoyon bo‘ladi. Aniqrog‘i, graflar ko‘patmasida qatnashgan birorta grafning qirralari korteji bo‘sh bo‘lsada, ko‘paytirish amalini qo‘llash natijasida hosil bo‘lgan grafning qirralari korteji bo‘sh bo‘lmasligi ham mumkin. Haqiqatdan ham, yuqorida keltirilgan graflarning ko‘paytmasi ta’rifidan kelib chiqadiki, agar graf va graflarning ko‘paytmasi, ya’ni, bo‘lsa, u holda bo‘ladi va kortej elementlari bilan birlashma elementlari orasida o‘zaro bir qiymatli moslik mavjud. Shuning uchun, agar, masalan, , bo‘lsa, u holda bo‘ladi, chunki grafning tarifiga ko‘ra . Demak, , ya’ni bo‘sh graf bo‘lsada, bo‘sh bo‘lmagan grafdir.
Graflarni ko‘paytirish amalini takror qo‘llash usuli bilan graflar nazariyasining muhim sinfini tashkil etuvchi o‘lchovli kublarni aniqlash mumkin. o‘lchovli kub ( ) uchlari soni ikkiga teng bo‘lgan to‘la graf yordamida quyidagi rekurrent formula bilan aniqlanadi:
, .
Yuqorida graflar ustidagi ba’zi amallar haqida qisqacha ma’lumot berildi. Shuni ta’kidlash lozimki, graflar ustida bundan boshqa bir qator amallar ham bor.

1^ 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.

2^ Kirxgof (Kirchhoff Gustav Robert, 1824-1887) – olmon faylasufi, fizigi.

3^ Keli yoki Keyli (Cayley Artur, 1821-1895) – ingliz matematigi.

4^ Kyonig (Dénes König, 1884-1944) – venger matematigi.

5^ Bu darslik olmon tilida yozilgan.

6^ Bundan keyin “juftliklar korteji” iborasi o‘rniga, qisqacha kortej iborasini qo‘llaymiz.

7^ Bu yerda ham juftlikning (kortejning) odatdagi yozuvi o‘rniga yozuvdan foydalanamiz.

8 ^ Bu masalani fransuz shoiri va yozuvchisi Bashe de Mezeriakning (1587-1638) matematikaga bag‘ishlangan ishlarida topish mumkin.

9 ^ Evklid (Ευκλείδης, eramizdan oldingi III asrda yashagan) – qadimgi yunon (grek) olimi.

10 ^ o‘lchovli Evklid fazosida ikkita va vektorlar orasidagi masofa (metrika) formula bo‘yicha aniqlanadi.

11 ^ Platon (Πλάτων, eramizdan oldingi 428 yoki 427 yil - eramizdan oldingi 348 yoki 347 yil) – yunon faylasufi.

12 ^ Petersen (Julius Peter Christian, 1839-1910) – Daniya matematigi.

13 ^ Bu graf haqidagi dastlabki ma’lumot 1891 yilda e’lon qilingan: J. Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891) 193-220.

14 ^ Bu yerda birlashma “ ” amali ning to‘plam, ning esa kortej ekanligini e’tiborga olgan holda amalga oshiriladi.