Жұмыс бағдарламасы (силлабус) осы мамандықттардың Қр мжмбс 08. 329-2006, Қр мжмбс 08. 33-2006 Мемлекеттік стандартына сәйкес құрылған
жүктеу/скачать 21,8 Mb.
|
Графтағы ең қысқа жолдар (арақашықтық). Айталық, 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= Анықтама. Ең қысқа (a, b) -маршруты a, b төбелерінің арақашықтығы деп аталады және  мен белгіленеді.
=0 (анықтама бойынша арақашықтық 0 ге тең болсын). Бұлай анықталған арақашықтық метриканың төмендегідей аксиомаларын қанағаттандырады.
- ≥0;
- = 0‹═›a=b;
- =Каталог: uploads uploads -> Сәлім меңдібаев армысың, алтын таң! Журналист жазбалары Қостанай – 2013 ж uploads -> Тақырыбы: Ғарышты игеру (аудандық семинар) uploads -> Реферат kz Қазақша рефераттар сайты Талғат Амангелдіұлы Мұсабаев Қазақстанның ұлттық ғарыш агенттігінің төрағасы. Ғарышкер, техника ғылымдарының докторы uploads -> Ғарыш әлеміне саяхат uploads -> Сабақ тақырыбы: Шерхан Мұртаза «Ай мен Айша» романы Сабақ мақсаты: ҚР «Білім туралы» uploads -> Қазақ тілі мен латын тілі кафедрасы Қазақ Әдебиеті пәні бойынша әдістемелік өҢдеу мамандығы: Фельдшер Мейірбике ісі Стамотология Курс: І семестрі: ІІ uploads -> Ф 7 –007-02 Қазақстан Республикасы Білім және ғылым министрлігі uploads -> 2011 жылдың 14 мамырында «Жалпы гигиена және экология», «Эпидемиология» кафедрасының ұйымдастыруымен және «Студенттік басқару ұйымының» ұйымдастыруымен Д. Е uploads -> Сабақтың тақырыбы Бала Мәншүк ( Мәриям Хакімжанова) Сілтеме uploads -> Ана тілі №2. Тақырыбы: Кел, балалар, оқылық Мақсаты жүктеу/скачать 21,8 Mb. Достарыңызбен бөлісу:
|