Matematyka Dyskretna - Rekurencja / Kongurencja

[abc666]

\(\displaystyle{ spec(\alpha )=\{ \lfloor \alpha \rfloor, \lfloor 2\alpha \rfloor, \lfloor 3\alpha \rfloor, ... \}}\)
tutaj
\(\displaystyle{ spec_n(\alpha )=\lfloor n\alpha \rfloor}\)

[BlackDante]

a mam takie pytanko: bo te algorytmy to mniej więcej proste są no ale: Jak się zabrać za rysowanie dowolnego grafu na podstawie: (a) {1,1,2,2,4,4,4,4}? I jak powstaje macierz Incydencji? bo na wikipedii tego przykładu jakoś nie pojmuje.

[abc666]

Wiesz już, że to jest ciąg wierzchołków to zmodyfikujmy go tak (po uporządkowaniu).

\(\displaystyle{ \{\{A, 4\}, \{B, 4\}, \{C, 4\}, \{D, 4\}, \{E, 2\}, \{F, 2\}, \{G, 1\}, \{H, 1\}\}}\)

No i postępujesz wg algorytm. Zerujemy \(\displaystyle{ A}\) i odejmujemy od 4 następnych.

\(\displaystyle{ \{\{A, 0\}, \{B, 3\}, \{C, 3\}, \{D, 3\}, \{E, 1\}, \{F, 2\}, \{G, 1\}, \{H, 1\}\}}\)

I łączysz wierzchołek \(\displaystyle{ A}\) z tymi, od których odjąłeś. Czyli po pierwszym kroku wygląda to tak.

\(\displaystyle{ \psset{unit=1pt,arrowlength=2,arrowsize=3pt 3,arrowinset=.1}
\fcolorbox{white}{white}{%
\begin{pspicture}*(230, 200)
\psline(75, 175)(165, 175)
\psline(75, 175)(215, 135)
\psline(75, 175)(225, 65)
\psline(75, 175)(175, 15)
\pscircle[fillstyle=solid,fillcolor=white](83, 14){4} \put(83, 20){$F$}
\pscircle[fillstyle=solid,fillcolor=white](175, 15){4} \put(175, 20){$E$}
\pscircle[fillstyle=solid,fillcolor=white](25, 65){4} \put(30, 65){$G$}
\pscircle[fillstyle=solid,fillcolor=white](225, 65){4} \put(215, 70){$D$}
\pscircle[fillstyle=solid,fillcolor=white](25, 135){4} \put(30, 135){$H$}
\pscircle[fillstyle=solid,fillcolor=white](215, 135){4} \put(220, 135){$C$}
\pscircle[fillstyle=solid,fillcolor=white](75, 175){4} \put(80,178){$A$}
\pscircle[fillstyle=solid,fillcolor=white](165, 175){4} \put(170, 175){$B$}
\end{pspicture}
}%}\)

Teraz dalej wg algorytm sortujemy.
\(\displaystyle{ \{\{B, 3\}, \{C, 3\}, \{D, 3\}, \{F, 2\}, \{E, 1\}, \{G, 1\}, \{H, 1\}, \{A, 0\}\}}\)
i znowu odejmujemy i łaczymy
\(\displaystyle{ \{\{B, 0\}, \{C, 2\}, \{D, 2\}, \{F, 1\}, \{E, 1\}, \{G, 1\}, \{H, 1\}, \{A, 0\}\}}\)

\(\displaystyle{ \psset{unit=1pt,arrowlength=2,arrowsize=3pt 3,arrowinset=.1}
\fcolorbox{white}{white}{%
\begin{pspicture}*(230, 200)
\psline(75, 175)(165, 175)
\psline(75, 175)(215, 135)
\psline(75, 175)(225, 65)
\psline(75, 175)(175, 15)
\psline(165, 175)(215, 135)
\psline(165, 175)(225, 65)
\psline(165, 175)(83, 14)
\pscircle[fillstyle=solid,fillcolor=white](83, 14){4} \put(83, 20){$F$}
\pscircle[fillstyle=solid,fillcolor=white](175, 15){4} \put(175, 20){$E$}
\pscircle[fillstyle=solid,fillcolor=white](25, 65){4} \put(30, 65){$G$}
\pscircle[fillstyle=solid,fillcolor=white](225, 65){4} \put(215, 70){$D$}
\pscircle[fillstyle=solid,fillcolor=white](25, 135){4} \put(30, 135){$H$}
\pscircle[fillstyle=solid,fillcolor=white](215, 135){4} \put(220, 135){$C$}
\pscircle[fillstyle=solid,fillcolor=white](75, 175){4} \put(80,178){$A$}
\pscircle[fillstyle=solid,fillcolor=white](165, 175){4} \put(170, 175){$B$}
\end{pspicture}
}%}\)

