Дәріс тақырыбы: Графтар теориясы (5 сағат) Негізгі сұрақтар

жүктеу 0,75 Mb.

бет	7/23
Дата	03.02.2022
өлшемі	0,75 Mb.
	#35463

1 2 3 4 5 6 7 8 9 10 ... 23

лекция

Ішкі графтар және графтардың бөлігі. Граф бөліктерімен операциялар
Граф бөліктеріне қолданылатын амалдар.
Графтар мен бинарлы қатынастар.

Анықтама: G₁, G₂графтарының бірігуі деп G₁UG₂=1UM₂,R₁UR₂> графын айтады.

Анықтама:ЕгерМ₂∩М₂= онда G₁,G₂графының қиылысуы деп, G₁∩G₂=1∩M₂,R₁∩R₂> графын айтады.

Анықтама: G₁, G₂графтарының сақиналы қосындысы деп G₁G₂=1UM₂,R₁R₂>, мұндағы R₁R₂=( R₁\R₂)U(R₂\R₁).

Мысалы G₁ және G₂ графтары берілсін.

G₁=< {a₁, a₂, a₃}, {[a₁, a₂], (a₂, a₃)}>;

G₂=< {a₁, a₂, a₄}, {(a₁, a₂, ), (a₄, a₁)}>;

Табу керек: G₁U G₂, G₁∩G₂, G₁G₂?

Шешуі: Анықтама бойынша:

G₁UG₂=<{a₁, a₂, a₃, a₄},{[a₁, a₂], (a₂, a₃), (a₄, a₁)}>;

G₁∩G₂=< {a₁, a₂}, {(a₁, a₂)}>.

G₁G₂=<{ a₁, a₂, a₃, a₄}, {( a₂, a₁), (a₂, a₃), (a₄, a₁)}>;

G₁, G₂ графтарының қосылуы деп

G₁+ G₂ =

Мына суреттің а пунктіндегі G₁, G₂ графтарының қосындысы б пунктте көрсетілген.

G₁, G₂графтарының көбейтіндісі деп G₁xG₂=1xM₂, R>, мұндағы ((a₁,b₁), (a₂, b₂)) R тек сонда ғана, егер a₁=a₂ және (b₁,b₂) R₂ немесе b₁=b₂ және (a₁,a₂) R₁.

Ішкі графтар және графтардың бөлігі.

Граф бөліктерімен операциялар.

Анықтама: Егер М¹М және R¹R∩(M¹)²болса, яғни G¹ графының төбелер жиыны G графы төбелер жиынына, ал G¹қабырғалар жиыны G графының қабырғалар жиынына жатса G¹- G бөлігі деп аталады.

АнықтамаАйталық. G=,G¹=1,R¹> графтары берілсін. Егер М¹М және R¹=R∩(M¹)²болса, яғни G¹ графының төбелер жиыны G-ң төбелер жиынында жатса ал G¹-ң доғалары екі жағымен де G графына жатса G¹–G графының ішкі графы деп аталады.

Анықтама.Егер Н графыныңтөбелер жиыны V(H) мен қабырғалар жиыны E(H) G графының сәйкесінше төбелері мен қабырғалар V(G), E(G) жиындарында жатса және , онда Н графы G графының бөлігі деп аталады .

Анықтама Егер , G графының бөлігі Н суграф деп аталады. Егер G графының кез келген төбесі Н графының ең болмаса бір қабырғасына инцидентті болса , онда бағытталмаған Н графы G графын жабады дейміз.

Мысалы:а) G=<{1, 2, 3, 4}, {[1, 2], [1, 3], [1,4], [2,3], [3,4]}>

б)G¹=<{1, 2, 3}, {[1, 2], [1, 3], [2, 3]}>-G ішкі графы (М¹МR¹, R¹=R∩R¹)

в)G¹¹=<{1,2,3},{[1,2],(2,3)}>-G графының бөлігі (M¹¹М,R¹¹R∩(M¹¹)²)

Граф бөліктеріне қолданылатын амалдар.

Граф бөліктеріне төмендегідей амалдар орындалады:

Н-бөліктің толықтаушы -G-графының Н-ға жатпайтын барлық қабырғалар жиынымен анықталады. , мұндағы E(G)-G-графының қабырғаларының жиыны.

-G графының Н₁, Н₂бөліктерінің қосындысы :

- және ;

- G графының Н₁, Н₂ бөліктерінің көбейтіндісі : және ;

Егер H₁, H₂ бөліктерінің ортақ төбелері болмаса, яғни , демек ортақ қабырғалары да жоқ , онда H₁, H₂ бөліктері төбелері бойынша қиылыспайды.

Егер H₁, H₂ бөліктерінің ортақ қабырғалары болмаса ,онда H₁ , H₂ бөліктері қабырғалары бойынша қиылыспайды.

Егер болса онда тура қосынды деп аталады.

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

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

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

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

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

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

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

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

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

жүктеу 0,75 Mb.

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

1 2 3 4 5 6 7 8 9 10 ... 23