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.
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
|
|
|
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:
Do'stlaringiz bilan baham: |