Графтағы ең қысқа жолдар (арақашықтық). Айталық, G кез-келген граф, ал х, yV(G) оның екі төбесі болсын. х-тен у апаратын маршрутты Р0 деп, ал ұз. Р арқылы х пен у-ті қосатын кез келген маршруттың ұзындығын белгілейік. (ұз. Q арқылы Q маршрутының ұзындығы белгіленеді.).
Анықтама. Егер ұз. Р0≤ ұзындығы Р болса Р0 маршруты ең қысқа маршрут деп аталады.
Ең қысқа жолда төбелер мен доғалар (қабырғалар) қайталанбайды. Шынында да, егер Р0 маршрутында Р0:х=z, e1, z1,….,zp-1, ep, zp=у zi=zj бар болса, онда Р0 маршрутын zі-ден zj-ға дейінгі кесіндіні алып тастап қысқартуға болар еді, яғни Р0 -ді x = z0, e1,...,ei, zi, ej+1,...,zp-1, ep, zp=у маршрутымен алмастырар едік. Сондықтан да шын мәнінде ең қысқа маршрут қарапайым шынжыр болады. «Ең қысқа жол», «Ең қысқа маршрут», «Ең қысқа шынжыр» терминдерінің мағынасы бірдей.
Айталық, G= байланысқан бағытталмаған граф, ал а мен b оның әртүрлі төбелері болсын.
Анықтама. Ең қысқа (a, b) -маршруты a, b төбелерінің арақашықтығы деп аталады және  мен белгіленеді.
=0 (анықтама бойынша арақашықтық 0 ге тең болсын). Бұлай анықталған арақашықтық метриканың төмендегідей аксиомаларын қанағаттандырады.
- ≥0;
- = 0‹═›a=b;
- =
Достарыңызбен бөлісу: |
