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

Орман болатын G суграфы қаңқалы ағаш немесе G суграфының қаңқасы деп аталады.

Ең аз қосылу туралы есеп.(Ең аз салмақты қаңқалы ағаш құру)

Жол тұрғызу есебі түрінде өрнектеуге болатын мына есептің практикалық мағынасы үлкен. Жолдар желісімен қосылуы қажет бірнеше қалалар болсын. Әр екі қаланы қосатын жолдың бағасы белгілі. Мүмкін болатын жолдар желісінің ең арзанын салу қажет болсын. (Жолдардың орнына электр желісін, мұнай құбыры желісі, т.б. алуға болады.

Ең арзан жолдар желісін кескіндейтін граф әрқашан ағаш болады. Себебі, егер цикл бар болса, циклдың бір қабырғасын алып тастауға болар еді, ал төбелер қосылған болып қала берер еді. Есептің математикалық қойылуы. Айталық, бағытталмаған G(V, E), |V|=n, графының әр қабырғасына осы қабырғаның салмағы болып саналатын қандай да бір μ(e) нақты сан бекітілген болсын. G графында салмағы ең аз, ең кіші қосылу, яғни G графының Т қаңқасын салу керек болсын.

μ(T)= .

Сызу жұмысын салмағы μ(e₁ ) ең аз e₁ қабырғасын таңдаудан басталады. Егер мұндай қабырғалар бірнешеу болса, олардың кез келгенін алуға болады. Таңдалған қабырғаға E\{e₁} алынған ең аз салмақты е2 қабырғасы е3 ретінде цикл құрмайтын E\{e₁,е₂} деп алынған ең аз салмақты E\{e₁,е₂, e₃} таңдалады. Қабырға таңдау процесі кез келген қабырға қосу цикл пайда болуына әкеліп соққанға дейін жүргізіледі. Осы граф ең аз салмақты қаңқалы ағаш болып саналады.

Графтардағы маршруттар..
Егер графтың кез келген 2 төбесін қосатын маршрут бар болса, граф байланысты (мықты байланысты) деп аталады,ондай маршрут болмаса ол байланыспаған граф болады.

Маршруттар.Айталық G= Н-граф болсын.

Мұндағы a₁, a₂,…,a_n+1 M U₁ U₂, … , U_n R