Boolesche Matrixmuliplikation und Transitive Hülle

Next: Der 4-Russen-Algorithmus für Boolesche Up: Transitive Hülle Previous: Min-Plus-Matrix-Produkt und Min-Plus-Transitive Hülle

Boolesche Matrixmuliplikation und Transitive Hülle

Ersetze in 4.6.1. Distanzmatrix durch (Boolesche) Adjazenzmatrix und ersetze Min-Plus durch $\vee, \wedge$ , d.h.:

$\begin{displaymath} C=A\cdot B; \quad c_{ij} = \bigvee_{k=1}^{n} a_{ik} \wedge b_{kj}\end{displaymath}$

Setze $a_{ii}=1, 1 \leq i \leq n$
Dann gilt für A^k (Boolesches Produkt, A⁰ = I)

$\begin{displaymath} a_{ij} = \left\{ \begin{array} {cl} 1 & \text{falls es im ... ...bestehend aus } \leq k \text{ Kanten gibt} \end{array} \right.\end{displaymath}$

Transitive Hülle

$\begin{displaymath} A^* := \bigvee\limits_{i\geq 0} A^i\end{displaymath}$

ist damit die Adjazenzmatrix der transitiven Hülle des zugrundeliegenden Graphen (= A^n-1).

$\fbox {\parbox[c]{12.45cm}{\textbf{Satz:} Sei M$(n)$\space die Zeitkomplexit\uml... ...}}}$, dann gilt: \\ \begin{center} T$(n) = \Theta($M$(n))$\space \end{center}}}$

Beweis:

Matrixmultiplikation $\prec$ transitive Hülle:
Gegeben: A,B; Gesucht: $C=A\cdot B$ (Boolesches Produkt); Setze:
$\begin{displaymath} L= \underbrace{ \begin{pmatrix} 0&A&0\\ 0&0&B\\ 0&0&0 ... ... \\ \end{array}\!\!\!\!\!\!\!\right\}\text{\footnotesize$3n$} \end{displaymath}$
L ist Adjazenzmatrix eines tripartiten, gerichteten Graphen, denn:

$\textstyle\parbox{20mm}{ \begin{math} \begin{array} {cccc} &\underline{u}&\u... ...u}&0&A&0\\ \underline{v}&0&0&B\\ \underline{w}&0&0&0 \end{array} \end{math}}$

$\begin{picture} (50,35) \multiput(5,5)(20,0){3}{\circle*{1}} \multiput(5,25)(2... ...9}} \put(5,22.5){\vector(4,-1){19}} \put(26,18){\vector(4,1){19}}\end{picture}$

Daher kann L^* leicht bestimmt werden:
$\begin{displaymath} L^*= \begin{pmatrix} I&A&AB\\ 0&I&B\\ 0&0&I \end{pmatrix} \end{displaymath}$
Also gilt: M $(n) \leq$ T $(3n) = \mathcal{O}($ T(n)).
Transitive Hülle $\prec$ Matrixmultiplikation
Gegeben: $L\ n\times n$ Boolesche Matrix; gesucht: L^*; Annahme: n ist Zweierpotenz. Teile auf:
$\begin{displaymath} \begin{split} L=& \begin{pmatrix} A&B\\ C&D \end{pmatri... ...e{\ }_{\frac{n}{2}}\underbrace{\ }_{\frac{n}{2}}} \end{split} \end{displaymath}$
Dann gilt:
$\begin{displaymath} \begin{array} {lll} E =& (A \vee BD^*C)^*&\text{betrachte a... ...\text{analog}\\ H =& D^*\vee GF &\text{analog} \end{array} \end{displaymath}$
Um L^* zu berechnen, benötigen wir zwei Transitive-Hülle-Berechnungen und sechs Matrixprodukte für Matrizen der Dimension $\frac{n}{2}\times\frac{n}{2}$ , plus Aufwand für $\vee$ , der $\leq c'n^2$ ist. Also:
$\begin{displaymath} \begin{array} {llll} \text{T}(n) & \leq 2 \text{T}(\frac{n}... ...{1}{4}(2c+6+4c')\text{M}(n)\\ &\leq c\text{M}(n) \end{array} \end{displaymath}$
falls $c \geq \frac{1}{4}(2c+6+4c')$ , also falls $c \geq 3 + 2c'$ .
Also T $(n) = \mathcal{O}($ M(n)).

$\Diamond$

Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999