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

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

- =

жүктеу 21,8 Mb.

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