Toshkent viloyati Chirchiq Davlat pedagogika instituti Aniq fanlar fakulteti

1.1-t a s d i q . Har qanday chekli grafni 3 o‘lchovli Evklid fazosida geometrik ifodalash mumkin.
Shuni ham ta’kidlash kerakki, 1- tasdiqdagi 3ni 2ga almashtirib
bo‘lmaydi, chunki tekislikda qirralarini (yoylarini) ifodalovchi kesishmaydigan (aniqrog‘i, chetki nuqtalaridan boshqa umumiy nuqtalari bo‘lmagan) chiziqlar yordamida tasvirlash imkoniyati faqat ba’zi graflargagina xos, ya’ni har qanday
grafning 2 o‘lchovli Evklid fazosida (tekislikda) geometrik ifodalanishi mavjud bo‘lavermaydi.
Agar graf tekislikda geometrik ifodalanishga ega bo‘lsa, u holda bunday graf tekis (yassi) graf deb ataladi. Bunday graf tekislikda yotuvchi graf deb ham atalishi 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.
Tekis grafga izomorf graf planar graf deb ataladi.

Qo‘shnilik matritsalari. Endi grafning boshqa bir berilish usuli negizida yotuvchi graf uchlari qo‘shniligi matritsasi tushunchasini qarab chiqamiz.

G  (V ,U )
– uchlari soni m ga teng bo‘lgan belgilangan, sirtmoqsiz va karrali

qirralarsiz graf bo‘lsin.

Elementlari
<sup>1,

a</sup>ij ^{ }

_0,
agar i va j uchlar qo'shni bo'lsa, aks holda.

ko‘rinishda aniqlangan

A  (a_ij )
( i  1,2,...,m ;


j  1,2,...,m ) matritsani grafning uchlari

qo‘shniligi matritsasi deb ataymiz.
Bu ta’rifdan sirtmoqsiz va karrali qirralari bo‘lmagan graf uchlari qo‘shniligi matritsasining bosh diagonalida faqat nollar bo‘lishi, satrlaridagi birlar soni esa mos uchlarning darajalariga tengligi kelib chiqadi.

Uchlari soni m ga teng bo‘lgan belgilangan oriyentirlangan

G  (V ,U )