1 пєнініњ ОЌу программасы syllabus

1. А матрицасының бірінші бағанын қарап шығыңыз. Бұл бағаннан 1 бар жолды табыңыз да оған бірін жолды қосыңыз.

2.(1) пунктте құрылған матрицаның 2 бағанын қараңыз. Бұл бағаннан 1 бар жолды тауып, оған 2- жолды қосыңыз.

3.(2) пунктте құрылған матрицаның 3 бағанын қараңыз. Бұл бағаннан 1 бар жолды тауып оған 3- жолды қосыңыз.

4.Осылайша алдыңғы қадамда құрылған матрицаның келесі бағандарын қарауды жалғастырасыз. Одан 1 бар жолды тауып, оған зерттеліп отырған бағанға сәйкес жолды қосасыз.

5. Барлық бағандар қарастырылып болғанша жалғастырасыз.

Сонымен С матрицасында G графының әр түрлі элементтерінің арасындағы байланыстың бар я жоқ екендігі турлы ақпарат болады(маршруттар арқылы).

Егер G_i- бағытталмаған байланысты граф болса, онда С байланыс матрицасының барлық элементтері 1-ге тең.

Жалпы (жағдайда) алғанда бағытталмаған графтың байланыс матрицасы граф төбелері жиынын байланыс компоненттеріне бөлетін эквиваленттік қатынас матрицасы болып табылады.

Бұл матрицаның анықталуынан, егер С-жеткізу матрицасы болса, Q=C^Т.Бұл екі матрицаларды ( Q, C) графтың мықты компоненттерін табуға пайдалануға болады.

S=Q*C матрицасын қарастырамыз , мұндағы _* операциясы С мен Q матрицаларының сәйкес элементтерін көбейту дегенді көрсетеді, яғни:

s_ij=q_{ij *} с_ij

i

j

Ең қысқа жолда төбелер мен доғалар (қабырғалар) қайталанбайды. Шынында да, егер Р₀ маршрутында Р₀: х = z, e₁, z₁, …., z_p-1, e_p, z_p = у z_i=z_j бар болса, онда Р₀ маршрутын z_і-ден z_j-ға дейінгі кесіндіні алып тастап қысқартуға болар еді, яғни Р₀ -ді x = z₀, e₁, ..., e_i, z_i, e_j+1, ..., z_p-1, e_p, z_p = у маршрутымен алмастырар едік. Сондықтан да шын мәнінде ең қысқа маршрут қарапайым шынжыр болады. «Ең қысқа жол», «Ең қысқа маршрут», «Ең қысқа шынжыр» терминдерінің мағынасы бірдей.

байланысқан бағытталмаған граф, ал а мен b оның әртүрлі төбелері болсын.

Анықтама. Ең қысқа (a, b) -маршруты a, b төбелерінің арақашықтығы деп аталады және

мен белгіленеді.

=0 (анықтама бойынша арақашықтық 0 ге тең болсын). Бұлай анықталған арақашықтық метриканың төмендегідей аксиомаларын қанағаттандырады.

- ≥0;

- = 0‹═›a=b;

- =( b, a) (симметриялық);

- < (үшбұрыш теңсіздігі)

Анықтама. Егер M={a₁, a₂, …, a_n} төбелер жиыны болса, онда элементтері P_ij =(р_ij) арақашықтықтар арқылы анықталатын р_ij = матрицасы арақашықтық матрицасы деп аталады. P^T=P , яғни Р- симетриялы матрица.

Анықтама. Тұрақты бір а төбесі үшін e(a)max{│bM} а төбесінің эксцентриситеті деп аталады. Яғни төбелердің эксцентриситеті осы төбемен одан ең алыс жатқан төбенің арақашықтығы.

Егер Р арақашықтық матрицасы болса онда e(a_i) эксцентриситеті і-ші жолда орналасқан сандардың ең үлкеніне тең. Төбелері эксцентриситеттерінің ішіндегі ең үлкені G графының диаметрі деп аталады және ол d(G) болып белгіленеді; d(G)=max{e(a)│aM}

Анықтама. Егер e(a)=d(G) болса а төбесі перийфериядағы төбе деп аталады Мысал :

Суреттегі G графының диаметрін табу керек.

Арақашықтық матрицасы

е(1) =3; е(2) =2; е(3) =3; е(4) =2; е(5) =2;

d(G)=3 1,3-перифериядағы төбелер болады.

Анықтама эксцентриситеттердің ең кішісі графтың радиусы деп аталады r(G) болып белгіленеді; r(G)min{e(a)│aM};

Анықтама Егер e(a)=r(G) а төбесі орталық төбе деп аталады.. Барлық орталық төбелердің жиыны графтың центрі деп аталады. Мысалы, жоғарыдағы графтың радиусы 2-ге тең r(G)=2, центрі {2, 4, 5} жиыны болады.

Орталық төбелерді табу есебі іс жүзінде көптеп кездеседі. Мысалы граф – төбелері елді мекендер, қабырғалары олардың арасындағы жолдарды білдіретін – жолдар желісін өрнектейтін болсын.Ауруханаларды, қызмет көрсету пунктерін т.б. тиімді орналастыру керек. Тиімділік дегенді бұл жерде қызмет көрсететін пункттен неғұрлым алыс орналасқан елді мекендердің ара қашықтығын неғұрлым азайту болып табылады. Демек, графтың орталық төбелері больница, қызмет көрсету пункттерін орналастыратын орындар болып табылады. Нақтылы есептерде бұларға қоса елді мекендердің ара қашықтығын, жолға кететін уақыт, жол бағасын т.б. ескеруге тура келеді. Бұл параметрлерді ескеру үшін салмақталған графтар қолданылады. Айталық G = әр (a, b) доғасының салмағы (a, b) нақты санына тең салмақтанған граф болсын.

жүктеу 19,56 Mb.

Достарыңызбен бөлісу: