Graflarga doir misollar

GRAFLARGA DOIR MISOLLAR

1. 
   O`zbekiston respublikasi hududidagi aeroportlar to`plamini V bilan hamda uchib qo`nayotgan samoloyotlar to`plamini U bilan belgilaylik.
   

u holda (V,U) juftlikni graf sifatida qarash mumkin.

Grafning uchlari sifatida aeroportlani yoylar sifatida samolyotlarning uchib qo`nishlarini olishimiz mumkin.

Aga bi aeroportdan ikkinchishiga samoloyotlar borib qaytsa bu holatni karrali yoylar orqali va qandaydir bir aeroportdan samolyot ko`tarilib qaytib qo`nsa uni sirtmoq shaklda ifodalashimiz mumkin.

Дарахтлар. Дарахт деб, ҳалқага эга бўлмаган боғланган графга айтилади. Дарахтларни йиғиндиси ўрмон деб аталади. Шундай қилиб, ўрмоннинг компонентлари дарахт ҳисобланади. 2.1-расмда бешинчи тартибли дарахтлар келтирилган.



Тўлиқ графлар. Графда унинг иҳтиёрий иккита чўққиси бир-бирига боғланган бўлса тўлиқ граф деб аталади. Масалан, граф G= m та чўққидан иборат бўлса, ундаги қобиқлар сони m(m-1)/2 га тенг бўлади (2.2-расм).



Юлдузли граф деб, бошланғич чўққиси х_i ва қолганлари Х/x_j тугаш чўққилардан иборат бўлиб, қобиқлар ҳосил қилган графга айтилади (2.3-расм).

x_j

x_i

Мультиграф ва псевдограф. Айрим ҳолларда иккита чўққининг боғланиши биттадан кўп қобиқлар билан ифодаланади. Бундай ҳолларда мультиграф тушунчаси ҳосил бўлади. Мультиграф бу (Х, U) иккилигидан ташкил топган бўлиб Х – бўш бўлмаган чўққилар тўплами, U эса иккилик чўққилар тўпламчасидан ташкил топган қобиқлар тўплами. Тўпламчалар параллел қобиқлардан иборат (2.4.,а-расм).

Шундай килиб, агар иҳтиёрий графда бирорта қобиқлар карали ёки параллел бўлса, бундай графлар мультиграф дейилади.

	x2		x2
х1	x4	х1	х4	x3
		x3

x5 а

x5

бўлмаган чўққилар тўплами, U эса тартибсиз чўққилар иккилиги – албатта ҳар хил бўлмаган қобиқларнинг мажмуаси.

Йўналтирилган ва йўналтирилмаган графлар. Агар графни қобиқларини аниқлашда уларни бошланғич ва тугаш чўққиларининг тартиби инобатга олинмаса, яъни:

U=(x_i, x_j)=(x_j, x_i)

бўлса, у ҳолда U йўналтирилмаган қобиқ, агар уларнинг тартиби зарурий бўлса, йўналтирилган қобиқ деб аталади. Бунда x_i - қобиқнинг бошланғич чўққиси, x_j эса тугаш чўққиси ҳисобланади.

Граф йўналтирилмаган деб аталади, агар унинг ҳар бир қобиғи йўналтирилмаган бўлса ва йўналтирилган деб аталади, агар ҳамма қобиғи йўналтирилган бўлса.

Йўналтирилмаган графлар 2.5-расмда ва йўналтирилган графлар 2.6-расмда тасвирланган.

.5-расм

2.6-расм