Автор Тема: Составить матрицы инцидентности, достижимости и сильной связности  (Прочитано 1082 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Александр

  • Пользователь
  • Сообщений: 10
    • Просмотр профиля
Нарисовать граф. Составить матрицы инцидентности,Достижимости и сильной связности орграфа если его матрица смежности
 

Оффлайн phobos

  • Модератор
  • Сообщений: 95
  • Поблагодарили: 85 раз(а)
    • Просмотр профиля
Нарисуем ориентированный граф \(  \large G  \), заданный данной матрицей смежности \(  \large A\left(G\right)  \).

По определению матрицей инцидентности ориентированного графа \(  \large G  \) называется матрица \(  \large B\left(G\right)  \) размера \(  \large n\times m  \) (\(  \large n  \) --- число вершин, \(  \large m  \) --- число дуг) с элементами:

\(  \large b_{ij}=-1  \),если \(  \large j  \)-я дуга начинается в \(  \large i  \)-й вершине;
\(  \large b_{ij}=1  \),если \(  \large j  \)-я дуга заканчивается в \(  \large i  \)-й вершине;
\(  \large b_{ij}=0  \), если иначе.

Так как число вершин графа \(  \large 5  \), а число дуг \(  \large 9  \), то матрица будет размерности \(  \large 5\times 9  \).

\(  \large B(G)=\begin{pmatrix}
 {} & {x1} & {x2} & {x3} & {x4} & {x5} & {x6} & {x7} & {x8} & {x9} \\
 {1} & {-1} & {-1} & {1} & {0} & {0} & {1} & {0} & {0} & {0} \\
 {2} & {1} & {0} & {-1} & {-1} & {1} & {0} & {0} & {1} & {0} \\
 {3} & {0} & {0} & {0} & {0} & {-1} & {0} & {1} & {0} & {0} \\
 {4} & {0} & {1} & {0} & {0} & {0} & {-1} & {-1} & {0} & {1} \\
 {5} & {0} & {0} & {0} & {1} & {0} & {0} & {0} & {-1} & {-1}
\end{pmatrix}  \)

Построим матрицу достижимости данного орграфа \(  \large G  \). По определению, матрица достижимости --- это квадратная матрица \(  \large S\left(G\right)  \) размера \(  \large n\times n  \) (\(  \large n  \) --- число вершин) с элементами:

\(  \large s_{ij}=1  \), если вершина \(  \large j   \) достижима из вершины \(  \large i  \);
\(  \large s_{ij}=0  \), если иначе.

Поскольку орграф \(  \large G  \) состоит из \(  \large 5  \) вершин, то матрица \(  \large S\left(G\right)  \) имеет размер \(  \large 5\times 5  \).

\(  \large S(G)=\begin{pmatrix}
 {1} & {1} & {1} & {1} & {1} \\
 {1} & {1} & {1} & {1} & {1} \\
 {1} & {1} & {1} & {1} & {1} \\
 {1} & {1} & {1} & {1} & {1} \\
 {1} & {1} & {1} & {1} & {1}
\end{pmatrix}  \)

Матрица сильной связности \(  \large D\left(G\right)  \) состоит из элементов \(  \large d_{ij}=\left(\left(c_{ij}\right)\wedge \left(c_{ji}\right)\right)  \). Поскольку в матрице достижимости \(  \large S\left(G\right)  \) все элементы \(  \large s_{ij}=1  \), то все элементы \(  \large d_{ij}  \) матрицы \(  \large D\left(G\right)  \) также равны \(  \large 1  \), то есть данный граф \(  \large G  \) является сильно связным.

Определим для каждой вершины орграфа полустепени исхода/захода вершин. Полустепень исхода \(  \large d^-\left(i\right)  \) вершины --- это число дуг, исходящих из этой вершины, а полустепень захода \(  \large d^+\left(i\right)  \) вершины --- это число дуг, заходящих в эту вершину.

\( \begin{array}{|c|c|}
\hline
 & 1 & 2 & 3 & 4 & 5 \\
\hline
 d^-\left(i\right) & 2 & 2 & 1 & 2 & 2 \\
\hline
 d^+\left(i\right) & 2 & 3 & 1 & 2 & 1 \\
\hline
\end{array} \)
 
Сказали спасибо: Admin