2. Элементы теории множеств

Rasmda ko'rsatilgan digrafik bo'lmagan G uchun qo'shnilik matritsasi a quyidagi ko'rinishga

Digraf qo'shnilik matritsasi

Rasmda ko'rsatilgan G digrafi uchun qo'shnilik matritsasi quyidagi ko'rinishga

Grafiklarni o'rnatish usullari

4) Insidans matritsasi .

Insidans matritsasi B - jadval, qatorlar ular grafikning uchlariga, ustunlari esa qirralarga mos keladi .

Matritsa elementlari quyidagicha aniqlanadi:

Grafiklarni o'rnatish usullari

1) digraf bo'lmaganlar uchun

1 agar v i uchi e j chetiga tushsa ;

b ij = 0 aks holda _

Digraf insidans matritsasi

2) digraf uchun

-1 agar chekka e j v i tepasiga kiradi ;

1 agar e j qirrasi v i uchidan chiqsa ;

b ij = 2 agar e j qirrasi v i uchidan aylana bo'lsa ;

0 agar e j va v i hodisa bo'lmasa.

G

Marshrut

G ustunidagi marshrut =(V,E) cho'qqilarning chekli o'zgaruvchan ketma- ketligidir va qirralari v 0 , e 1 , v 1 , e 2 ,…,v k-1 , e k , v k , cho‘qqilarda boshlanib, tugaydi va v i-1 va v i chekka uchlari e i , 1  i  k .

Marshrut

Agar marshrutning oxirgi uchlari boshqacha bo'lsa ( v 1 , e 1 , v 2 , e 2 , v 3 , e 3 , v 6 , e 9 , v 5 , e 7 , v 3 , e 11 , v 6 ) marshrut ochiq deb ataladi. ).

oxirgi uchlari bir xil bo'lsa ( v 1 , e 1 , v 2 , e 2 , v 3 , e 7 , v 5 , e 3 , v 2 , e 4 , v 4 , e 5 , v ) yo'nalish yopiq deb ataladi . 1 ) .

G

Zanjir

, agar uning barcha qirralari aniq bo'lsa, zanjir deyiladi .