|
Navzu: Bog`langan graflar. Marshrut, zanjir, sikllar. Eyler va
|
| bet | 3/3 | | Sana | 08.02.2024 | | Hajmi | 132,99 Kb. | | #153003 |
Bog'liq graflareyler grafi deyiladi.
Agar bog`liqli grafda barcha uchlar juft bo`lsa, bu graf eyler sikliga ega bo`ladi.
Teskari tasdiq ham o`rinli: agar graf eyler sikliga ega bo`lsa, uning barcha uchlari darajalari juft bo`ladi.
Misol.
Agar grafda oddiy cikl mavjud bo`lib, bu ciklda grafning barcha uchlari qatnashsa, bunday sikl Gamilton sikli deyiladi. Oddiy zanjir Gamilton zanjiri deyiladi, agar bunday grafda uchlarning hammasi ishtirok etsa. Boshqacha aytganda, agar zanjir grafning barcha uchlaridan bir martadan o`tsa, bunday zanjirga gamilton zanjiri deyiladi. Unda uch va qirralar takrorlanmasligi kerak.
Grafda Gamilton tsikli mavjud bo`lsa, bu graf Gamilton grafi deyiladi. Yoki agar bog`liqli grafda har bir uchdan faqat bir martadan o`tuvchi sikl mavjud bo`lsa, bunday graf gamilton grafi deyiladi.
m i s o l . rasmda tasvirlangan graflarning har biri oltita uch va yettita qirralarga ega bo`lib, ular izomorf emas.
Hammasi bo`lib beshta qavariq muntazam ko‘pyoqli mavjudligi qadimdan ma’lum (Evklid isbotlagan): tetraedr, kub, oktaedr, dodekaedr va ikosaedr. Bu ko‘pyoqlilarning umumiy nomi ham bor – Platon jismlari. Barcha Platon jismlariga mos graflar tekislikda geometrik ifodalanadi. Masalan, tetraedr va kubga mos graflarning geometrik ifodalanishi 39- rasmda tasvirlangan.
Platon jismlaridan tetraedr, kub va dodekaedr kubik grafga misol bo`ladi.
rasmda tasvirlangan Petersen grafi deb
ataluvchi 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 atalishi mumkin.
Boshqacha so`zlar bilan 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 graflar tekis graflardir.
Tekis grafga izomorf graf planar graf deb ataladi.
rasm
• Gamilton grafi. Agar grafda oddiy cikl mavjud
bo'lib, bu ciklda grafning barcha tugunlari
qatnashsa, bunday tsikl Gamilьton tsikli
deyiladi.
• Oddiy zanjir Gamilton zanjiri deyiladi, agar
bunday grafda tugunlarning hammasi ishtirok
etsa. Tugun va qirralar takrorlanmasligi kerak.
•
Grafda Gamilьton tsikli mavjud bo'lsa, bu
graf Gamilьton grafi deyiladi.
|
| |
