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

Ең қысқа жолда төбелер мен доғалар (қабырғалар) қайталанбайды. Шынында да, егер Р₀ маршрутында Р₀:х=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=у маршрутымен алмастырар едік. Сондықтан да шын мәнінде ең қысқа маршрут қарапайым шынжыр болады. «Ең қысқа жол», «Ең қысқа маршрут», «Ең қысқа шынжыр» терминдерінің мағынасы бірдей.

Айталық, G= байланысқан бағытталмаған граф, ал а мен 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{ │b M} а төбесінің эксцентриситеті деп аталады. Яғни төбелердің эксцентриситеті осы төбемен одан ең алыс жатқан төбенің арақашықтығы.

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

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

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