9-mavzu: Graflar nazariyasining asosiy tushunchalari. Graflarning ba’zi turlari. Graflarning berilish usullari. Qo`shnilik va insidentlik matritsalari. Graflarning izomorfligi. Qoshnilik. Insidentlik. Uchning darajasi

Graflarning yig`indisi va kesishmasi

{V₁,E₁ } {V₂,E₂} G₁ va G₂ graflarning yig`indisi deb – G = G<sub>1</sub> U G<sub>2</sub> grflarga aytiladi, bunda V = V<sub>1</sub> U V<sub>2</sub> , E = E<sub>1</sub> U E<sub>2</sub> bo`ladi. Quyida graflar yig`indisiga misollar keltirilgan:

13- rasm

G₁ va G₂ graflarning kesishmasi deb – shunday G = {G,E} grafga aytiladiki, bunda V = V₁ V₂ , E = E₁ E₂ quyida grafning kesishmasiga misollar keltirilgan:

14- rasm

Ta’rifdan ko`rinadiki, graflarning kesishmasi bo`sh graf bo`ladi, ya’ni G = G<sub>1</sub> G<sub>2</sub> = bo`ladi, agar V₁ V₂ = bo`lsa, ya’ni ikkala graf bir xil belgilangan uchlarga ega bo`lmasa.

M asalan:

15- rasm.

Agar V₁ V₂ = va E₁ E₂ = bo`lsa, u holda uchlar to`plami V₁ V₂ bo`lgan G = G<sub>1</sub> G<sub>2</sub> nol graf bo`ladi.

16-rasm

Agar V₁ = V₂ va E₁ = E₂ bo`lsa, u holda G = G₁ G₂=G.

Agar V₁= V₂ va E₁= E₂ bo`lsa, u holda G = G<sub>1</sub> G<sub>2</sub> = G<sub>1</sub> = G<sub>2</sub> bo`ladi.

Graflarning izomorfligi

Mos uchlari mos qirralari bailan tutashtirilgan, yo`nalishlari ham bir xil bo`lgan graflar izomorf (o`xshash) graflar deyiladi.

G₁ {V,U} va G₂ {V₁, U₁} graflar berilgan bo`lib, V va V<sub>1</sub> , U va U<sub>1</sub> o`rtasida biyeksiya o`rnatish mumkin bo`lsa, bunday graflar izomorf graflar deyiladi. Demak, uchlari va qirralari har xil bo`lgan graflar izomorf bo`lmaydi.

Masalan, Quyida keltirilgan graflar izomorf graflardir.

1 8- rasm

19- rasm

Qo`shnilik va insidentlik matritsalari

Graflarning qo`shnilik matritsasi deb – tartibi n*n bo`lgan (v_ij) matritsaga aytiladi.

Bunda A_ij=

Masalan:

27- rasm

Qo`shnilik matritsiyaga ko`ra matritsaning ko`rinishini aniqlish mumkin. Diagonal va bosh faqat 0 lardan iborat bo`lsa, bunday graf oddiy graf bo`ladi. Agar bosh diagonal 0 lardan iborat bo`lib, boshqa o`rinlardan 1 dan boshqa sonlar ham uchrasa, u holda bu graf multigraf bo`ladi. Agar bosh diagonalda 0 dan farqli sonlar ham uchrasa, u holda graf halqaga ega va demak u psevdograf bo`ladi.

Qo`shnilik ,matritsiya yordamida har bir uchning darajalarini aniqlash mumkin. buning uchun mos ustun yoki satrlardagi sonlar qo`shilib bu yig`indiga bosh diagonallarini shu satr (yoki ustun) bilan kesishmasida to`g`ri qo`shiladi.

Agar matritsiyaning barcha sonlarining yig`indisiga barcha diagonal sonlarini qo`shsak va natijani 2 ga bo`lsak, u holda grafning barcha qirralari soni topiladi.

Insidentlik matritsasi

Grafning insidentlik matritsasi ||A_ij|| (i=1,...,m, j=1,..., n) deb m ta qator va n ta ustundan iborat quyidagi ko`rinishda hosil qilingan matritsaga aytiladi:

a) A_ij matritsaning satrlariga G ning uchlari, ustunlariga G ning qirralari mos qo`yiladi;

b) U holda

A_ij=

Agar G yo`naltirilgan graf bo`lsa, u holda

A_ij=

Bu yerda v_j – j-uchni, e_i – i-qirrani aniqlaydi.

Masalan:

28- rasmga mos qo`shnilik matritsasi quyidagicha bo`ladi:

rasmda tasvirlangan grafning insidentlik matritsasi quyidagicha bo`ladi:

. 29- rasm

Qoidadan foydadanib insidentlik matritsasini hosil qilamiz.

Graflar faqat va faqat insidentlik matritsalari bir-birlaridan satrlarining o`rinlarini va ustunlarining o`rinlarini mos almashtirishlar yordamida hosil bo`lsagina izomorf bo`ladi.