Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi kengayib

6. Graflarning yig`indisi va kesishmasi 
G
1

{V

1
,E
1

} va {V
2

,E

2
} G

2
graflarning yig`indisi deb G = G
1
U G

2
grflarga 

aytiladi, bunda V = V
1
U V

2
, E = E

1
U E

2
bo`ladi. Quyida graflar 

yig`indisiga misollar keltirilgan:

6.1- rasm 

G
1

va G

2
graflarning kesishmasi deb – shunday G = {G,E} grafga 
aytiladiki, bunda V = V
1

V
2

, E = E

1
E

2
quyida grafning kesishmasiga 
misollar keltirilgan:

6.2- rasm 

---

---

11

Ta’rifdan ko`rinadiki, graflarning kesishmasi bo`sh graf bo`ladi, ya’ni
G = G

1
G

2

=


bo`ladi, agar V

1
V

2

=


bo`lsa, ya’ni ikkala graf bir xil 

belgilangan uchlarga ega bo`lmasa.

Masalan: 

6.3- rasm.

Agar V

1
V

2
=


va E

1
E

2
=


bo`lsa, u holda uchlar to`plami V
1
V

2 

bo`lgan G = G
1
G

2
nol graf bo`ladi. 

6.4-rasm
Agar V

1
= V

2
va E

1
= E

2
bo`lsa, u holda G = G
1
G

2

=G.
Agar V

1
= V

2
va E

1
= E

2
bo`lsa, u holda G = G
1
G

2

= G
1
= G

2
bo`ladi. 

Mavzuga doir mashqlar: 
1. G

1
, G

2
va G

3
graflar quyidagicha berilgan: 

G = {V
1

,E

1
} V

1
= { 1,2,3,4,5,6}; E

1
= {{1,2},{1,3}, {1,4}, {2,3}, {2,6}, 

{3,5}, {3,6}, {5,6}};

G
2

= {V
2

, E

2
}, V

2
= {1,2,3,4,5,6,7,8}, E
2
= {{1,4}, {2,3}, {3,5}, {3,6}, 

{5,6}, {5,7}, {5,8}, {6,7}, {6,8}};

G
3

= {V
3

, E

3
}, V

3
= {3,4,5,6,7,8,9}, E
3
= {{3,5} ,{3,6}, {3,8} {4,6}, 

{5,6},{5,7}, {6,7}, {7,8}, {7,9}, {8,9}}.

---

---

12

2.Grafning uchlari va qirralari sonini toping:
G = G

1
U G

2
; G = G
1
U G

2
G

3
;
G = G

1
U G

2
U G

3
; G = (G

1
U G

2
) G

3
;
G = G

1
G

2

; G = G
1

(G

2
U G

3
).

3. Graflarning uchlarining ko`paytmasini toping:

G = G

1
U G

2
G

3
; G = G

1
G

2

U G
1
G

13
U G

12
G

13
;

G = G

2
U G

1
G

12
U G

22
G

12
G

13
.

---

---

13

7. Graflarning izomorfligi
Mos uchlari mos qirralari bailan tutashtirilgan, yo`nalishlari ham bir xil 
bo`lgan graflar izomorf (o`xshash) graflar deyiladi.
G
1
{V,U} va G

2
{V

1
, U

1
} graflar berilgan bo`lib, V va V

1
, U va U

1
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.

7.1- rasm 

7.2- rasm 

---

---

14
Mavzuga doir mashqlar: 

1. 7.3- rasmdagi graflar ichidan izomorf bo`lmaganlarni ko`rsating.
7.3- rasm
2. Qaysi savollarga “ha” deb javob berish mumkin: 

a) Qirralari bo`lmagan graflar izomorf bo`lish mumkinmi?

b) 1 xil sondagi uchlarga ega bo`lgan 2 ta graf berilgan har qanday 
belgilanishda ham bu graflarning izomorfligi saqlanib qoladimi?
c) 2 ta bir hil sondagi uchga ega bo`lgan 1 jinsli graflar berilgan. Bu graflar 
uchlarining har qanday ixtiyoriy belgilanishi izomorflik shartlarini saqlab
qoladimi? 
d) Izomorflik tushunchasini psevdograflarga qo`llash mumkinmi?
e) Bo`sh bo`lmagan graf o`zining qism grafga izomorf bo`lishi mumkinmi? 
f) Qism graf, uchlarining soni o`zining uchlari soniga teng bo`lgan nol
grafga izomorf bo`lishi mumkinmi? 
g) Ekvivalentnlik munosabati izomorf bo`ladimi?
3. Graflar izomorfmi? Javobingizni asoslang. 

7.4- rasm 

4. Graflarning izomorfligini isbotlang.
7.5- rasm 

---

---

15

5. Graflarning izomorfligini isbotlang.

7.6- rasm

6. Graflar izomorf emasligini isbotlang. 

7.7- rasm 

7. Graflar izomorf emasligini isbotlang. 

7.8- rasm 

---

---

16