Қазақстан республикасының білім және ғылым министірлігі

Графтар мен бинарлы қатынастар

жүктеу 21,8 Mb.

бет	95/214
Дата	09.01.2018
өлшемі	21,8 Mb.
	#7265
түрі	Мазмұндама

1 ... 91 92 93 94 95 96 97 98 ... 214

Графтар мен бинарлы қатынастар.

V жиынында берілген R қатынасына өзара бір мәнді анықталған,

орындалса ғана

қабырғасы бар болатын V төбелер жиындарымен қабырғалар еселі емес бағытталған G(R) графы сәйкес келеді.

1-мысал: Симметриялы, антисиметриялы, рефлексивті, антирефлексивті, транзитивті R бинарлы қатынасына өзара бір мәнді сәйкес G графының қандай ерекшеліктері бар?

Айталық , R бинарлы қатынасы

жиынында анықталсын.

а) симметриялы R қатынасына еселі қабырғалары жоқ,

орындалса ғана

қабырғасы бар болатын бағытталмаған G(R) графы сәйкес келеді (симметриялы болғандықтан

б) Антисиметриялы R қатынасына еселі қабырғаларсыз,(әртүрлі төбелерге қарама-қарсы бағытталған қабырғалары бар төбелер болмайтын) өзара бір мәнді бағытталған G(R) графы сәйкес келеді .

в) Егер R рефлексивті болса, барлық төбелерінде ілгектері бар еселі қабырғаларсыз G(R) графы сәйкес келеді.

г) Егер R антирефлексивті болса, еселі қабырғаларсыз G(R) графында бір де бір ілгек болмайды.

д) Егер R транзитивті болса, еселі қабырғаларсыз G(R) графының әрбір

және

қабырғалар жұбына оларды тұйықтайтын

қабырғасы бар болады.

Негізгі әдебиет: 1 [161-180]; 2[108-114].

Қосымша әдебиет: 7[88-130] .

Бақылау сұрақтары:

Қандай графтар бағытталған графтар деп аталады?
Қандай графтар бағытталмаған деп аталады?
Графтарда қандай төбелер сыбайлас төбелер деп аталады?
Төбелер дәрежесі деген не?
Графтардың берілу тәсілдерін атаңыз.
Графтармен қандай операциялар орындалады.

жүктеу 21,8 Mb.

Достарыңызбен бөлісу:

1 ... 91 92 93 94 95 96 97 98 ... 214