Насочена претеглена графика - теория, теория на графиката, случайна разходка

Имам свързана насочена претеглена графика. Тежестта на ръба представлява вероятност за придвижване между върхове; тежести за всички краища, излъчвани от върхова сума до една. Графиката съдържа две мивки: A и B. За всеки върх в графиката искам да знам вероятността една разходка, произхождаща от там, да достигне A и еднаква за B. Какъв проблем е това? Как да го реша?

Отговори:

Този проблем е от алгебра. За път, започващ с върха, вероятността за достигане на A е средната стойност на вероятностите за достигане на A от всеки от съседните му върхове, претеглена от крайните тегла. Нека поставим това по-конкретно.

Позволявам P бъде матрицата на съседство за графиката. Това е, P_{И, Й} е вероятността за преминаване от върха аз до върха к, Комплект P_{А, А} = 1. Ако вземем вектор на вероятностите, присвоен на всеки връх и го умножим по P, тогава полученият вектор съдържа средно претеглена стойност на съседите на всяка върха. Това, което търсим, е вектор V, така че P v = v и V_А = 1.

Този вектор V е собственият вектор на P съответстващи на собствената стойност на 1. Да P винаги имаш такова собствено значение? За щастие Теорема на Перон-Фробениус ни казва, че го прави и че това е най-голямото собствено значение на P, След това решението е да се формира матрицата на съседство P и намерете собствения вектор, съответстващ на най-голямата му собствена стойност.

Има и приблизително решение. Ако вземем вектор х на вершинните вероятности, с х_А = 1, а останалите елементи са 0 P^к х ще се сближат до V като к отива в безкрайността. P^к може да е по-лесно да се изчисли за малки стойности на к отколкото собствения вектор.

пример

Нека разгледаме следната проста графика:

Ако нареждаме върховете по азбучен ред, тогава матрицата P съответстващата на графиката е:

Тази матрица има собствена стойност, равна на 1, и съответният собствен вектор е: [1 0 70/79 49/79]. Тоест, точната вероятност да се стигне А от ° С е 70/79, и от д тя е 49/79. Ако изработите отговора за B, излиза на 9/79 и 30/79, което е точно това, което очакваме.

Стойността на P¹⁶ [1 0 0 0] е приблизително [1 0 0.886 0.62] и е правилен за 6 десетични знака.