Совет 1: Как из матрицы построить граф

В информатике графом называют геометрическое представление множества точек (вершин) и линий (ребер), связывающих все или часть из данных точек. Наличие или отсутствие связи (ребра) в графе, а также направленность соединения (ее ориентированность, вырождение в петлю) описывается в специальных матрицах графов – инцинденций и смежности. По любой из данных матриц можно построить граф, используя соответствующие определения.
Инструкция
1
Графы бывают ориентированными и неориентированными. В первом случае ребра, соединяющие вершины графа, задают направление движения стрелкой на одном из своих концов. Если ребро начинается и заканчивается в одной и той же вершине, оно вырождается в петлю. Все данные условия графа явно задаются в матрице инцинденций. Матрица смежностей содержит лишь информацию о наличии связи между вершинами графа, не раскрывая ее особенностей.
2
Постройте граф по матрице инцинденций. Для этого посчитайте количество строк n и столбцов m в заданной матрице. Строки соответствуют вершинам графа, а столбцы – ребрам. На свободном пространстве листа отметьте вершины строящегося графа кружками, их будет столько, сколько строк содержит матрица инцинденций. Пронумеруйте вершины от 1 до n.
3
Разбор матрицы лучше осуществлять по столбцам, определяя таким образом наличие связи между вершинами и ее направление. Просматривая первый столбец сверху вниз, ищите значение отличное от нуля. При нахождении числа -1 или 1 запомните, в какой строке оно расположено, и ищите вторую единицу в том же столбце. Обнаружив оба числа, проведите на графе линию, соединяющую две вершины с номерами отмеченных строк. Если одно из найденных значений было -1, значит, граф является ориентированным – укажите на линии направляющую стрелку к той вершине, где в матрице находится -1. Если оба значения описаны единицами, следовательно, строящийся граф неориентированный и его ребра не имеют направления. Если в столбце обнаружено число 2, проведите петлю в вершине, соответствующей позиционной строке матрицы. Нулевые значения указывают на отсутствие связи. Рассмотрите аналогичным образом остальные столбцы и отобразите на рисунке все заданные ребра графа.
4
Постройте граф по матрице смежности. Данная матрица является квадратной, т.к. число ее строк равно числу столбцов и соответствует количеству вершин в графе. На листе нарисуйте кружки-вершины по числу срок матрицы. Разбор матрицы смежности лучше проводить, двигаясь по строке. Начиная с первой строки слева направо, ищите значения отличные от нуля. Найдя 1 (или другое ненулевое число) заметьте его текущую позицию в строке и столбце. На графе проведите линию между вершинами, соответствующими замеченными строке и столбцу. Т.е. если 1 стоит на пересечении 2 строки и 3 столбца матрицы смежности, ребро графа соединит 2 и 3 его вершины. Продолжите поиск ненулевых значений до конца матрицы смежности и заполните граф аналогичным образом.

Совет 2: Как найти матрицу перехода

Матрицы перехода возникают при рассмотрении марковских цепей, которые являются частным случаем марковских процессов. Определяющее их свойство состоит в том, что состояние процесса в «будущем», зависит от текущего состояния (в настоящем) и, при этом, не связано с «прошлым».
Инструкция
1
Необходимо рассмотреть случайный процесс (СП) X(t). Его вероятностное описание основывается на рассмотрении n-мерной плотности вероятности его сечений W(x1, x2,…,xn; t1, t2,…,tn), которую, на основе аппарата условных плотностей вероятности, можно переписать в виде W(x1, x2,…,xn; t1, t2,…,tn)= W(x1, x2,…,x(n-1); t1, t2,…,t(n-1))∙W(xn, tn|x1, t1, x2,t2, …,x(n-1), t(n-1)), cчитая, что t1< t2
2
Определение. СП, для которого при любых последовательных моментов времени t1< t2
3
Используя аппарат все тех же условных плотностей вероятностей, можно прийти к выводу, чтоW(x1, x2,…,x(n-1), xn,tn; t1, t2,…,t(n-1),tn)=W(x1, tn)∙W(x2, t2|x1, t1)…∙W( xn,tn|x(n-1), t(n-1)). Таким образом, все состояния марковского процесса полностью определяются его начальным состоянием и плотностями вероятностей переходов W(xn, tn|X(t(n-1))=x(n-1))). Для дискретных последовательностей (дискретны возможные состояния и время), где вместо плотностей вероятностей переходов присутствуют их вероятности и матрицы переходов, процесс носит название - цепь Маркова.
4
Рассмотрите однородную цепь Маркова (нет зависимости от времени). Матрицы перехода составляются из условных вероятностей перехода p(ij) (см. рис.1). Это вероятность того, что за один шаг система, имевшая состояние равное хi, перейдет в состояние xj. Вероятности переходов определяет постановка задачи и ее физические смысл. Подставляя их в матрицу получают ответ для данной задачи.
5
Типовые примеры построения матриц перехода дают задачи о блуждающих частицах. Пример. Пусть система имеет пять состояний x1, x2, x3, x4, x5. Первое и пятое являются граничными. Пусть на каждом шаге система может перейти только в соседнее по номеру состояние, причем при движении в сторону х5 с вероятность p, a в сторону х1 с вероятность q (p+q=1). При достижении границ система может перейти в х3 с вероятность v или остаться в прежнем состоянии с вероятностью1-v. Решение . Для того чтобы задача стала совершенно прозрачной постройте граф состояний (см. рис. 2).
Видео по теме
Поиск
Совет полезен?
Добавить комментарий к статье
Осталось символов: 500
к
Honor 6X Premium
новая премиальная версия
узнать больше