I tak dalej. No i tutaj powinniśmy otrzymać
\(\displaystyle{ \psset{unit=1pt,arrowlength=2,arrowsize=3pt 3,arrowinset=.1}
\fcolorbox{white}{white}{%
\begin{pspicture}*(230, 200)
\psline(75, 175)(165, 175)
\psline(75, 175)(215, 135)
\psline(75, 175)(225, 65)
\psline(75, 175)(175, 15)
\psline(165, 175)(215, 135)
\psline(165, 175)(225, 65)
\psline(165, 175)(83, 14)
\psline(215, 135)(225, 65)
\psline(215, 135)(83, 14)
\psline(225, 65)(175, 15)
\psline(25, 65)(25, 135)
\pscircle[fillstyle=solid,fillcolor=white](83, 14){4} \put(83, 20){$F$}
\pscircle[fillstyle=solid,fillcolor=white](175, 15){4} \put(175, 20){$E$}
\pscircle[fillstyle=solid,fillcolor=white](25, 65){4} \put(30, 65){$G$}
\pscircle[fillstyle=solid,fillcolor=white](225, 65){4} \put(215, 70){$D$}
\pscircle[fillstyle=solid,fillcolor=white](25, 135){4} \put(30, 135){$H$}
\pscircle[fillstyle=solid,fillcolor=white](215, 135){4} \put(220, 135){$C$}
\pscircle[fillstyle=solid,fillcolor=white](75, 175){4} \put(80,178){$A$}
\pscircle[fillstyle=solid,fillcolor=white](165, 175){4} \put(170, 175){$B$}
\end{pspicture}
}%}\)

I jak łatwo sprawdzić wyszło nam tak jak trzeba. Graf nie jest spójny, ale nikt nie powiedział, że musi być.

No i jak teraz tu wyznaczyć macierz incydencji. Ponieważ mamy tutaj 8 wierzchołków i 11 krawędzi (suma stopni na dwa) to nasza macierz, będzie miała 11 kolumn i 8 wierszy. No i kolejne wiersze odpowiadają kolejnym wierzchołkom, a kolumny kolejnym krawędziom. Dobrze by było sobie oznaczyć jakoś te krawędzie np. \(\displaystyle{ e_1, e_2,...}\). No i teraz niech krawędź od \(\displaystyle{ A}\) do \(\displaystyle{ B}\) będzie tą pierwszą. Wtedy w macierzy incydencji w pierwszej kolumnie musisz wpisać jedynki dla \(\displaystyle{ A}\) i \(\displaystyle{ B}\) (czerwone). Teraz niech druga krawędź to będzie miedzy \(\displaystyle{ A}\) i \(\displaystyle{ C}\). Analogicznie drugą kolumnę robisz (niebieskie).
\(\displaystyle{ \left[\begin{array}{ccccccccccc}{\color{red}1}&{\color{blue}1}&-&-&-&-&-&-&-&-&-\\
{\color{red}1}&0&-&-&-&-&-&-&-&-&-\\
0&{\color{blue}1}&-&-&-&-&-&-&-&-&-\\
0&0&-&-&-&-&-&-&-&-&-\\
0&0&-&-&-&-&-&-&-&-&-\\
0&0&-&-&-&-&-&-&-&-&-\\
0&0&-&-&-&-&-&-&-&-&-\\
0&0&-&-&-&-&-&-&-&-&-\\
\end{array}\right]}\)

I tak musisz wypełnić całą tą macierz. Zauważ, że w każdej kolumnie są dwie jedynki.

[BlackDante]

dziękuję pięknie i przy okazji gratuluje znajomości matematyki jak i systemu LaTeX-a jak patrze na kody tych obrazków to oczopląsu dostaje