Қазақстан республикасының білім және ғылым министірлігі

жүктеу 21,8 Mb. бет 104/214 Дата 09.01.2018 өлшемі 21,8 Mb. #7265 түрі Мазмұндама

( b, a) (симметриялық); - < (үшбұрыш теңсіздігі) Анықтама. Егер M={a1, a2, …, an} төбелер жиыны болса, онда элементтері Pij =(рij) арақашықтықтар арқылы анықталатын рij= матрицасы арақашықтық матрицасы деп аталады. PT=P, яғни Р-симетриялы матрица. Анықтама. Тұрақты бір а төбесі үшін e(a)max{│bM} а төбесінің эксцентриситеті деп аталады. Яғни төбелердің эксцентриситеті осы төбемен одан ең алыс жатқан төбенің арақашықтығы. Егер Р арақашықтық матрицасы болса онда e(ai) эксцентриситеті і-ші жолда орналасқан сандардың ең үлкеніне тең. Төбелері эксцентриситеттерінің ішіндегі ең үлкені G графының диаметрі деп аталады және ол d(G) болып белгіленеді; d(G)=max{e(a)│aM} Анықтама. Егер e(a)=d(G) болса а төбесі перийфериядағы төбе деп аталады Мысал : Суреттегі G графының диаметрін табу керек. Анықтама. Эксцентриситеттердің ең кішісі графтың радиусы деп аталады r(G) болып белгіленеді; r (G)min{e (a)│aM}; Анықтама. Егер e(a)=r(G) а төбесі орталық төбе деп аталады. Барлық орталық төбелердің жиыны графтың центрі деп аталады. Мысалы, жоғарыдағы графтың радиусы 2-ге тең r(G)=2, центрі {2, 4, 5} жиыны болады. Орталық төбелерді табу есебі іс жүзінде көптеп кездеседі. Мысалы граф – төбелері елді мекендер, қабырғалары олардың арасындағы жолдарды білдіретін – жолдар желісін өрнектейтін болсын.Ауруханаларды, қызмет көрсету пунктерін т.б. тиімді орналастыру керек. Тиімділік дегенді бұл жерде қызмет көрсететін пункттен неғұрлым алыс орналасқан елді мекендердің ара қашықтығын неғұрлым азайту болып табылады. Демек, графтың орталық төбелері больница, қызмет көрсету пункттерін орналастыратын орындар болып табылады. Нақтылы есептерде бұларға қоса елді мекендердің ара қашықтығын, жолға кететін уақыт, жол бағасын т.б. ескеруге тура келеді. Бұл параметрлерді ескеру үшін салмақталған графтар қолданылады. Айталық G= әр (a, b) доғасының салмағы(a, b) нақты санына тең салмақтанған граф болсын. жүктеу 21,8 Mb. Достарыңызбен бөлісу:

©g.engime.org 2024
әкімшілігінің қараңыз