2-ta’rif a to‘plamning har bir elementi b to‘plamda mavjud, aksincha, b to‘plamning har bir elementi a to‘plamda ham mavjud bo‘lsa, va a va b to‘plamlarni teng (tengkuchli) deb atab, buni A=B yoki B=A belgi bilan ifodalaymiz. 3-ta’rif
Download 1.22 Mb.
|
Diskret nazarya
- Bu sahifa navigatsiya:
- 13- mavzu.
|
t e o r e m a . Har qanday chekli grafni 3 o‘lchovli Evklid 1 fazosida 2
geometrik ifodalash mumkin Petersen 4 grafi 5 deb ataluvchi 8- shaklda tasvirlangan graf ham kubik grafdir. Agar graf tekislikda geometrik ifodalanishga ega bolsa, u holda bunday graf tekis (yassi) graf deb ataladi. Bunday graf tekislikda yotuvchi graf deb ham atalishi mumkin. Tekis grafga izomorf graf planar graf deb ataladi. Orentirlangan grafning Uchlari qoshnilik matrisasi(m*m) deb A=(i=1,2,…..,m , j=1,2,…m) matrisaga aytiladi. t e o r e m a . Graflar faqat va faqat uchlari qo‘shniligi matritsalari birbirlaridan satrlarining o‘rinlarini va ustunlarining o‘rinlarini mos almashtirishlar yordamida hosil bo‘lsagina izomorf bo‘lishadi. C=(i=1,2,…n , j=1,2…, n) (n*n) matritsa grafning qirralari qo‘shniligi matritsasi deb ataladi. Elementlari G grafning i va j uchlarini tutashtiruvchi qirralar soniga teng bolgan A=(I,j=1,2,….,m) matritsa oriyentirlanmagan multigrafning uchlari qo‘shniligi matritsasi deb ataladi. (n*n) matritsa grafning qirralari qo‘shniligi matritsasi deb ataladi. t e o r e m a . Graflar (orgraflar) faqat va faqat insidentlik matritsalari bir-birlaridan satrlarining o‘rinlarini va ustunlarining o‘rinlarini mos almashtirishlar yordamida hosil bo‘lsagina izomorf bo‘lishadi. 13- mavzu. Izomorfizm tushunchasi. Graflarning izomorfligi.(graf ustida amallar). Graflar ustida sodda amallar. Graflar ustida turli amallar bajarish mumkin, masalan, graflarni birlashtirish, biriktirish, ko„paytirish, grafni qismlarga ajratish va hokazo. Eng sodda amallardan biri sifatida grafdan uchni olib tashlash amalini keltirsa boladi. Bu amalni qo„llash berilgan grafning uchlari to„plamidan birorta element yo„qotishni (olib tashlashni) anglatadi. Eng sodda amallar qatoriga grafdan qirrani (yoyni) olib tashlash amalini ham kiritish mumkin. Bu amalga ko„ra berilgan grafning qirralari (yoylari) toplamidan birorta element yo„qotiladi (olib tashlanadi) Bolinish graflari izomorf bo„lgan graflar gomeomorf graflar deb ataladi. Agar birlashtirilayotgan graflarning uchlari toplamlari kesishmasa, u holda bu graflarning birlashmasi diz’yunkt birlashma deb ataladi. Download 1.22 Mb. Do'stlaringiz bilan baham: 
|