Grafning geometrik ifodalanishi

<П \
vektor orasidagi masofa (metrika) d(x,y)= formula bo'yicha
V^¹ )
aniqlanadi.
u=u={\, 3), и =(2, 3), и₅=(3, 4), u={2, 2). G grafning barcha
и. (/=1,6) qirralari oriyentirlanmagan (chunki uchlarini tutashti-ruvchi chiziqlarda yo'nalish ko'rsatilmagan) bo'lgani uchun G oriyentirlanmagan grafdir. Grafning qirralaridan biri, aniqrog'i, u₆sirtmoqdir, u₂va и_ъesa karrali qirralardir. Bu grafda, masalan, 1 va2 uchlar qo'shni, 1 va 4 uchlar esa qo'shni emas. Undagi 2 va3 uchlar w₄ qirraga insident va, aksincha, u_Aqirra 2 va 3 uchlarga insi-dentdir. Bu yerda, u₄vau₅qirralar qo'shni qirralardir, chunki ular umurniy uchga (3 uch) ega, и, va u₅qirralar esa qo'shni emas. ■
2-misol.Geometrik ifodalanishi 2-shakldagi ko'rinishda bo'lgan oriyentirlangan grafni qaraymiz. Bu grafda o'n bitta element bor:
5 ta uch va 6 ta yoy, ya'ni shaklda (5,6)-orgraf berilgan. Bu grafni G=(V,U) bilan belgilaymiz, bu yerda F={1,2,3,4,5}, U= <(1,2), (1,3), (5,2), (4,1), (4,5), (5,4)> yoki U= <и₁,и₂,и₃,и_л,и₅,и₆>. Berilgan G orgrafda sirtmoq ham, karrali yoylar ham yo'q. Bu graf­ning (1,3) yoyi uchun 1 boshlan-g'ich, 3 uch esa oxirgi uchdir. ■ 3-misol.XVT1I asrda Kyonig-sberg ko'priklari haqidagi masalaning qo'yilishi va L. Eyler tomo-nidan yechlishi graflarning matematik nazariyasi paydo bo'lishiga xizmat qilganligi yuqorida ta'kidlangan edi.
Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko'priklar joylashuvi 3-shaklda tasvirlangan (bu shakl L. Eylerning birinchi sahifasi ushbu bobning 1-paragrafda keltirilgan ilmiy ishidan olindi).

Kyonigsberg ko'priklari ha-qidagi masalada quyidagi savolga javob berish so'raladi: «Sha-harning to'rt A, B, С va D qis-midan birida joylashgan uydan chiqib, yetti ko'prikning har biridan faqat bir marta o'tgan holda у ana o'sha uyga qaytib kelish mumkinmi?»
Bu savolga javob izlash maqsadida ko'priklardan o'tish-lar muhimligini e'tiborga olgan holda qo'yilgan masalani tahlil qilish uchun 4-shaklda tasvirlangan grafni qaraymiz. Bu grafning uchlari shaharning A, B, Сva D qismlariga, qirralari esa ko'priklarga mos keladi. Qaralayotgan graf oriyentirlanmagan graf bo'lib, 4 ta uch va7 ta qirradan tashkil topgan. Uning qirralari orasida karralilari bor, lekin sirtmoqlar yo'q.
Kyonigsberg shahridagi ko'priklardan faqat bir marta o'tgan holda yurish boshlangan joyga qaytib kelish muammosi, 4-shakl-dagi grafdan foydalangan holda ushbu bobning 5-paragrafida hal qilinadi. ■
4-misol.5-shaklda tasvirlangan grafiar bir-biriga izomorfdir.■
5-misol.6-shaklda tasvirlangan graflarning har biri olti uch va yetti qirraga ega boiib, ular izomorf emas. ■

Hammasi bo'lib, beshta qavariq muntazam ко 'pyoqli mavjudligi qadimdan ma'lum (Evklid isbotlagan): tetraedr, kub, oktaedr, dodekaedr va ikosaedr. Bu ko'pyoqlilarning umumiy nomi ham bor — Platon¹ jismlari.Shunisi qiziqki, barcha Platon jismlariga
¹Platon (ГШтгау, eramizdan oldingi 428 yoki 427-yil — eramizdan oldingi 348 yoki 347-yil) — yunon faylasufi.
mos grafiar tekislikda geometrik ifodalanadi. Masalan, tetraedr vakubga mos graflaming geometrik ifodalanishi 7-shaklda tasvirlangan.
Darvoqe, Platon jismlaridan tetraedr, kub va dodekaedr kubik grafga misol bo'ladi.

Petersen¹ graft¹deb ataluvchi 8-shaklda tasvirlangan graf ham kubik grafdir.

Agar graf tekislikda geometrik ifodalanishga ega bo'lsa, u holda bunday graf tekis (yassi) graf, deb ataladi. Bunday graf tekislikda yotuvchi graf deb ham atahshi mumkin.
Boshqacha aytganda, tekis grafning barcha uchlari bir tekislikda yotadi hamda barcha qirralari (yoylari) o'sha tekislikda yotuvchi o'zaro kesishmaydigan uzluksiz chiziqlar bo'lib, ular faqat o'zlari insident bo'lgan uchlardagina umumiy nuqtalarga ega.
Platon jismlariga mos barcha grafiar tekis graflardir.Tekis grafga izomorf graf planar graf deb ataladi.
Tekis bo'lmagan grafga ajoyib misol uch uy va uch quduq haqidagi boshqotirma masalaga mos grafdir. Uchta u_vu₂,u₃uy va uchta q_vq₂,q₃quduq bor. Har bir uydan har bir quduqqa ixtiyo-riy ikkitasi kesishmaydigan qilib uzluksiz yo'lakchalar o'tkazish mumkinmi?



¹ Petersen (Julius Peter Christian, 1839—1910) — Daniya matematigi.
² Bu graf haqidagi dastlabki ma'lumot 1891-yilda e'lon qilingan. J. Petersen,
Die Theoriederregularen graphs, Acta Math. 15 (1891) 193—220.

Qog'ozda masala shartini qanoatlantira-digan grafni chizishga urinishlar muvaffaqiyat-siz tugaydi.Shunday uri-nishlardan biri 9-shakl-da keltirilgan