\documentclass{slides}
\usepackage{amsmath,amssymb}
\hoffset-1cm
\begin{document}
\slide
\begin{center}
Boolesche Matrixmultiplikation\\ und Transitive H\"ulle
\end{center}
$G = (V,E)$ endlicher gerichteter Graph\\
Knoten: $V = \{1,2,\ldots,n\}$,
Kanten: $E \subseteq V \times V$\\
Adjazenzmatrix (Matrix der Relation $E$)
\[
A = [ a_{i,j}]_{1 \leq i,j \leq n}~~\text{mit}~~
a_{i,j} =
\begin{cases}
1 & \text{falls }i \rightarrow j \in E \cr
0 & \text{falls }i \rightarrow j \not \in E
\end{cases}
\]

Boolesche Matrixmultiplikation:
\begin{align*}
A = [a_{i,j}], &B = [b_{i,j}], A \cdot B = [c_{i,j}]~~\text{mit}\cr
&c_{i,j} = \bigvee_{k=1}^n a_{i,k} \wedge b_{k,j}
\end{align*}

Interpretation der Matrixpotenzen $A^k = [a_{i,j}^{(k)}]$
\[
a_{i,j}^{(k)} = 1 ~~\Leftrightarrow ~~
\left\{
\begin{minipage}{7cm}
es gibt in $G$ einen Pfad der L\"ange $k$ von $i$ nach $j$
\end{minipage}
\right.
\]

\slide

$A^* = [a_{i,j}^{(*)}]$: 
Matrix der transitiven H\"ulle der Relation $E$
\[
a_{i,j}^{(*)} = 1 ~~\Leftrightarrow ~~
\left\{
\begin{minipage}{7cm}
es gibt in $G$ einen Pfad von $i$ nach $j$
\end{minipage}
\right.
\]

Generell 
\[
A^* = A^0 \vee A^1 \vee A^2 \vee \ldots  = 
\bigvee_{k=0}^{\infty} A^k
\]

Wegen $\sharp A = n$ gilt sogar
\[
A^* = A^0 \vee A^1 \vee A^2 \vee \ldots  \vee A^{n-1}= 
\bigvee_{k=0}^{n-1} A^k = (I \vee A)^{n-1}
\]

und damit auch
\[
A^* = A^0 \vee A^1 \vee A^2 \vee \ldots  \vee A^{m}= 
\bigvee_{k=0}^{m} A^k = (I \vee A)^{m}
\]
f\"ur alle $m \geq n-1$.


\slide

Berechnung  der transitiven H\"ulle $A^*$ \\
durch interiertes
Quadrieren:
\[
(I \vee A) \rightarrow
(I \vee A)^2 \rightarrow
(I \vee A)^4 \rightarrow
\ldots \rightarrow
(I \vee A)^{2^p}
\]
mit $p = \lceil \log_2 (n-1) \rceil$ zeigt:\\
Berechnung der transitiven H\"ulle \"uber $\Omega = \{\vee, \wedge\}$
hat
\begin{align*}
\text{Gr\"osse} ~~:~~ & M_{matrix}^{(B)}(n,k) \lceil \log_2 n \rceil \cr
\text{Tiefe} ~~:~~ & k \cdot \log_2 n \cdot \lceil \log_2 n \rceil
\end{align*}

\slide

Reduktion von Boolescher Matrixmultiplikation auf Berechnung der
transitiven H\"ulle
\[
\begin{bmatrix}
0 & A & 0\cr
0 & 0 & B\cr
0 & 0 & 0
\end{bmatrix}^*
=
\begin{bmatrix}
I & A & A \cdot B\cr
0 & I & B\cr
0 & 0 & I
\end{bmatrix}
\]
 
\bigskip

Reduktion der Berechnung der
transitiven H\"ulle auf Boolesche Matrixmultiplikation (rekursiv)
\[
A =
\begin{bmatrix}
U & V \cr
W & X
\end{bmatrix}~~~(\text{Format}~n \times n)
\]
wobei $U,V,W,X$ mit Format $n/2 \times n/2$.\\
Dann ist
\[
A^* =
\begin{bmatrix}
Y^* & Y^* \cdot V \cdot X^* \cr
X^* \cdot W \cdot Y^* & X^* + X^*\cdot W \cdot Y^* \cdot V \cdot X^*
\end{bmatrix}
\]
wobei $Y = U + V \cdot X^* \cdot W$

zeigt: Schaltkreisgr\"osse f\"ur transitive H\"ulle ist
proportional zu $M_{matrix}^{(B)}(n,k)$ - aber dabei ist die Tiefe
nicht mehr logarithmisch!
\end{document}