Je ziet hier een graaf met de punten $A$, $B$ en $C$. Er zijn tussen de punten verschillende wegen. Sommige van die wegen zijn éénrichtingsverkeer. ![]() Je kunt bij deze graaf een directe-wegen-matrix opstellen. Hierin kan je dan aangeven hoeveel directe verbindingen er zijn tussen de verschillende punten. Dat ziet er dan zo uit: $\begin{array}{*{20}c}M&{\begin{array}{*{20}c}{van}\\{\begin{array}{*{20}c}A&B&C\\\end{array}}\\\end{array}}\\{\begin{array}{*{20}c}{naar}&{\begin{array}{*{20}c}A\\B\\C\\\end{array}}\\\end{array}}&{\left({\begin{array}{*{20}c}1&2&1\\2&0&2\\3&4&0\\\end{array}}\right)}\\\end{array}$ Er zijn (bijvoorbeeld) 4 directe wegen van $B$ naar $C$, maar er zijn 2 directe wegen van $C$ naar $B$. M in het kwadraat Je kunt $M$ met zichzelf vermenigvuldigen: $M^2=\left({\begin{array}{*{20}c}1&2&1\\2&0&2\\3&4&0\\\end{array}}\right)\times\left({\begin{array}{*{20}c}1&2&1\\2&0&2\\3&4&0\\\end{array}}\right)=\left({\begin{array}{*{20}c}8&6&5\\8&{12}&2\\{11}&6&{11}\\\end{array}}\right)$ Dat geeft: $\begin{array}{*{20}c}{M^2}&{\begin{array}{*{20}c}{van}\\{\begin{array}{*{20}c}A&B&C\\\end{array}}\\\end{array}}\\{\begin{array}{*{20}c}{naar}&{\begin{array}{*{20}c}A\\B\\C\\\end{array}}\\\end{array}}&{\left({\begin{array}{*{20}c}8&6&5\\8&{12}&2\\{11}&6&{11}\\\end{array}}\right)}\\\end{array}$ De getallen in $M^2$ geven het aantal tweestapswegen. Hoe kan je dat controleren? Volgens matrix $M^2$ zijn er $8$ tweestapswegen van $A$ naar $A$. Dit getal komt van deze vermenigvuldiging (rij×kolom): $1·1 + 2·2 + 1·3 = 1 + 4 + 3 = 8$ Wat reken je dan precies uit?
In totaal kan je dus op 1+4+3=8 manieren van $A$ naar $A$ in twee stappen.
|