Mövzu 1: Ekonometrika fənninin predmeti, obyekti və həll edəcəyi məsələlər



Yüklə 0,55 Mb.
Pdf görüntüsü
səhifə3/4
tarix04.12.2019
ölçüsü0,55 Mb.
#29803
1   2   3   4
[kitabyurdu.org]-1477769866 ekonometrika

predmetrini təşkil edir. Parametrik proqramlaşdırma məsələsi istehsalın

proqramlaşdırması məsələsinin öyrənilməsi ilə  əlaqədar meydana gəlmişdir. Bu müxtəlif

iqtisadi proseslərin riyazi modelinin qurulması ilə onu optimal planlaşdırmağa imkan

verir.


Indi isə məqsəd funksiyası parametrik olan məsələyə baxaq.

Tutaq ki,

Məqsəd funksiyasının



    əmsalları hər hansı

`



; +

`

 aralığında dəyişir.



Onda uyğunluq üçün məqsəd funksiyasının əmsalını

( ) =


`

+

"



 ilə əvəz edib tədqiq

etmək məqsədə uyğundur. Harda ki,

`

,

"



 hər hansı aralıqda dəyişən sabitlər,

− isə


parametrdir. Bu halda riyai məsələ aşağıdakı şəkilə düşər.

=

(



`



"

)

məqsəd funksiyası verilmişdir.



Məhdudiyyət şərtləri

=   = 1,  (2)

≥ 0  = 1,  (3)

Hər bir


− nın qiyməti üçün ≤ ≤  intervalında (harda ki,   ə   ixtiyari

həqiqi ədədlərdir) elə mənfi olmayan

= ( , , … , ) vektorunu tapmalı ki, (2)

sistemini ödəsin və

(1) funksiyasına minimum qiymət versin.

Qoyulmuş məsələni

 parametrininin dəyişməsindən asılı olaraq araşdıraq.

Nəticədə iki haldan birinə gələrik:

=    üçün optimal plan mövcuddur (  halı);



downloaded from KitabYurdu.org

=  üçün məqsəd funksiyası məhdud deyil (  halı);

Bu halların hər birinə nəzər yetirək:

A – halı:

Tutaq ki,

=  üçün optimal plan alınmışdır. Hansı  ki, hər hansı bazisə uyğun

gəlir.

, , … ,  sistemindən ibarət olan m vektordan təşkil olunmuşdur. Planın



optimallıq şərtinə görə onun qiymətləndirilməsi

−  ≤ 0 şərtini ödəməlidir. Belə ki,

=

`

+



"

. Onda optimallıq şərti belə şəkil alır.

=∝ +


≤ 0  = 1,  (4)

Harda ki,

 ə  − hər hansı həqiqi ədədlərdir. Burada daxil edilir ki,

+

 ≤ 0, = 1,   bərabərsizliklər sisemi birgədir və aşağıdakı həlli var:



≥ − ∝ ⁄   ü ü   < 0 −

üçü


≤ − ∝ ⁄   ü ü   > 0 −

üçü


Tutaq ki,

=

max(− ∝ ⁄ )



−∞ ə ə   ≥ 0

 ̅ =


min(− ∝ ⁄ )

+∞ ə ə   ≤ 0

Onda

=  üçün məsələnin optimal həlli bu məsələnin optimal planı ilə üst – üstə



düşür, bütün

 üçün,


≤ ≤   şərtini ödəyən. Bu halda [ ; ] intervalının sol ucu

örtülmüşdür, yəni

≤ , onda məsələnin həlli üçün sağ ucu da örtmək zəruridir və yaxud

≥  məsələnin həlli olmadığını göstərmək lazımdır.

Beləliklə, əgər  sonludursa və

≥ , və yaxud = +∞, onda həll prosesi sona

çatır.

Bu prosesi davam etdirsək aşağıdakı teoremi isbat etmiş olarıq.



Teorem:

 parametrinin heç olmazsa bir qiyməti üçün yeni bazis optimal plana

uyğundur.

B – halı:

1.

Tutaq ki, aparılmış iberasiya nəticəsində hər bir



 vektoru üçün

+

>



0  qiymətləndirilməsi alınmışdır,

≤ 0. Onda əgər

≥ 0 olarsa ixtiyari  üçün xətti

funksiya aşağıdan məhdud deyil.

2.

Əgər


< 0 olarsa. Onda

+

> 0 bərabərsizliyi bütün



<

`

=



. Buradan ixtiyari

≤ <

`

 üçün optimal plana malik deyil.



Bu qayda ilə sərbəst hədlərdə parametr olan və məhdudiyyət sistemində parametr

olan parametrik məsələlərə də baxılır.

Məqsəd funksiyası

=

Məhdudiyyət şərtləri



downloaded from KitabYurdu.org

= ` +

 = 1,


≥ 0  = 1,

Hər bir


≤ ≤  üçün harda ki,    ə   ixtiyari həqiqi ədədlərdir. Elə bir mənfi

olmayan


= ( , , … , ) vektoru tapmalı ki, məhdudiyyət sistemini ödəsin və məqsəd

funksiyasına minimum qiymət versin.

downloaded from KitabYurdu.org


Mövzu 19: Kəsr – xəti proqramlaşdırma məsələsi

Əgər qeyri xətti proqramlaşdırma məsələsində məhdudiyyət xətti ancaq məqsəd

funksiyası kəsr – xətti olarsa, onda belə məsələni kəsr – xətt proqramlaşdırma məsələsi

adlanır. Kəsr – xətti proqramlaşdırma məsələsinin ümumi şəkli:

( ) =

+

+ … +



+

+ … +


=



(1)

Funksiyasını

Şərtləri daxilində maksimallaşdırmalı (minimallaşdırmalı)

Simpleks metodu

Bir sıra iqtisadi məsələlərdə məzmunu tələb edir ki;

Məqsəd funksiyası

.........................

şərtini ödəsin.

Bu şərt daxilində kəsr – xətti proqramlaşdırma məsələsinin simpleks metodla həll

etmək olar.

Yeni dəyişənlər daxil edək.

.........................

.........................

Onda


(1) − (3) məsələsi aşağıdakı şəkil alar.

..................................

..................................

..................................

.................................

Şərtləri daxilində

downloaded from KitabYurdu.org


Nəticədə xətti proqramlaşdırma məsələsi alınır. Onu Simpleks metodla həll

etdikdən sonra (

(4) −ü nəzərə almaqla) (1) − (2) məsələsinin optimal həllini taparıq.

Dediklərimizi misal üzəridə aydınlaşdıraq.

Misal 1:

...............................

...............................

...............................

Həlli: Şərtə görə bütün dəyişənlər mənfi deyil. Onda

(3) şərti 2 + 3 + 1 > 0

və, uyğun olaraq, əlavə məhdudiyyətlər

...............................

..........................

Məsələ aşağıdakı şəkili alar:

...............................

...............................

...............................

...............................

İkinci, üçüncü və dördüncü məhdudiyyətləri

> 0 − a vurub yeni dəyişənlər

daxil edək:

=  ;


=

Nəticədə xətti proqramlaşdırma məsələsi alarıq:

...........................

...........................

...........................

Bu məsələni Simpleks üsulla həll etsək, alarıq:

...........................

Əvəzləməni nəzərə alsaq:

=

= 20 ;  =



= 12

downloaded from KitabYurdu.org



Beləliklə,

..............................

Kəsr – xətti proqramlaşdırma məsələlərində məqsəd funksiyası ii xətti funksiya

nisbəti şəklində verilməklə, məchulların mümkün dəyişmə oblastını müəyyən edən şərtlər

həmçinin xətli olurlar.

downloaded from KitabYurdu.org



Mövzu 20: Dinamik proqramlaşdırma məsələsi

Dinamik proqramlaşdırma optimal həllin tapılması bir neçə etapın yolu ilə

tapılmasına əsaslanır. Bu mövqe müxtəlif prinsiplərlə həyata keçirilir. Bir sıra məsələlərdə

zaman periodu ilə, digərlərində isə idarəetmə obyektinə görə. Çox vaxt bölgü süni olaraq

yerinə yetirilir. Dinamik proqramlaşdırmanın fundamental prinsipi onun mövqeyinin və

məsələnin etaplara bölünməsi optimaldır.

Belə yanaşma böyük həcmli məsələləri kiçik məsələlərə bölməkdən ibarətdir. Bu

isə hesablamanın həcmini kifayət qədər ixtisar edir və idarə edici həllin tapılmasını

sürətləndirir. Dinamik proqramlaşdırmada hesablama rekurrent aparılır, belə ki, hər hansı

alt məsələnin optimal həlli növbəti məsələnin ilkin verilənləri kimi qəbul edilir.

Misala baxaq. 1 – ci məntəqədən 10 – cu məntəqəyə verilmiş hərəkət marşrutuna

görə optimal marşrutu tapmalı.

..........................................

..........................................

..........................................

..........................................

Şək.1

Sxemdə göstərilmiş hər bir kvadrat məntəqələri göstərir. Özləridə nömrələnib. Bir



məntəqədən digər məntəqəyə gediş haqqı, məsələn i məntəqəsindən İ məntəqəsinə gediş

haqqı


 ilə işarə edək (Bu qiymətlər sxemdə göstərilmişdir).

Tələb olunur ki, 1 – ci məntəqədən 10 – cu məntəqəyə elə marşrutla getmək

lazımdır ki, xərc mimimum olsun.

Həlli: Belmanın rekurrent münasibətlər düsturuna görə

..............................

Harda ki, N – həlldəki etapların sayıdır.

( ) − i məntəqəsindən olan yol üçn minimal xərcin strategiyasına cavab verən

dəyərdir. Harda ki, əgər sonuncu məntəqəyə n addım qalıb.

( ) −  ( ) tapmaq üçün həlldi.

Sonuncu məntəqədən optimal marşrutun tapılması ilə başlayaq.

.....................................

......................................

.......................

.............................

.............................

..............................

.............................

.............................

.............................

Beləliklə, optimal yol təyin olundu.

downloaded from KitabYurdu.org


Mövzu 21: Qeyri – xətti proqramlaşdırma məsələsinin

ümumi qoyuluşu

Əgər

( , , … , ) =



,

= 1,  (1)

= ( , , … , ) =



(2)

,

harda ki,



 ə  − məlum sabitlərdir. Onda həllin mənfi olmaması şərti ilə xətti

proqramlaşdırma məsələsi alırıq. Riyazi proqramlaşdırmanın

(1) − (2)  şərtlərini

ödəməyən istənilən məsələsinə qeyri – xətti proqramlaşdırma məsələsi deyilir.

Qeyri – xətti proqramlaşdırma məsələsi sinfi xətti proqramlaşdırma məsələsi

sinfindən genişdir. Qeyri – xətti proqramlaşdırmada əsas nəticələr elə məsələlərə baxarkən

alınır ki, hansı ki, mədudiyyət sistemi xəttidir, ancaq məqsə funksiyası qeyri – xəttidir.

Hətta belə məsələəlrin optimal həlli yalnız bir sinif məqsəd funksiyalar üçün tapıla bilər.

Xüsusi bir sinif məqsəd funksiyalar üçün tapıla bilər. Xüsusi hallara baxaq. Əgər məqsəd

funksiyası separabellidirsə (

 − funksiyasının cəmidir) və ya kvadratikdir.

Xətti proqramlaşdırma məsələsində ekstremum nöqtələri həllər çoxbucaqlısının

təpə nöqtələrində olurdusa, biz elə misallara baxacayıq ki, qeyri – xətti proqramlaşdırma

məsələsində qeyri – xətti məqsəd funksiyası oblastın daxilində ola bilər4 üzün tilində və

ya çoxbucaqlının təpəsində ola bilər.

Beləliklə, xətti proqramlaşdırma metodunun köməyi ilə, bir təpədən digərinə

keçidihəyata keçirən, optimal həlli almaq olar, o şərt daxilində ki, məqsəd funksiyası əlavə

məhdudiyyətləri ödəyir.

Daha çox çətinlik qeyri – xətti məhdudiyyət olduqda meydana çıxır.

Qeyri – xətti proqramlaşdırma məsələsinə baxılması klassik optimallaşdırma

məsələsi ilə başlayır. Bu zaman

(1) − də tənliklər olur, mənfi olmamaq şərti iştirak etmir

və dəyişənlərin tam ədədli olması

( , , … , ) ə  ( , , … , ) funksiyaları ikinci

tərtibdən az olmayan xüsusi törəməyə malikdirlər və kəsilməzdirlər.

İki dəyişənli qeyri – xətti proqramlaşdırma məsələsinin həllinə nəzər yetirək. Necə

ki, xətti proqramlaşdırmada onlar ola bilsin ki, qrafik üsulla həll edilsin.

Misal 1:


= ( − 4) + ( − 6)  separabelli funksiyasının

+

≥ 1



2 + 3 ≥ 12

≥ 0,


≥ 0

Məhdudiyyət şərtləri daxilində maksimal və minimal qiymətini tapın.

downloaded from KitabYurdu.org


Həlli: n Təyin oblastı

 çoxbucaqlısıdır (şək.1). yəni mümkün olan həllər

oblastı

− dir.


...........(şək. 1)...............

Əgər


=  ( > 0) götürsək, Onda ( − 4) + ( − 6) =  çevrə tənliyini

alarıq.


Q (radiusun kvadratını) – nü azaltmaqla (artırmaqla) Z – in qiyməti uyğun olaraq

azalır (artır).

M – nöqtəsindən, çevrənin mərkəzi kimi müxtəlif radiuslu çevrələr çəksək alarıq:

funksiyanın minimal qiyməti

( ) = 196/13 .  (24/3 ; 36/15) nöqtəsində alır, hansı

ki, çevrə həllər oblastına kəsir. D nöqtəsi künc deyil, onun koordinatları MD və CE düz

xətlərinin tənlikləri sistemindən tapılır.

Z funksiyasının iki lokal maksimumu var:

( ; 0) təpəsində

( ) = 45,  (6; 0) − təpəsində ( ) = 40. Belə ki, ( ) > ( ) onda

− təpəsi

qlobal maksimum olar.

Misal 2. Tutaq ki, fərz edilən həllər çoxluğu əvvəlki misaldakı kimidir.

= ( − 4) + ( − 1)

Bu funksiyanın minimum və maksimum qiymətini tapın.

Həlli: Funksiya minimal qiymətini

(4; 1) nöqtəsində alır. (şək.2)

( ) = 0


Z funksiyasının iki lokal maksimumu var:

Təpələrdə isə

(6; 0) −   ( ) = 5

(0; 4) − ə  ( ) = 25

Buna görə qlobal maksimumu C təpəsində alır.

Misal 3.


=

+   funksiyasının

+

≤ 4


+

≥ 5


≤ 7

 ≤ 6


≥ 0,  ≥ 0

məhdudiyyət şərtlərini ödəyən maksimum və minimum qiymətlərini tapın.

Həlli:

Bu halda mümkün olan həllər çoxluğu iki ayrı – ayrı hissədən ibarətdir.



Z funksiyası Z=17

(1; 4)  ə  (4; 1) – də alır.

Z funksiyası iki lokal maksimuma malikdir.

( ; 6) nöqtəsində ( ) =

 – i

(7; ) – də ( ) = 2417 49



M nöqtəsi qlobal maksimum nöqtəsidir.

Xətti proqramlaşdırma məsələsinin həlli üçün Laqranj vuruqları üsuluna baxaq.

Qeyri - xətti proqramlaşdırma nəzəriyyəsinin praktiki tətbiqi zamanı çox vaxt elə hallara

downloaded from KitabYurdu.org



təsadüf edilir ki, məsələnin riyazi qoyuluşunda məhdudiyyət şərtləri bərabərliklərdən

ibarət olur, məhculların işarələri üzərinə isə heç bir məhdudiyyət qoyulmur. Bununla

bərabər

  öz törəmələri ilə birlikdə keçilməz funksiyalar olurlar, yəni alırıq:



  Məqsəd fuksiyası

Məhdudiyyət şərtləri

 – yə  şərti ekstremum məsələsi yaxud klassik optimallaşdırma məsələsi

deyilir.


Bu məsələnin Laqranj vuruqları üsulu ilə həlli aşağıdakı etaplardan ibarətdir.

I.

 – Laqranj funksiyasının tərtib edilməsi.



Bu məqsədlə Laqranj vuruqları adlanan

 dəyişənləri daxil edilməklə

Laqranj fuksiyası tərtib edilir.

II.


 – nın

 dəyişənlərinə nəzərən xüsusi törəmələrinin tapılması

III. Tənliklər sisteminin həlli

IV. Optimal həllin təyini

Ekstremumun kafilik əlamətinin vasitəsi ilə şübhəli nöqtələr içərisində elə nöqtə

tapılır ki, burada Z(x) məqsəd funksiyası maksimum (minimum) qiymət alır. Bu isə (1),

(2) məsələsinin optimal həlli olur.

V. Z(x) – in ekstremum qiymətinin hesablanması

Optimal həlli (1) ifadəsində nəzərə alınmaqla

 hesablanır.

Misal.

I.

II.



downloaded from KitabYurdu.org

III.

IV. Ikinci tərtib xüsusi törəmələrdən istifadə etməklə asanlıqla göstərmək olar ki,

alınan həlldə Z(x) minimum qiymət alır. Deməli, optimal həlldir.

V.

)



.

downloaded from KitabYurdu.org



Mövzu 22: Qradiyent metodu və onun alqoritmi

Qeyri – xətti proqramlaşdırma məsələsinin qradiyent metodu ilə həlli elə istənilən

metod başa düşülür ki, məqsəd funksiyasının optimal nöqtəyə hərəkətinin istiqaməti bu

funksiyanın qradiyentinin metodu lokal eksremum nöqtəsini məqsəd funksiyasının həllər

oblastının qabarıqlığı (çöküklüyü) şərti ilə tapılmasını göstərir.

Tutaq ki,

 məsqəd funksiyası verilmişdir.

funksiyasının hər hansı

 nöqtəsində qradiyenti.

 

vektorudur.   vektoru



səthinin normalı istiqamətindədir.

 funksiyasının şərtsiz ekstremum tapılması

üçün qradiyent metodunun tətbiqinə baxaq. Yəni məhdudiyyət iştirak etmir. Həll prosesi

iterasiyalıdır.

 başlanğıc nöqtəsi götürülür və yerdəyişmə addımı (  vuruğu ilə

xarakterizə olunan) götürülür, belə ki,  

funksiyasına ən böyük dəyişmə təmin etsin.

 harda ki, yeni nöqtə

  vuruğu

in ektrmumu şərtinin zəruriliyinə görə olan

Çətindən tapılır.   – dən

nı tapıb


müəyyən edirik. Əgər yeni nöqtədə

 olarsa həll sona çatır. Belə halda qradiyent üzrə həll mümkün olunur. Əgər

 olarsa

 nöqtəsi başlanğıc nöqtə qəbul edilir və proses o vaxta kimi davam



etdirilir ki, hələlik sıfır qradiyent alınmışdır. Çox vaxt həllin nəticəsi başlanğıc nöqtənin

seçilməsindən asılı olur, hansı ki, optimal həllə yaxınlaşma başlayır.

Tutaq ki, bizə qabarıq proqramlaşdır məsələsi verilmişdir.

Qradiyent metodunun alqoritmi.

1.

Funksiyanın



 qradiyentini tapmalı və

 tənliyini həll etməli.

 şərtlərini (sistemini) stasionar nöqtələri təyin etməli və bu nöqtələrdə  

funksiyasını

hesablamalı.

2.

 funksiyasının qradiyentinin tapmalı və stasionar nöqtələrini təyin



etməli onları ki, oblastın uyğun

– sərhədində yerləşsin. bunun üçün aşağıdakı sistemi

həll etməli.

sisteminin həllindən eləsi götürürük ki,

 ü və

  şərtini ödəsin.



Məqsəd funksiyasının bu nöqtələrdə qiymətini hesablayırıq.

downloaded from KitabYurdu.org



3.

Bütün sərhəd hiper müstəvilərin kəsişməsini tapırıq. Bunun üçün aşağıdakı

sistemi həll edirik.

Harda ki,

 həllərindən götürürük və bu həllərdə



 in qiymətini

hesablayırıq.

Bu halda, əgər

 olarsa, həllər çoxbucaqlısının bucaq nöqtələrini tapmaq

kafidir və bu nöqtələrdə məqsəd funksiyasının qiymətini hesablayırıq.

4.

Məqsəd funksiyasının qiymətlərinin bütün nöqtələrdə müqayisə edirik və



 və

 götürürük.



Misal:

funksiyasının qradiyent metoduilə maksimumunu tapmalı. İterasiya prosesinin

 nöqtəsindən başlamalı

Həlli:

 nöqtəsində funksiyanın qradiyent təyin edirik.

 nöqtəsini götürürük. Həmin nöqtədə

funksiyanın qradiyentini tapırıq.

Sıfır qradiyent alırıq. Deməli

 nöqtəsi stasionar nöqtədir. Məqsəd

funksiyası qabarıqdır.

 qabarıq



funksiyaların cəmidir).

Onda tapılan nöqtədə

Cavab:

downloaded from KitabYurdu.org



Mövzu 23: Qrafalar nəzəriyyəsi

Boş olmayan

 çoxluğu və

 münasibətlər çoxluğu qraf adlanır.

( , ) ilə işarə

olunur. Əgər

 çoxluğu sonludursa, onda qraf sonlu adlanır.

( , ) qrafı həndəsi nöqteyi nəzərdən sonları verilmiş nöqtələr çoxluğuna daxil

olan boş olmayan nöqtələr çoxluğunu (təpələri) və parçalar çoxluğunu (tillər) göstərir.

Qrafın heç bir tilində yerləşməyən təpələrə izoləedilmiş deyirlər.

Tillə birləşdirilmiş (əlaqələnmiş) təpələrə qonşu təpələr adlanır. əgər iki müxtəlif

til ümumi (ortaq təpəyə malikdirsə onda onlar qonşa tillər adlanırlar. Til və onun istənilən

təpəsi insindent adlanır.

( , ) qrafın başlanğıc və son təpələri üst – üstə düşərsə o ilgək

adlanır.

 və


 təpələrini birləşdirən tillərin sayına bərabər olan

 elementlərindən

ibarət olan matrisə (

ə) qonşuluq matrisi deyilir.

Əgər

 təpəsi


 tilinə insindentdirsə və  əks halda sıfıra bərabərdirsə

elementləri 1 olur, bu elementlərdən təşkil olunmuş

− matrisinə insindent matris

deyilir.


Tilləri birləşdirən və ya hər bir təpə üçün qonşu təpələr çoxluğunun verilməsi üçn

qrafları təpələr (cütləri) kimi vermək olar.

Qrafaların xarakteristikası

Əgər iki müxtəlif təpə yalnız və yalnız bir tillə  əlaqələndirilibsə onda G(X,T)

qapalı tam adlanır. Tam qrafalarda hər bir təpə bir til üzərində yerləşir, belə ki, o yerdə

qalan təpələrdə birləşdirilmişdir. Tam qrafı vermək üçün onun təpələrinin sayını bilmək

kifayətdir. Tam olmayan qrafları tamamlamaq olar, yenilənmiş tillərin əlavə olunması ilə

Tilə insindent, qrafın tillərinin sayına bərabər olan

 ədədinə

( , ) qrafının

təpəsinin dərəcəsi deyilir. Əgər dərəcə cüt (tək) – dürsə - təpə cüt(tək) adlanır.

Teorem 1: Əgər sonlu G(X,T) (ilgəksiz) qrafı n təpə və m tilə malikdirsə, onda

= 2

Teorem 2: (İstənilən) Tək (sayda) təpəli qrafların sayı cütdür.



Teorem 3: İstənilən

( > 2) təpəli qrafda kiçik ölçüdə, iki eyni dərəcəli təpə

həmişə tapılır.

Teorem 4: Əgər

( > 2) təpəli qrafda dəqiqliklə iki təpə eyni dərəcəlidirsə onda

bu qrafda ya

“0” dərəcəli təpə ya da ( − 1) dərəcəli bir təpə həmişə tapılır.

Qrafda yol və tsikl

− dən − a yol qrafın elə tillər ardıcıllığıdır ki, aparıcı  və − dur, hansı ki,

iki qonşu til ortaq təpəyə malikdir və heç bir tillər iki dəfə görüşmür. Yolun uzunluğu bu

yolun tillərinin sayı adlanır.

− dən


−  yol əgər bi təpədən bir dəfədən artıq

keçmirsə o sadə adlanır.

downloaded from KitabYurdu.org


Tsikl – elə yol adlanır ki, başlanğıc və son təpələr üst – üstə düşür. Tsikldə olan

tillərin sayına onun uzunluğu deyilir. Əgər bir təpədən bir dəfədən artıq olmayaraq

keçərsə, onda o sadə tsikl adlanır.

Teorem 5: Əgər

( , ) qrafında bütün sadə tsikllər cüt uzunluğa malikdirsə, onda

qraf heç bir tək uzunluğa malik tskli yoxdur.

Qrafın əlaqəsi, ağaclar

Qrafın iki təpəsi əlaqəlidir, əgər qrafda sonları bu təpələrdə olan yol mövcuddursa,

əks halda əlaqəli deyil. Əgər ixtiyari iki təpə əlaqəlidirsə, onda qraf əlaqəlidir, əks halda

əlaqəli deyil.

Teorem 6:

( , )  qrafı  yalnız  və  yalnız  o  vaxt  sadə  tsikldir  ki,  onun  hər  bir

təpəsinin qüvvəti 2 – yə bərabərdir.

( , ) − də ( , ) tili körpü adlanır o vaxt ki, bu tildə ləğv etdikdə  və

təpələri əlaqəli deyil.

Əlaqəli və tsiklsiz qraf ağac adlanır. Dərəcəsi 1 - ə malik olan təpə.....................

adlanır.

Müstəvi qraflar

( , ) − müstəvi qraf adlanır o vaxt ki, onu müstəvi üzərində elə təsvir etmək

olsun ki, onun heç bir iki tili orta nöqtəyə malik olmasın,  yalnız onların ümumi təpəsindən

başqa. Heç bir iki kəsişməyən qrafın sxemi qrafın müstəvi görüşü adlanır.

Müstəvi görünüşü yalnız müstəvi olur və tərsinə.

( , ) qrafının müstəvi görünüşünün üzü müstəvisinin elə hissəsidir ki, digər

tsiklləri saxlamayan sadə tsikllərlə məhdudlaşan.

Müstəvinin qrafın müstəvi görünüşünün (şəklində verilməsinin) kənarında yerləşən


Yüklə 0,55 Mb.

Dostları ilə paylaş:
1   2   3   4




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin