\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\mathllap }[2][]{{#1#2}}\)
\(\newcommand {\mathrlap }[2][]{{#1#2}}\)
\(\newcommand {\mathclap }[2][]{{#1#2}}\)
\(\newcommand {\mathmbox }[1]{#1}\)
\(\newcommand {\clap }[1]{#1}\)
\(\newcommand {\LWRmathmakebox }[2][]{#2}\)
\(\newcommand {\mathmakebox }[1][]{\LWRmathmakebox }\)
\(\newcommand {\cramped }[2][]{{#1#2}}\)
\(\newcommand {\crampedllap }[2][]{{#1#2}}\)
\(\newcommand {\crampedrlap }[2][]{{#1#2}}\)
\(\newcommand {\crampedclap }[2][]{{#1#2}}\)
\(\newenvironment {crampedsubarray}[1]{}{}\)
\(\newcommand {\crampedsubstack }{}\)
\(\newcommand {\smashoperator }[2][]{#2\limits }\)
\(\newcommand {\adjustlimits }{}\)
\(\newcommand {\SwapAboveDisplaySkip }{}\)
\(\require {extpfeil}\)
\(\Newextarrow \xleftrightarrow {10,10}{0x2194}\)
\(\Newextarrow \xLeftarrow {10,10}{0x21d0}\)
\(\Newextarrow \xhookleftarrow {10,10}{0x21a9}\)
\(\Newextarrow \xmapsto {10,10}{0x21a6}\)
\(\Newextarrow \xRightarrow {10,10}{0x21d2}\)
\(\Newextarrow \xLeftrightarrow {10,10}{0x21d4}\)
\(\Newextarrow \xhookrightarrow {10,10}{0x21aa}\)
\(\Newextarrow \xrightharpoondown {10,10}{0x21c1}\)
\(\Newextarrow \xleftharpoondown {10,10}{0x21bd}\)
\(\Newextarrow \xrightleftharpoons {10,10}{0x21cc}\)
\(\Newextarrow \xrightharpoonup {10,10}{0x21c0}\)
\(\Newextarrow \xleftharpoonup {10,10}{0x21bc}\)
\(\Newextarrow \xleftrightharpoons {10,10}{0x21cb}\)
\(\newcommand {\LWRdounderbracket }[3]{\underset {#3}{\underline {#1}}}\)
\(\newcommand {\LWRunderbracket }[2][]{\LWRdounderbracket {#2}}\)
\(\newcommand {\underbracket }[1][]{\LWRunderbracket }\)
\(\newcommand {\LWRdooverbracket }[3]{\overset {#3}{\overline {#1}}}\)
\(\newcommand {\LWRoverbracket }[2][]{\LWRdooverbracket {#2}}\)
\(\newcommand {\overbracket }[1][]{\LWRoverbracket }\)
\(\newcommand {\LATEXunderbrace }[1]{\underbrace {#1}}\)
\(\newcommand {\LATEXoverbrace }[1]{\overbrace {#1}}\)
\(\newenvironment {matrix*}[1][]{\begin {matrix}}{\end {matrix}}\)
\(\newenvironment {pmatrix*}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bmatrix*}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bmatrix*}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vmatrix*}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vmatrix*}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newenvironment {smallmatrix*}[1][]{\begin {matrix}}{\end {matrix}}\)
\(\newenvironment {psmallmatrix*}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bsmallmatrix*}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bsmallmatrix*}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vsmallmatrix*}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vsmallmatrix*}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newenvironment {psmallmatrix}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bsmallmatrix}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bsmallmatrix}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vsmallmatrix}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vsmallmatrix}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newcommand {\LWRmultlined }[1][]{\begin {multline*}}\)
\(\newenvironment {multlined}[1][]{\LWRmultlined }{\end {multline*}}\)
\(\let \LWRorigshoveleft \shoveleft \)
\(\renewcommand {\shoveleft }[1][]{\LWRorigshoveleft }\)
\(\let \LWRorigshoveright \shoveright \)
\(\renewcommand {\shoveright }[1][]{\LWRorigshoveright }\)
\(\newenvironment {dcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {dcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {rcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {rcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {drcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {drcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {cases*}{\begin {cases}}{\end {cases}}\)
\(\newcommand {\MoveEqLeft }[1][]{}\)
\(\def \LWRAboxed #1!|!{\fbox {\(#1\)}&\fbox {\(#2\)}} \newcommand {\Aboxed }[1]{\LWRAboxed #1&&!|!} \)
\( \newcommand {\LWRABLines }[1][\Updownarrow ]{#1 \notag \\}\newcommand {\ArrowBetweenLines }{\ifstar \LWRABLines \LWRABLines } \)
\(\newcommand {\shortintertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\vdotswithin }[1]{\hspace {.5em}\vdots }\)
\(\newcommand {\LWRshortvdotswithinstar }[1]{\vdots \hspace {.5em} & \\}\)
\(\newcommand {\LWRshortvdotswithinnostar }[1]{& \hspace {.5em}\vdots \\}\)
\(\newcommand {\shortvdotswithin }{\ifstar \LWRshortvdotswithinstar \LWRshortvdotswithinnostar }\)
\(\newcommand {\MTFlushSpaceAbove }{}\)
\(\newcommand {\MTFlushSpaceBelow }{\\}\)
\(\newcommand \lparen {(}\)
\(\newcommand \rparen {)}\)
\(\newcommand {\ordinarycolon }{:}\)
\(\newcommand {\vcentcolon }{\mathrel {\mathop \ordinarycolon }}\)
\(\newcommand \dblcolon {\vcentcolon \vcentcolon }\)
\(\newcommand \coloneqq {\vcentcolon =}\)
\(\newcommand \Coloneqq {\dblcolon =}\)
\(\newcommand \coloneq {\vcentcolon {-}}\)
\(\newcommand \Coloneq {\dblcolon {-}}\)
\(\newcommand \eqqcolon {=\vcentcolon }\)
\(\newcommand \Eqqcolon {=\dblcolon }\)
\(\newcommand \eqcolon {\mathrel {-}\vcentcolon }\)
\(\newcommand \Eqcolon {\mathrel {-}\dblcolon }\)
\(\newcommand \colonapprox {\vcentcolon \approx }\)
\(\newcommand \Colonapprox {\dblcolon \approx }\)
\(\newcommand \colonsim {\vcentcolon \sim }\)
\(\newcommand \Colonsim {\dblcolon \sim }\)
\(\newcommand {\nuparrow }{\mathrel {\cancel {\uparrow }}}\)
\(\newcommand {\ndownarrow }{\mathrel {\cancel {\downarrow }}}\)
\(\newcommand {\bigtimes }{\mathop {\Large \times }\limits }\)
\(\newcommand {\prescript }[3]{{}^{#1}_{#2}#3}\)
\(\newenvironment {lgathered}{\begin {gathered}}{\end {gathered}}\)
\(\newenvironment {rgathered}{\begin {gathered}}{\end {gathered}}\)
\(\newcommand {\splitfrac }[2]{{}^{#1}_{#2}}\)
\(\let \splitdfrac \splitfrac \)
\(\newcommand {\LWRoverlaysymbols }[2]{\mathord {\smash {\mathop {#2\strut }\limits ^{\smash {\lower 3ex{#1}}}}\strut }}\)
\(\newcommand{\alphaup}{\unicode{x03B1}}\)
\(\newcommand{\betaup}{\unicode{x03B2}}\)
\(\newcommand{\gammaup}{\unicode{x03B3}}\)
\(\newcommand{\digammaup}{\unicode{x03DD}}\)
\(\newcommand{\deltaup}{\unicode{x03B4}}\)
\(\newcommand{\epsilonup}{\unicode{x03F5}}\)
\(\newcommand{\varepsilonup}{\unicode{x03B5}}\)
\(\newcommand{\zetaup}{\unicode{x03B6}}\)
\(\newcommand{\etaup}{\unicode{x03B7}}\)
\(\newcommand{\thetaup}{\unicode{x03B8}}\)
\(\newcommand{\varthetaup}{\unicode{x03D1}}\)
\(\newcommand{\iotaup}{\unicode{x03B9}}\)
\(\newcommand{\kappaup}{\unicode{x03BA}}\)
\(\newcommand{\varkappaup}{\unicode{x03F0}}\)
\(\newcommand{\lambdaup}{\unicode{x03BB}}\)
\(\newcommand{\muup}{\unicode{x03BC}}\)
\(\newcommand{\nuup}{\unicode{x03BD}}\)
\(\newcommand{\xiup}{\unicode{x03BE}}\)
\(\newcommand{\omicronup}{\unicode{x03BF}}\)
\(\newcommand{\piup}{\unicode{x03C0}}\)
\(\newcommand{\varpiup}{\unicode{x03D6}}\)
\(\newcommand{\rhoup}{\unicode{x03C1}}\)
\(\newcommand{\varrhoup}{\unicode{x03F1}}\)
\(\newcommand{\sigmaup}{\unicode{x03C3}}\)
\(\newcommand{\varsigmaup}{\unicode{x03C2}}\)
\(\newcommand{\tauup}{\unicode{x03C4}}\)
\(\newcommand{\upsilonup}{\unicode{x03C5}}\)
\(\newcommand{\phiup}{\unicode{x03D5}}\)
\(\newcommand{\varphiup}{\unicode{x03C6}}\)
\(\newcommand{\chiup}{\unicode{x03C7}}\)
\(\newcommand{\psiup}{\unicode{x03C8}}\)
\(\newcommand{\omegaup}{\unicode{x03C9}}\)
\(\newcommand{\Alphaup}{\unicode{x0391}}\)
\(\newcommand{\Betaup}{\unicode{x0392}}\)
\(\newcommand{\Gammaup}{\unicode{x0393}}\)
\(\newcommand{\Digammaup}{\unicode{x03DC}}\)
\(\newcommand{\Deltaup}{\unicode{x0394}}\)
\(\newcommand{\Epsilonup}{\unicode{x0395}}\)
\(\newcommand{\Zetaup}{\unicode{x0396}}\)
\(\newcommand{\Etaup}{\unicode{x0397}}\)
\(\newcommand{\Thetaup}{\unicode{x0398}}\)
\(\newcommand{\Varthetaup}{\unicode{x03F4}}\)
\(\newcommand{\Iotaup}{\unicode{x0399}}\)
\(\newcommand{\Kappaup}{\unicode{x039A}}\)
\(\newcommand{\Lambdaup}{\unicode{x039B}}\)
\(\newcommand{\Muup}{\unicode{x039C}}\)
\(\newcommand{\Nuup}{\unicode{x039D}}\)
\(\newcommand{\Xiup}{\unicode{x039E}}\)
\(\newcommand{\Omicronup}{\unicode{x039F}}\)
\(\newcommand{\Piup}{\unicode{x03A0}}\)
\(\newcommand{\Varpiup}{\unicode{x03D6}}\)
\(\newcommand{\Rhoup}{\unicode{x03A1}}\)
\(\newcommand{\Sigmaup}{\unicode{x03A3}}\)
\(\newcommand{\Tauup}{\unicode{x03A4}}\)
\(\newcommand{\Upsilonup}{\unicode{x03A5}}\)
\(\newcommand{\Phiup}{\unicode{x03A6}}\)
\(\newcommand{\Chiup}{\unicode{x03A7}}\)
\(\newcommand{\Psiup}{\unicode{x03A8}}\)
\(\newcommand{\Omegaup}{\unicode{x03A9}}\)
\(\newcommand{\alphait}{\unicode{x1D6FC}}\)
\(\newcommand{\betait}{\unicode{x1D6FD}}\)
\(\newcommand{\gammait}{\unicode{x1D6FE}}\)
\(\newcommand{\digammait}{\mathit{\unicode{x03DD}}}\)
\(\newcommand{\deltait}{\unicode{x1D6FF}}\)
\(\newcommand{\epsilonit}{\unicode{x1D716}}\)
\(\newcommand{\varepsilonit}{\unicode{x1D700}}\)
\(\newcommand{\zetait}{\unicode{x1D701}}\)
\(\newcommand{\etait}{\unicode{x1D702}}\)
\(\newcommand{\thetait}{\unicode{x1D703}}\)
\(\newcommand{\varthetait}{\unicode{x1D717}}\)
\(\newcommand{\iotait}{\unicode{x1D704}}\)
\(\newcommand{\kappait}{\unicode{x1D705}}\)
\(\newcommand{\varkappait}{\unicode{x1D718}}\)
\(\newcommand{\lambdait}{\unicode{x1D706}}\)
\(\newcommand{\muit}{\unicode{x1D707}}\)
\(\newcommand{\nuit}{\unicode{x1D708}}\)
\(\newcommand{\xiit}{\unicode{x1D709}}\)
\(\newcommand{\omicronit}{\unicode{x1D70A}}\)
\(\newcommand{\piit}{\unicode{x1D70B}}\)
\(\newcommand{\varpiit}{\unicode{x1D71B}}\)
\(\newcommand{\rhoit}{\unicode{x1D70C}}\)
\(\newcommand{\varrhoit}{\unicode{x1D71A}}\)
\(\newcommand{\sigmait}{\unicode{x1D70E}}\)
\(\newcommand{\varsigmait}{\unicode{x1D70D}}\)
\(\newcommand{\tauit}{\unicode{x1D70F}}\)
\(\newcommand{\upsilonit}{\unicode{x1D710}}\)
\(\newcommand{\phiit}{\unicode{x1D719}}\)
\(\newcommand{\varphiit}{\unicode{x1D711}}\)
\(\newcommand{\chiit}{\unicode{x1D712}}\)
\(\newcommand{\psiit}{\unicode{x1D713}}\)
\(\newcommand{\omegait}{\unicode{x1D714}}\)
\(\newcommand{\Alphait}{\unicode{x1D6E2}}\)
\(\newcommand{\Betait}{\unicode{x1D6E3}}\)
\(\newcommand{\Gammait}{\unicode{x1D6E4}}\)
\(\newcommand{\Digammait}{\mathit{\unicode{x03DC}}}\)
\(\newcommand{\Deltait}{\unicode{x1D6E5}}\)
\(\newcommand{\Epsilonit}{\unicode{x1D6E6}}\)
\(\newcommand{\Zetait}{\unicode{x1D6E7}}\)
\(\newcommand{\Etait}{\unicode{x1D6E8}}\)
\(\newcommand{\Thetait}{\unicode{x1D6E9}}\)
\(\newcommand{\Varthetait}{\unicode{x1D6F3}}\)
\(\newcommand{\Iotait}{\unicode{x1D6EA}}\)
\(\newcommand{\Kappait}{\unicode{x1D6EB}}\)
\(\newcommand{\Lambdait}{\unicode{x1D6EC}}\)
\(\newcommand{\Muit}{\unicode{x1D6ED}}\)
\(\newcommand{\Nuit}{\unicode{x1D6EE}}\)
\(\newcommand{\Xiit}{\unicode{x1D6EF}}\)
\(\newcommand{\Omicronit}{\unicode{x1D6F0}}\)
\(\newcommand{\Piit}{\unicode{x1D6F1}}\)
\(\newcommand{\Rhoit}{\unicode{x1D6F2}}\)
\(\newcommand{\Sigmait}{\unicode{x1D6F4}}\)
\(\newcommand{\Tauit}{\unicode{x1D6F5}}\)
\(\newcommand{\Upsilonit}{\unicode{x1D6F6}}\)
\(\newcommand{\Phiit}{\unicode{x1D6F7}}\)
\(\newcommand{\Chiit}{\unicode{x1D6F8}}\)
\(\newcommand{\Psiit}{\unicode{x1D6F9}}\)
\(\newcommand{\Omegait}{\unicode{x1D6FA}}\)
\(\let \digammaup \Digammaup \)
\(\renewcommand {\digammait }{\mathit {\digammaup }}\)
\(\newcommand {\smallin }{\unicode {x220A}}\)
\(\newcommand {\smallowns }{\unicode {x220D}}\)
\(\newcommand {\notsmallin }{\LWRoverlaysymbols {/}{\unicode {x220A}}}\)
\(\newcommand {\notsmallowns }{\LWRoverlaysymbols {/}{\unicode {x220D}}}\)
\(\newcommand {\rightangle }{\unicode {x221F}}\)
\(\newcommand {\intclockwise }{\unicode {x2231}}\)
\(\newcommand {\ointclockwise }{\unicode {x2232}}\)
\(\newcommand {\ointctrclockwise }{\unicode {x2233}}\)
\(\newcommand {\oiint }{\unicode {x222F}}\)
\(\newcommand {\oiiint }{\unicode {x2230}}\)
\(\newcommand {\ddag }{\unicode {x2021}}\)
\(\newcommand {\P }{\unicode {x00B6}}\)
\(\newcommand {\copyright }{\unicode {x00A9}}\)
\(\newcommand {\dag }{\unicode {x2020}}\)
\(\newcommand {\pounds }{\unicode {x00A3}}\)
\(\newcommand {\iddots }{\unicode {x22F0}}\)
\(\newcommand {\utimes }{\overline {\times }}\)
\(\newcommand {\dtimes }{\underline {\times }}\)
\(\newcommand {\udtimes }{\overline {\underline {\times }}}\)
\(\newcommand {\leftwave }{\left \{}\)
\(\newcommand {\rightwave }{\right \}}\)
\(\newcommand {\toprule }[1][]{\hline }\)
\(\let \midrule \toprule \)
\(\let \bottomrule \toprule \)
\(\newcommand {\cmidrule }[2][]{}\)
\(\newcommand {\morecmidrules }{}\)
\(\newcommand {\specialrule }[3]{\hline }\)
\(\newcommand {\addlinespace }[1][]{}\)
\(\newcommand {\LWRsubmultirow }[2][]{#2}\)
\(\newcommand {\LWRmultirow }[2][]{\LWRsubmultirow }\)
\(\newcommand {\multirow }[2][]{\LWRmultirow }\)
\(\newcommand {\mrowcell }{}\)
\(\newcommand {\mcolrowcell }{}\)
\(\newcommand {\STneed }[1]{}\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\newcommand {\tothe }[1]{^{#1}}\)
\(\newcommand {\raiseto }[2]{{#2}^{#1}}\)
\(\newcommand {\ang }[2][]{(\mathrm {#2})\degree }\)
\(\newcommand {\num }[2][]{\mathrm {#2}}\)
\(\newcommand {\si }[2][]{\mathrm {#2}}\)
\(\newcommand {\LWRSI }[2][]{\mathrm {#1\LWRSInumber \,#2}}\)
\(\newcommand {\SI }[2][]{\def \LWRSInumber {#2}\LWRSI }\)
\(\newcommand {\numlist }[2][]{\mathrm {#2}}\)
\(\newcommand {\numrange }[3][]{\mathrm {#2\,\unicode {x2013}\,#3}}\)
\(\newcommand {\SIlist }[3][]{\mathrm {#2\,#3}}\)
\(\newcommand {\SIrange }[4][]{\mathrm {#2\,#4\,\unicode {x2013}\,#3\,#4}}\)
\(\newcommand {\tablenum }[2][]{\mathrm {#2}}\)
\(\newcommand {\ampere }{\mathrm {A}}\)
\(\newcommand {\candela }{\mathrm {cd}}\)
\(\newcommand {\kelvin }{\mathrm {K}}\)
\(\newcommand {\kilogram }{\mathrm {kg}}\)
\(\newcommand {\metre }{\mathrm {m}}\)
\(\newcommand {\mole }{\mathrm {mol}}\)
\(\newcommand {\second }{\mathrm {s}}\)
\(\newcommand {\becquerel }{\mathrm {Bq}}\)
\(\newcommand {\degreeCelsius }{\unicode {x2103}}\)
\(\newcommand {\coulomb }{\mathrm {C}}\)
\(\newcommand {\farad }{\mathrm {F}}\)
\(\newcommand {\gray }{\mathrm {Gy}}\)
\(\newcommand {\hertz }{\mathrm {Hz}}\)
\(\newcommand {\henry }{\mathrm {H}}\)
\(\newcommand {\joule }{\mathrm {J}}\)
\(\newcommand {\katal }{\mathrm {kat}}\)
\(\newcommand {\lumen }{\mathrm {lm}}\)
\(\newcommand {\lux }{\mathrm {lx}}\)
\(\newcommand {\newton }{\mathrm {N}}\)
\(\newcommand {\ohm }{\mathrm {\Omega }}\)
\(\newcommand {\pascal }{\mathrm {Pa}}\)
\(\newcommand {\radian }{\mathrm {rad}}\)
\(\newcommand {\siemens }{\mathrm {S}}\)
\(\newcommand {\sievert }{\mathrm {Sv}}\)
\(\newcommand {\steradian }{\mathrm {sr}}\)
\(\newcommand {\tesla }{\mathrm {T}}\)
\(\newcommand {\volt }{\mathrm {V}}\)
\(\newcommand {\watt }{\mathrm {W}}\)
\(\newcommand {\weber }{\mathrm {Wb}}\)
\(\newcommand {\day }{\mathrm {d}}\)
\(\newcommand {\degree }{\mathrm {^\circ }}\)
\(\newcommand {\hectare }{\mathrm {ha}}\)
\(\newcommand {\hour }{\mathrm {h}}\)
\(\newcommand {\litre }{\mathrm {l}}\)
\(\newcommand {\liter }{\mathrm {L}}\)
\(\newcommand {\arcminute }{^\prime }\)
\(\newcommand {\minute }{\mathrm {min}}\)
\(\newcommand {\arcsecond }{^{\prime \prime }}\)
\(\newcommand {\tonne }{\mathrm {t}}\)
\(\newcommand {\astronomicalunit }{au}\)
\(\newcommand {\atomicmassunit }{u}\)
\(\newcommand {\bohr }{\mathit {a}_0}\)
\(\newcommand {\clight }{\mathit {c}_0}\)
\(\newcommand {\dalton }{\mathrm {D}_\mathrm {a}}\)
\(\newcommand {\electronmass }{\mathit {m}_{\mathrm {e}}}\)
\(\newcommand {\electronvolt }{\mathrm {eV}}\)
\(\newcommand {\elementarycharge }{\mathit {e}}\)
\(\newcommand {\hartree }{\mathit {E}_{\mathrm {h}}}\)
\(\newcommand {\planckbar }{\mathit {\unicode {x210F}}}\)
\(\newcommand {\angstrom }{\mathrm {\unicode {x212B}}}\)
\(\let \LWRorigbar \bar \)
\(\newcommand {\bar }{\mathrm {bar}}\)
\(\newcommand {\barn }{\mathrm {b}}\)
\(\newcommand {\bel }{\mathrm {B}}\)
\(\newcommand {\decibel }{\mathrm {dB}}\)
\(\newcommand {\knot }{\mathrm {kn}}\)
\(\newcommand {\mmHg }{\mathrm {mmHg}}\)
\(\newcommand {\nauticalmile }{\mathrm {M}}\)
\(\newcommand {\neper }{\mathrm {Np}}\)
\(\newcommand {\yocto }{\mathrm {y}}\)
\(\newcommand {\zepto }{\mathrm {z}}\)
\(\newcommand {\atto }{\mathrm {a}}\)
\(\newcommand {\femto }{\mathrm {f}}\)
\(\newcommand {\pico }{\mathrm {p}}\)
\(\newcommand {\nano }{\mathrm {n}}\)
\(\newcommand {\micro }{\mathrm {\unicode {x00B5}}}\)
\(\newcommand {\milli }{\mathrm {m}}\)
\(\newcommand {\centi }{\mathrm {c}}\)
\(\newcommand {\deci }{\mathrm {d}}\)
\(\newcommand {\deca }{\mathrm {da}}\)
\(\newcommand {\hecto }{\mathrm {h}}\)
\(\newcommand {\kilo }{\mathrm {k}}\)
\(\newcommand {\mega }{\mathrm {M}}\)
\(\newcommand {\giga }{\mathrm {G}}\)
\(\newcommand {\tera }{\mathrm {T}}\)
\(\newcommand {\peta }{\mathrm {P}}\)
\(\newcommand {\exa }{\mathrm {E}}\)
\(\newcommand {\zetta }{\mathrm {Z}}\)
\(\newcommand {\yotta }{\mathrm {Y}}\)
\(\newcommand {\percent }{\mathrm {\%}}\)
\(\newcommand {\meter }{\mathrm {m}}\)
\(\newcommand {\metre }{\mathrm {m}}\)
\(\newcommand {\gram }{\mathrm {g}}\)
\(\newcommand {\kg }{\kilo \gram }\)
\(\newcommand {\of }[1]{_{\mathrm {#1}}}\)
\(\newcommand {\squared }{^2}\)
\(\newcommand {\square }[1]{\mathrm {#1}^2}\)
\(\newcommand {\cubed }{^3}\)
\(\newcommand {\cubic }[1]{\mathrm {#1}^3}\)
\(\newcommand {\per }{/}\)
\(\newcommand {\celsius }{\unicode {x2103}}\)
\(\newcommand {\fg }{\femto \gram }\)
\(\newcommand {\pg }{\pico \gram }\)
\(\newcommand {\ng }{\nano \gram }\)
\(\newcommand {\ug }{\micro \gram }\)
\(\newcommand {\mg }{\milli \gram }\)
\(\newcommand {\g }{\gram }\)
\(\newcommand {\kg }{\kilo \gram }\)
\(\newcommand {\amu }{\mathrm {u}}\)
\(\newcommand {\nm }{\nano \metre }\)
\(\newcommand {\um }{\micro \metre }\)
\(\newcommand {\mm }{\milli \metre }\)
\(\newcommand {\cm }{\centi \metre }\)
\(\newcommand {\dm }{\deci \metre }\)
\(\newcommand {\m }{\metre }\)
\(\newcommand {\km }{\kilo \metre }\)
\(\newcommand {\as }{\atto \second }\)
\(\newcommand {\fs }{\femto \second }\)
\(\newcommand {\ps }{\pico \second }\)
\(\newcommand {\ns }{\nano \second }\)
\(\newcommand {\us }{\micro \second }\)
\(\newcommand {\ms }{\milli \second }\)
\(\newcommand {\s }{\second }\)
\(\newcommand {\fmol }{\femto \mol }\)
\(\newcommand {\pmol }{\pico \mol }\)
\(\newcommand {\nmol }{\nano \mol }\)
\(\newcommand {\umol }{\micro \mol }\)
\(\newcommand {\mmol }{\milli \mol }\)
\(\newcommand {\mol }{\mol }\)
\(\newcommand {\kmol }{\kilo \mol }\)
\(\newcommand {\pA }{\pico \ampere }\)
\(\newcommand {\nA }{\nano \ampere }\)
\(\newcommand {\uA }{\micro \ampere }\)
\(\newcommand {\mA }{\milli \ampere }\)
\(\newcommand {\A }{\ampere }\)
\(\newcommand {\kA }{\kilo \ampere }\)
\(\newcommand {\ul }{\micro \litre }\)
\(\newcommand {\ml }{\milli \litre }\)
\(\newcommand {\l }{\litre }\)
\(\newcommand {\hl }{\hecto \litre }\)
\(\newcommand {\uL }{\micro \liter }\)
\(\newcommand {\mL }{\milli \liter }\)
\(\newcommand {\L }{\liter }\)
\(\newcommand {\hL }{\hecto \liter }\)
\(\newcommand {\mHz }{\milli \hertz }\)
\(\newcommand {\Hz }{\hertz }\)
\(\newcommand {\kHz }{\kilo \hertz }\)
\(\newcommand {\MHz }{\mega \hertz }\)
\(\newcommand {\GHz }{\giga \hertz }\)
\(\newcommand {\THz }{\tera \hertz }\)
\(\newcommand {\mN }{\milli \newton }\)
\(\newcommand {\N }{\newton }\)
\(\newcommand {\kN }{\kilo \newton }\)
\(\newcommand {\MN }{\mega \newton }\)
\(\newcommand {\Pa }{\pascal }\)
\(\newcommand {\kPa }{\kilo \pascal }\)
\(\newcommand {\MPa }{\mega \pascal }\)
\(\newcommand {\GPa }{\giga \pascal }\)
\(\newcommand {\mohm }{\milli \ohm }\)
\(\newcommand {\kohm }{\kilo \ohm }\)
\(\newcommand {\Mohm }{\mega \ohm }\)
\(\newcommand {\pV }{\pico \volt }\)
\(\newcommand {\nV }{\nano \volt }\)
\(\newcommand {\uV }{\micro \volt }\)
\(\newcommand {\mV }{\milli \volt }\)
\(\newcommand {\V }{\volt }\)
\(\newcommand {\kV }{\kilo \volt }\)
\(\newcommand {\W }{\watt }\)
\(\newcommand {\uW }{\micro \watt }\)
\(\newcommand {\mW }{\milli \watt }\)
\(\newcommand {\kW }{\kilo \watt }\)
\(\newcommand {\MW }{\mega \watt }\)
\(\newcommand {\GW }{\giga \watt }\)
\(\newcommand {\J }{\joule }\)
\(\newcommand {\uJ }{\micro \joule }\)
\(\newcommand {\mJ }{\milli \joule }\)
\(\newcommand {\kJ }{\kilo \joule }\)
\(\newcommand {\eV }{\electronvolt }\)
\(\newcommand {\meV }{\milli \electronvolt }\)
\(\newcommand {\keV }{\kilo \electronvolt }\)
\(\newcommand {\MeV }{\mega \electronvolt }\)
\(\newcommand {\GeV }{\giga \electronvolt }\)
\(\newcommand {\TeV }{\tera \electronvolt }\)
\(\newcommand {\kWh }{\kilo \watt \hour }\)
\(\newcommand {\F }{\farad }\)
\(\newcommand {\fF }{\femto \farad }\)
\(\newcommand {\pF }{\pico \farad }\)
\(\newcommand {\K }{\mathrm {K}}\)
\(\newcommand {\dB }{\mathrm {dB}}\)
\(\newcommand {\kibi }{\mathrm {Ki}}\)
\(\newcommand {\mebi }{\mathrm {Mi}}\)
\(\newcommand {\gibi }{\mathrm {Gi}}\)
\(\newcommand {\tebi }{\mathrm {Ti}}\)
\(\newcommand {\pebi }{\mathrm {Pi}}\)
\(\newcommand {\exbi }{\mathrm {Ei}}\)
\(\newcommand {\zebi }{\mathrm {Zi}}\)
\(\newcommand {\yobi }{\mathrm {Yi}}\)
\(\require {mhchem}\)
\(\require {cancel}\)
\(\newcommand {\fint }{âĺŊ}\)
\(\newcommand {\hdots }{\cdots }\)
\(\newcommand {\mathnormal }[1]{#1}\)
\(\newcommand {\vecs }[2]{\vec {#1}_{#2}}\)
\(\newcommand {\code }[1]{\lstinline [basicstyle=\ttfamily ]{#1}}\)
\(\renewcommand {\O }{\ensuremath {\mathcal {O}}}\)
\(\newcommand {\source }{\ensuremath {\operatorname {source}}}\)
\(\newcommand {\target }{\ensuremath {\operatorname {target}}}\)
\(\renewcommand {\num }{\ensuremath {\operatorname {num}}}\)
\(\newcommand {\indeg }{\ensuremath {\operatorname {indeg}}}\)
\(\newcommand {\mycap }{\ensuremath {\operatorname {cap}}}\)
\(\newcommand {\cost }{\ensuremath {\operatorname {cost}}}\)
\(\newcommand {\pot }{\ensuremath {\operatorname {pot}}}\)
\(\newcommand {\ccost }{\ensuremath {\operatorname {ccost}}}\)
\(\newcommand {\dcost }{\ensuremath {\operatorname {dcost}}}\)
\(\newcommand {\icost }{\ensuremath {\operatorname {icost}}}\)
\(\newcommand {\qed }{\hfill $\Box $}\)
\(\newcommand {\fracsize }[1]{{\large #1}}\)
\(\newcommand {\matrixsize }[1]{{\scriptsize #1}}\)
\(\newcommand {\name }[1]{\textsc {#1}}\)
\(\newcommand {\smallpmatrix }[1]{\left (\begin {smallmatrix}#1\end {smallmatrix}\right )}\)
\(\newcommand {\matlab }{{\fontfamily {bch}\scshape \selectfont {}Matlab}}\)
\(\newcommand {\innerproduct }[1]{\left \langle {#1}\right \rangle }\)
\(\newcommand {\norm }[1]{\left \Vert {#1}\right \Vert }\)
\(\renewcommand {\natural }{\mathbb {N}}\)
\(\newcommand {\integer }{\mathbb {Z}}\)
\(\newcommand {\rational }{\mathbb {Q}}\)
\(\newcommand {\real }{\mathbb {R}}\)
\(\newcommand {\complex }{\mathbb {C}}\)
\(\renewcommand {\d }{\mathop {}\!\mathrm {d}}\)
\(\newcommand {\dr }{\d {}r}\)
\(\newcommand {\ds }{\d {}s}\)
\(\newcommand {\dt }{\d {}t}\)
\(\newcommand {\du }{\d {}u}\)
\(\newcommand {\dv }{\d {}v}\)
\(\newcommand {\dw }{\d {}w}\)
\(\newcommand {\dx }{\d {}x}\)
\(\newcommand {\dy }{\d {}y}\)
\(\newcommand {\dz }{\d {}z}\)
\(\newcommand {\dsigma }{\d {}\sigma }\)
\(\newcommand {\dphi }{\d {}\phi }\)
\(\newcommand {\dvarphi }{\d {}\varphi }\)
\(\newcommand {\dtau }{\d {}\tau }\)
\(\newcommand {\dxi }{\d {}\xi }\)
\(\newcommand {\dtheta }{\d {}\theta }\)
\(\newcommand {\tp }{\mathrm {T}}\)
Allgemeines
Gegeben sei ein zusammenhängender, ungerichteter Graph \(G = (V, E, c)\) mit Kostenfunktion \(c: E \rightarrow \mathbb {R}^+\). Gesucht ist \(E’ \subseteq E\) mit \(G’ = (V, E’)\) als
zusammenhängender Teilgraph, sodass \(\sum _{e’ \in E’} c(e’)\) minimal wird. Ein solcher Teilgraph heißt minimaler Spannbaum oder auch MST (minimal spanning tree).
Anwendungen: Kommikationsnetzwerke (Unternehmen möchte Kommunikationsnetz aufbauen, dabei alle mit minimalen Kosten verbinden) und als Hilfsmittel z. B. für die Lösung
des TSP (travelling salesman problem).
Was ist ein Baum? Ein ungerichteter Graph heißt Baum, falls
er minimal zusammenhängend ist
er zusammenhängend ist und \(n - 1\) Kanten hat (\(n\) Knoten)
er maximal zyklenfrei ist.
Beobachtung: Die \(E’\) formen einen Baum.
Beweis: Die \(E’\) müssen einen zusammenhängenden Graph induzieren. Falls dieser kein Baum ist, gibt es einen Zyklus. Wegnahme einer Kante des Zyklus verletzt den Zusammenhang nicht, macht
aber die Lösung billiger. Widerspruch, denn \(E’\) muss minimale Kosten haben.
Prims Algorithmus
Man fängt mit einem beliebigen Knoten an. Nun betrachtet man alle Kanten, die zu den bisherigen aufgenommen Knoten inzident sind, und fügt die Kante mit dem kleinsten Gewicht hinzu. Dies macht man
solange, bis alle Knoten aufgenommen wurden.
Laufzeit: naiv \(\O (n \cdot m)\), da \(n\) Knoten aufgenommen werden und jedes Mal aus maximal \(m\) Kanten die billigste ausgesucht werden muss.
besser: Organisiere Knoten, die bislang noch nicht im Spannbaum sind, in einem Heap.
Seien \(S\) die Knoten im bereits konstruierten Spannbaum und \(V \setminus S\) der Rest. Man organisiert \(V \setminus S\) in einem Min-Heap gemäß ihrem minimalen Abstand zu einem Knoten in \(S\).
Zu Beginn ist \(|S| = 1\) und alle Knoten in \(V \setminus S\) sind mit ihrem Kantengewicht zum Startknoten im Heap (\(\O (n)\), da max. \(n\) Knoten aufgenommen werden müssen).
Wird ein Knoten \(v\) nun hinzugenommen, so entferne das Minimum aus dem Heap (also der Knoten, der am billigsten angebunden werden kann, \(\O (\log n)\)). Gehe dann alle Kanten \((v, w)\) durch, falls \(w \in V
\setminus S\) und der Distanzwert von \(w\) im Heap größer als \(c(v, w)\) ist, muss der Schlüssel von \(w\) in \(c(v, w)\) geändert werden (\(\O (\log n)\), change_key). Insgesamt werden so alle \(m\) Kanten einmal betrachtet, also beträgt die Gesamtlaufzeit \(\O (m \log n)\), da \(n \le m\) ist.
Korrektheit: Prims Algorithmus berechnet einen MST.
Beweis: In jeder „Runde“ wird die billigste Kante zwischen \(S\) und \(V \setminus S\) hinzugenommen. Gemäß cut property ist diese Kante Teil jeden MSTs. Der Algorithmus terminiert erst
für \(S = V\), die Kanten sind alle Teil jeden MSTs, also ist \(S\) am Ende auch ein MST.
Lemma (cut property): Sei \(S \subseteq V\) und \(e = (v, w)\) die Kante mit minimalem Gewicht zwischen \(S\) und \(V \setminus S\). Dann ist \(e\) in jedem MST von \(G\) enthalten.
Beweis: Betrachte alle Kanten \(E^\ast \) eines MST, der \(e\) nicht enthält. In \(E^\ast \) muss eine Kante \(e’\) zwischen \(S\) und \(V \setminus S\) verlaufen, da der MST ein Spannbaum
ist.
Nimmt man \(e\) zu \(E^\ast \) hinzu, so entsteht ein Zyklus. Dieser Zyklus übertritt die Grenze zwischen \(S\) und \(V \setminus S\) ein weiteres Mal, dieser Übertritt ist teurer als \(e\) (da \(e\)
minimales Gewicht). Also verringert das Aufnehmen von \(e\) und das Löschen des Übertritts die Kosten und erhält den Zusammenhang. Damit war der MST nicht minimal, ein Widerspruch.
Kruskals Algorithmus
Man ordnet zunächst alle Kanten aufsteigend nach ihrem Gewicht. Betrachte dann alle Kanten nacheinander: Wenn die Kante zwei beliebige bisher nicht verbundene Knoten verbindet, nimmt man sie in \(E’\) auf,
ansonsten betrachtet man sie nicht mehr.
Korrektheit: 1. \(E’\) bildet einen zusammenhängenden Graph. 2. \(E’\) bildet einen Baum.
3. \(E’\) bildet einen MST.
Beweis: 1. Angenommen, \(E’\) bildet nicht einen zusammenhängenden Graph, dann zerfällt \((V, E’)\) in mehrere ZHKs. Damit existiert in \(G = (V, E)\) eine Kante, die zwei dieser ZHKs
verbindet. Sie muss vom Algorithmus weggeworfen sein (andernfalls wäre sie in \(E’\)), ein Widerspruch, da der Algorithmus die Kante hätte aufnehmen müssen.
2. \(E’\) bildet einen Baum, da zyklenschließende Kanten weggeworfen werden.
3. Wenn eine Kante \(e = (v, w)\) in \(E’\) aufgenommen wird, kann man folgende Partitionierung vornehmen: Zu \(P\) gehört die ZHK von \(v\) und \(V \setminus P\) ist die ZHK von \(w\) sowie alle
anderen Knoten. Nach der cut property ist \(e\) in jeder MST enthalten, da es keine billigere Kante zwischen \(P\) und \(V \setminus P\) gibt.
Datenstruktur für effiziente Implementierung: Eine solche Datenstruktur muss folgende Operationen unterstützen: 1. teste, ob Knoten \(v\) und \(w\) in gleicher ZHK sind
2. vereinige ZHKs von \(v\) und \(w\), d. h. drücke aus, dass \(v\) und \(w\) ab jetzt in gleicher ZHK sind.
Union-Find-Datenstruktur: Gegeben sei ein Universerum \(U = \{1, \dotsc , N\}\). Man will eine Partition von \(U\), also einer Zerlegung in disjunkte Teilmengen, verwalten, wobei die folgenden Operationen
zulässig sein sollen:
InitPartition(\(N\)): legt Partition in \(N\) Teilmengen an
Find(\(x\)):
gibt für \(x \in U\) einen eindeutigen Bezeichner der Teilmenge, in der \(x\) liegt, zurück
Union(\(x, y\)):
vereinigt für \(x, y \in U\) (\(x, y\) nicht in gleicher Teilmenge) die beiden Teilmengen
Anwendung im Fall von Kruskals Algorithmus: Das Universum entspricht den Knoten des Graphen, die Teilmengen entsprechen den ZHKs während des Ablaufs des
Algorithmus.
Wenn eine Kante \(e = (v, w)\) betrachtet wird, muss entschieden werden, ob \(v\) und \(w\) in gleicher ZHK liegen, d. h. es muss überprüft werden, ob Find(\(v\)) \(=\) Find(\(w\)).
Falls dies nicht der Fall ist, wird die Kante als Teil des MST gewählt und die ZHKs werden verschmolzen, d. h. Union(\(v, w\)) muss aufgerufen werden.
Kruskals Algorithmus führt dabei höchstens \(m\) Finds und \(n - 1\) Unions aus.
Implementierung: Stelle ein Array TM[] der Größe \(N\) zur Verfügung, in dem für jedes Element \(v\) ein kanonisches
Element der Teilmenge, die \(v\) enthält, als Repräsentant gespeichert wird. Zu Beginn ist jede Teilmenge einelementig: TM[\(v\)] \(= v\).
Zusätzlich soll noch für jeden Repräsentanten \(v\) eine Liste der Elemente der Teilmenge, deren Repräsentant \(v\) ist, sowie die Länge dieser Liste gespeichert werden.
InitPartition(\(N\)): klar
Find(\(v\)): gib TM[\(v\)] zurück (Kosten \(\O (1)\))
Union(\(v, w\)): Ohne Einschränkung befinde sich \(w\) in der kleineren
Teilmenge.
Dann setze TM[\(x\)] \(:=\) Find(\(v\)) für alle \(x\) mit TM[\(x\)] \(=\) Find(\(w\)), hänge die Liste von Find(\(w\)) an
Find(\(v\)) und aktualisiere die Listenlängen
(Kosten \(\O (\)Länge der Liste von Find(\(w\))\()\)).
Laufzeitanalyse: Union muss im schlimmsten Fall \(\frac {N}{2}\) Knoten umsetzen. Die Gesamtkosten für \(n\) Unions sind \(G = \sum
_{i=1}^n \;(\)Kosten für \(i\)-te Union-Operation\()\). Es gilt nun \(G \le N \log N\), d. h. es kann nicht sein, dass jede der Union-Operationen \(\frac {N}{2}\) kostet.
Beweis: Man betrachtet die Anzahl der Umsetzungen eines bestimmten Knotens \(v\), d. h. man schaut, wie oft sich TM[\(v\)] ändert. Die Gesamtkosten sind dann \(G = \sum _v \;(\)Anzahl, wie oft sich TM[\(v\)] ändert\()\). Mit jeder Änderung von TM[\(v\)] verdoppelt sich die Teilmenge, die \(v\) enthält, mindestens. Also kann sich TM[\(v\)] maximal \(\log N\)-mal ändern.
Daher ist \(G \le \sum _v (\log N) \le N \log N\).
Für Kruskals Algorithmus bedeutet dies, dass der Algorithmus in \(\O (m \log n)\) implementiert werden kann, denn das Sortieren der Kanten benötigt \(\O (m
\log m) = \O (m \log n)\),
es gibt höchstens \(m\) Finds (\(\O (m)\)) sowie \(n - 1\) Unions (\(\O (n \log
n)\)).
Ein einzelner Union-Schritt kann jedoch \(\O (n)\) kosten.
falls man garantieren will, dass jeder Union-Schritt \(\O (\log n)\) kostet:
Bislang waren die Kosten für Find bzw. Union \(\O (1)\) bzw. evtl. \(\O (n)\). Im
Folgenden wird gezeigt, wie man Find in \(\O (\log n)\) durchführt, dafür aber Union in \(\O (1)\).
Idee: Verwalte die Teilmengen als gewurzelte Bäume. Zu Beginn ist jede Teilmenge der Baum mit nur einem Element, der Wurzel. Eine Union-Operation auf zwei Teilmengen verschmelzt die entsprechenden Bäume, indem der kleinere Baum (der mit weniger Knoten) direkt unter die Wurzel des
größeren gehängt wird.
Kosten nun: Find(\(v\)) kostet \(\O (\text {Tiefe des Baums})\) (laufe im
Baum, der \(v\) enthält, von \(v\) zur Wurzel, gib diese als eindeutige ID für Teilmenge zurück). Union kostet \(\O (1)\).
Lemma: Die Tiefe der auftretenden Bäume ist höchstens \(\log n\).
Beweis: Betrachte das tiefste Blatt \(v\) eines Baums. Die Tiefe von \(v\) hat genau dann um \(1\) zugenommen, wenn der Baum von \(v\) unter die Wurzel eines anderen Baums gehängt wurde. Der andere
Baum ist in diesem Fall mindestens so groß gewesen wie der Baum, der \(v\) enthält. Daher kann der Baum von \(v\) höchstens \(\log n\)-mal unter einen anderen Baum gehängt werden.
Deswegen ist die Tiefe von \(v\) höchstens \(\log n\).
Optimierungsidee: Wenn Find(\(x\)) auf einen Knoten aufgerufen wird, so wird im Baum
von \(x\) von \(x\) aus nach oben bis zur Wurzel gelaufen. Wenn man die Knoten auf dem Weg zur Wurzel alle direkt unter die Wurzel hängt, so werden spätere Finds nach diesen Knoten billiger (\(\O (1)\)).