Помощ DHS "Графики"

Скелетът на общата форма на графика. В случай на Graf изследване L = (XU Р) с обща форма не се изисква пълна информация за това, но знае които чифт това различните върхове са съседни и не прибягват до помощта на такава информация - скелета на графика L, които означават как. Брой се отнася до класа на прости графики с връх комплект за същата като тази в колоната на L, и нов набор от ребра. специфично както следва:

1) ако пространство L е линия, те се отстраняват;

2) ако пространство L е дъга, дъга произведени дезориентация;

3) ако пространство L е кратно на ребрата, те се заместват с един еквивалент ребро-връзка;

4) останалите ръбове образуват множество ребра.

По този начин, множество ребра включва ребра, множество от U получава след извършване на горните процедури 1, 2, 3.

Определяне на броя на «L» дължината на маршрутите на графиката

Път мл, J в графиката G = (X, U) е ограничен последователност на върхове и ръбове на формата -

където x0. XL - съответно започва и да завършва върхове маршрут m0, л.

Очевидно е, че само ограничен брой пътища могат да бъдат идентифицирани в краен графика G = (X, U). Trail разстояние миля, й е броят на ръбове, че тя включва.

Често трябва да знаете колко пътища на дадена дължина на G свързва с горната част на горния XI XJ.

За определяне на начини на дължина Q в графиката G = (X, U) неговата близост матрица R издигане на мощност, равна на р. След това, за всяка стойност на р = 1,2, ..., К стойност елемент (RI, й) Q R Q на матрицата определя броя на маршрути MI, дължината й равна на стойността на степен р.

Пример. За графика G = (X, U). показано на фигура 3, за определяне на броя на пътищата на дължина, равна на 2.

R графика близост матрица G има формата: