Navzu: Bog`langan graflar. Marshrut, zanjir, sikllar. Eyler va

22-23-navzu: Bog`langan graflar. Marshrut, zanjir, sikllar. Eyler va

Gamilton graflari

Bog`langan graflar. Marshrut, zanjir, sikllar

Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf bog‘langan graf deb ataladi.

Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo`lsa, u holda bu ikkita uch bog‘langan deyiladi. Bunday uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to‘plami bo‘yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog‘lamlilik komponentlari deb ataluvchi bog‘lamli qismlarning birlashmasi deb qarash mumkin.

Tekis
G  (V ,U )
graf uchun
m  r 1 n  k
tenglik o`rinlidir, bunda
m  V ,

n  U , r – yoqlar soni, k – bog‘lamlilik komponentalar soni.


n uzunlikdagi marshrut deb n ta qirraning bo`sh bo`lmagan ketma-ketligiga aytiladi. Qo`shni yoylar ketma-ketligi yo`l, qo`shni qirralar ketma-ketligi zanjir deyiladi. Boshqacha ta’riflansa, takroriy qirralarga ega bo`lmagan marshrut zanjir deyiladi. Yopiq zanjir esa sikl deyiladi.

Eyler grafi. Gamilton grafi. Sodda zanjirlarni aniqlash

Yo'naltirilmagan G graf berilgan bo`lsin. Eyler sikli shunday siklki, unda grafning ma'lum bir uchidan chiqib, barcha qirralardan faqat bir marta o'tib, yana shu uchga qaytib kelishi kerak.

Grafda Eyler sikli mavjud bo`lishi uchun:

1. 
   Graf bog`langan bo`lishi;
   
2. 
   Grafning barcha uchlarining darajalari juft bo`lishi kerak; Grafda Eyler zanjiri mavjud bo`lishi uchun:
   

1. 
   Graf boglangan bo`lishi;
   
2. 
   Grafning 2 ta uchi darajalari toq bo`lib, qolgan barcha uchlarining darajalari juft bo`lishi kerak.
   

Grafning barcha qirralaridan bir martadan o`tgan zanjir eyler zanjiri
deyiladi

Agar G yo`naltirilmagan grafda Eyler sikli mavjud bo`lsa, bunday grafga eyler grafi deyiladi. Boshqacha aytganda,grafning barcha uchlaridan o`tuvchi karrali qirralar va ilmoqlarga ega bo`lmagan graf eyler 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.

36. 
    rasm
    

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.

36. 
    rasm
    

36. 
    rasm
    

4. 
   m i s o l . 37- rasnda tasvirlangan graflar bir-biriga izomorfdir.
   
5. 
   m i s o l . 38- 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.
40- rasmda tasvirlangan Petersen grafi deb

ataluvchi graf ham kubik grafdir.
Agar graf tekislikda geometrik ifodalanishga ega
39-rasm

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.
40- rasm