Matematické Fórum

Berny · 19. 06. 2011 14:13 — Editoval Berny (19. 06. 2011 14:35)

Ahoj, potřeboval bych trochu poradit pokud by někdo mohl.
Mam zadany takovydle graf , najdete matici sousednosti:

Uploaded with ImageShack.us

A pokud jsem rozumnel vsemu spravne, tak si musim sestrojit matici sousednosti:

$\begin{array}[t]{ccccccc} 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 &1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 \end{array}$

A samotny postu probiha, ze budu nasobit matice az do N-1, tedy pokud mam matici 7x7, pak az do 6.
Takze A0, matice jednotkova
A1 - matice sousednosti

takze:
A1*A1 = A2
A2*A1 = A3
A3*A1 = A4
A4*A1 = A5
A5*A1 = A6 hotovo.

A pak budu dosazovat do nasi matice Vzdalenosti - D, vzdy mocninu matice, kde jsem nasel na prislusnem radku a sloupci 1.

Pochopil jsem to tak, ze na hlavni diagonale tedy budou vzdy 0 - podle matice jednotkove.

Dal jsem se tedy do pocitani, A2 mi vyslo takto:

$\begin{array}[t]{ccccccc} 2 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 4 & 4 & 1 & 1 & 1 & 1\\ 1 & 1 & 4 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 2 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 2 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 2 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 2 \end{array}$

Neni, nejaky jednodusi zpusob nez pocitat vsechny matice az do A6? Jestli nemohu pocitat jen prvky matice kde je 0, aby jsem nasel cestu?

Děkuji velice.

petrkovar · 20. 06. 2011 14:11

↑ Berny:Opakovaným násobením matice sousednosti nedostaneme matici vzáleností mezi dvojicemi vrcholů, ale matici, ve které bude element vyjadřovat počet sledů délky k (k je mocnina matice) mezi příslušnou dvojicí vrcholů. Pro určování vzdáleností je možno použít Floydův algoritmus nebo použít Dijsktrův algoritmus opakovaně pro různé výchozí vrcholy.

Berny · 20. 06. 2011 19:18

Ahoj, dekuju. Nekolik matic jsem si napocital, takovym zvlastnim systemem ktery vychazi, ale dekuji moc :)

Matematické Fórum

#1 19. 06. 2011 14:13 — Editoval Berny (19. 06. 2011 14:35)

Matice vzdalenosti z grafu

#2 20. 06. 2011 14:11

Re: Matice vzdalenosti z grafu

#3 20. 06. 2011 19:18

Re: Matice vzdalenosti z grafu

Zápatí