Jild. 3, No 4, 2015 issn 2309-0405

Vertex rang berish
faqat bir asrdan keyin Kennet Appel va Volfgang Xaken tomonidan hal qilindi. Bu vaqt grafik nazariyaning
tug'ilishi deb hisoblanadi. Caley daraxtlarni o'rganish uchun differensial hisobdan ma'lum analitik shakllarni
o'rgandi. Bu nazariy kimyoga juda ko'p ta'sir ko'rsatdi.
1. Tarmoqdagi eng qisqa yo'l algoritmi 2. Minimal kenglikdagi daraxtni topish 3. Grafik tekisligini topish 4. Qo'shni
matritsalarni topish algoritmlari. 5. Ulanishni topish algoritmlari 6. Grafikdagi sikllarni topish algoritmlari 7.
Ma’lumotlar strukturasidagi elementni izlash algoritmlari (DFS, BFS) va boshqalar. Grafik nazariyasi
tushunchalarini qo'llab-quvvatlash uchun turli xil kompyuter tillari qo'llaniladi. Bunday tillarning asosiy maqsadi
foydalanuvchiga grafiklar ustida amallarni ixcham va tabiiy shaklda shakllantirish imkonini berishdir. Ba'zi grafik
nazariy tillari:
1. SPANTREE – Berilgan grafikdagi kengayuvchi daraxtni topish uchun.
Machine Translated by Google

---

1
0
0
P
0
t3
t2
L(G) chiziqli grafik oddiy grafik boÿlib, L(G) ning choÿqqisini toÿgÿri boÿyash G ning bir xil ranglar soniga toÿgÿri chekka
rang berishini beradi. Shunday qilib, muammoni L (G) ning minimal to'g'ri cho'qqi rangini topish orqali hal qilish mumkin.
Masalan, t1, t2, t3, t4, 4 ta o'qituvchi borligini ko'rib chiqing . va 5 ta fan n1, n2, n3, n4, n5 o‘qitilishi kerak, deydi. O'qitish
talab matritsasi p = [pij] sifatida berilgan.
n5
t4
n1
n2
t1
n3
n4
www.idpublications.org
jild. 3, No 4, 2015
ISSN 2309-0405
57-bet
Akademik tadqiqotlar va mulohazalarning xalqaro jurnali
Progressive Academic Publishing, Buyuk Britaniya
1
0
0
0
0
1
Cheklovlar murakkab bo'lsa, o'qituvchilarga sinflar va fanlarni taqsimlash asosiy masalalardan
biridir. Bu muammoda grafik nazariyasi muhim rol o'ynaydi. "N" fanlari bo'lgan "t" o'qituvchilari
uchun "p" davrlarining mavjud soni jadvalini tuzish kerak. Bu quyidagicha amalga oshiriladi. Ikki
tomonlama grafik (yoki bigraf - cho'qqilarini ikkita ajratilgan U va V to'plamlariga bo'lish mumkin
bo'lgan grafik, har bir chekka U dagi cho'qqini V dagi bittaga bog'laydi ; ya'ni U va V mustaqil
to'plamlar) G bu erda cho'qqilar fakultet soni t1, t2, t3, t4, ……. tk va n mavzular soni n1, n2, n3,
n4, ……. nm shunday bo'lishi kerakki, uchlari "pi" qirralari bilan bog'langan. Taxminlarga ko'ra,
istalgan davrda har bir o'qituvchi ko'pi bilan bitta fandan dars berishi mumkin va har bir fanni
ko'pi bilan bitta o'qituvchi o'qitishi mumkin. Birinchi davrni ko'rib chiqing. Ushbu yagona davr
uchun jadval grafikdagi moslikka mos keladi va aksincha, har bir moslik O'qituvchining o'sha
davr mobaynida o'qitiladigan fanlar bo'yicha mumkin bo'lgan topshirig'iga mos keladi. Shunday
qilib, vaqt jadvalini tuzish muammosining yechimi G grafigining chekkalarini mos keladiganlarning
minimal soniga bo'lish orqali olinadi. Bundan tashqari, qirralarning ranglarning minimal soni bilan
bo'yalgan bo'lishi kerak. Bu muammoni vertex rang berish algoritmi bilan ham hal qilish mumkin.
“ G ning L(G) chiziqli grafigi G ning uchlari va qirralari teng songa ega va L(G) dagi ikkita cho‘qqi,
agar G ning tegishli qirralari umumiy cho‘qqi bo‘lsa, bir chekka bilan bog‘lanadi.