2. Элементы теории множеств

Uni ifodalovchi grafik shaklda ko'rsatilgan va og'ish matritsasi va og'ish vektori mos ravishda jadvallarda keltirilgan.

• Uni ifodalovchi grafik shaklda ko'rsatilgan va og'ish matritsasi va og'ish vektori mos ravishda jadvallarda keltirilgan.

Jadval. Burilish vektori

Shaharlar	P	B	L	G	M	H
Parij	0	2	1	1	2	2
Bordo	1	0	2	2	3	3
Lion	2	1	0	1	1	2
Grenobl				0		1
Marsel	3	2	1	2	0	1
Yaxshi						0

Grafik xususiyatlari
Jadval. Burilishlar d ( xi , xj )

	Shaharlar	P	B	L	G	M	H
d(x i )		2	3	2		3	

Grafiklarning xarakterli raqamlari

Grafiklar nazariyasi usullari bilan ko'pgina texnik masalalarni hal qilish grafiklarning ma'lum xarakteristikalarini aniqlashga qisqartiriladi, shuning uchun quyidagi xarakteristikalar bilan tanishish foydalidir.

siklomatik raqam. G ( X ) n ta uchi, m qirrasi va k komponenti ulangan yo naltirilmagan grafik bo lsin . Grafikning siklomatik soni G - bu raqam

µ( G ) = m - n + k .

Bu raqam qiziqarli jismoniy ma'noga ega: u grafikdagi asosiy (mustaqil) davrlarning eng ko'p soniga teng. Elektr zanjirlarini hisoblashda siklomatik raqam mustaqil zanjirlar sonini aniqlash uchun ishlatilishi mumkin.

Grafiklarning xarakterli raqamlari

xromatik raqam. p natural son bo'lsin. G ( X ) grafigi p-xromatik deb ataladi, agar uning uchlarini turli ranglar bilan bo'yash mumkin bo'lsa, ikkita qo'shni cho'qqilar bir xil rangga ega bo'lmaydi. Grafik p-xromatik bo'lgan eng kichik p soni grafikning xromatik soni deb ataladi va g ( G ) bilan belgilanadi.

Agar g ( G ) = 2 bo'lsa, u holda grafik bikromatik deyiladi . Grafikning bixromatik bo'lishi uchun zarur va etarli shart - unda toq uzunlikdagi tsikllarning yo'qligi.

Xromatik raqam dasturlashda xotira kataklaridan eng tejamkor foydalanish masalasini hal qilishda muhim rol o'ynaydi. Biroq, uning ta'rifi, g ( G ) = 2 dan tashqari , kompyuterdan foydalanishni talab qiladigan juda qiyin ishdir.

Grafiklarning xarakterli raqamlari

Ichki barqarorlik to'plami . S to'plami  Grafikning X G ( X ) ichki barqaror deyiladi, agar S dan ikkita uchi qo‘shni bo‘lmasa, ya’ni har qanday x  uchun S sodir bo'ladi: