Alla oleva verkko on yksinkertainen ja yhtenäinen, eli mistään solmusta ei ole kaari samaan solmuun ja jokaisesta solmusta on polku jokaiseen toiseen solmuun.

Näytä esimerkkinä polku, joka ei ole yksinkertainen yksinkertainen polku sykli, joka ei ole yksinkertainen yksinkertainen sykli Eulerin polku Eulerin sykli Hamiltonin polku Hamiltonin sykli

Ensimmäinen verkko (tai saman verkon ensimmäinen yhtenäinen aliverkko) on puu ja toinen on kaksijakoinen. Molemmissa verkoissa punaiset kaaret muodostavat pariutuksen eikä näihin pariutuksiin voida lisätä yhtään kaarta siten, että ne pysyvät pariutuksena.

Verkon

naapurimatriisi on \[ A=\begin{bmatrix} 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1 & 0\end{bmatrix}.\] Nyt \[ A^2=\begin{bmatrix}2 & 1 & 1 & 1 & 1\\ 1 & 2 & 1 & 1 & 1\\ 1 & 1 & 4 & 1 & 1\\ 1 & 1 & 1 & 2 & 1\\ 1 & 1& 1 & 1 & 2\end{bmatrix} \rlap{\qquad\text{ja}} \] \[ A^3=\begin{bmatrix} 2 & 3 & 5 & 2 & 2\\3 & 2 & 5 & 2 & 2\\ 5& 5 & 4 & 5 & 5 \\ 2 & 2 & 5 &2 & 3\\ 2 & 2 &5 & 3 &2\end{bmatrix}, \] ja matriisin $A^3$ alkio $(A^3)(1,2)=3$ kertoo, että solmusta $1$ on kolme polkua solmuun $2$, joiden pituus on $3$ eli $[1,3,1,2]$, $[1,2,1,2]$ ja $[1,2,3,2]$.

voimme kirjoittaa A=[0,1,1,0,0; 1,0,1,0,0; 1,1,0,1,1; 0,0,1,0,1; 0,0,1,1,0] tai A=[0 1 1 0 0; 1 0 1 0 0; 1 1 0 1 1; 0 0 1 0 1; 0 0 1 1 0] ja matriisit $A^2$ sekä $A^3$ voimme laskea komennoilla A^2 ja A^3.

Ovatko alla olevat verkot isomorfiset?

Vastaus [+]

Molemmissa verkoissa on $4$ solmua, joilla on $3$ naapuria ja $2$ joilla on $2$ naapuria, mutta tästä emme voi päätellä etteivät verkot olisivat isomorfiset. Sensijaan vasemmanpuoleisessa verkossa ei ole yhtään sykliä, jonka pituus olisi $3$ mutta sellaisia on oikeanpuoleisessa verkossa. Tästä seuraa, etteivät verkot voi olla isomorfiset.

Entä alla olevat verkot?

Vastaus [+]

Molemmissa verkoissa on kaksi solmua, joilla on kolme naapuria, eli solmut $2$ ja $4$ ja solmut $c$ ja $e$. Jos verkot ovat isomorfiset niin isomorfismi voisi olla sellainen, että $\psi(2)=c$ ja $\psi(4)=e$ (tai päinvastoin). Koska solmu $1$ on sekä solmun $2$ ja solmun $4$ naapuri ja samoin solmu $d$ on sekä solmun $c$ että solmun $e$ naapuri täytyy olla $\psi(1)=d$. Jäljellä olevista solmuista solmu $3$ on solmun $2$ muttei solmun $4$ naapuri ja solmu $b$ on solmun $c$ muttei solmun $e$ naapuri, joten $\psi(3)=b$ jolloin täytyy olla $\psi(5)=a$. Näin määritelty funktio $\psi$ on isomorfismi ja verkot ovat isomorfiset.

• Jos vaadimme, että verkko on yksinkertainen niin ei löydy yhtään koska yksinkertaisessa verkossa, jossa on $3$ solmua on korkeintaan $3$ kaarta.
• Naapurimatriisissa on $3$ riviä ja saraketta ja koska verkko on suuntaamaton niin tämä matriisi on symmetrinen, eli tiedämme mikä se on jos tunnemme alkiot rivillä $i$ ja sarakkeella $j$ kun $1\leq i\leq j\leq 3$. Koska verkossa on $4$ kaarta niin $4$ näistä $6$:sta alkiosta ovat $1$ ja muut $0$. Näin ollen vaihtoehtojen lukumäärä on $\binom 64= 15$ mutta osa näistä verkoista ovat tietenkin isomorfisia keskenään.
• Koska kysymys on ei-isomorfisten verkkojen lukumäärästä, niin voimme tehdä kaikista vaihtoehdoista luettelon:
  Ensiksi toteamme kuten edellä että ainakin yksi solmu on oma naapurinsa joten meillä on vaihtoehdot että $1$, $2$ tai $3$ solmua ovat oma naapurinsa. Ensimmäisessä vaihtoehdossa eri solmujen välillä on oltava $3$ kaarta, toisessa $2$ kaarta ja viimeisessä $1$ kaari.
• Jos $1$ tai $3$ solmua ovat oma naapurinsa niin molemmissa tapauksissa meillä on vain yksi vaihtoehto ja ne ovat
• Jos $2$ solmua ovat oma naapurinsa niin meillä on kaksi ei-isomorfista verkkoa ja ne ovat:
• Näin ollen on olemassa $4$ ei-isomorfista verkkoa, joissa on $3$ solmua ja $4$ kaarta.

Entä miten tämä kysymys ratkaistaan Pólyan lauseen avulla?

Vastaus [+]

• Jos solmujen joukko on $\{1,2,3\}$ niin tämän joukon permutaatiot ovat $(1)$, $(1\; 2)$, $(1\; 3)$, $(2\; 3)$, $(1\;2\;3)$ ja $(1\;3\;2)$.
• Jotta voimme nähdä miten solmujen permutaatiot toimivat verkoilla esitämme verkot naapurimatriiseina missä emme välitä lävistäjän alapuolella olevista alkioista: $\begin{bmatrix} a & b &c \\ & d & e \\ & & f\end{bmatrix}$. Lisäksi näemme, että verkko jossa on $4$ kaarta on tällaisen matriisin ''väritys'' ykkösillä ja nollilla siten, että neljästä alkiosta tehdään $1$ ja kahdesta $0$.
• Vaatimus, että naapurit pysyvät naapureina antaa homomorfismin $\psi$ solmujen permutaatioista joukon $\{a,b,c,d,e,f\}$ permutaatioden ryhmään ja tämä homomorfismi on seuraava: \begin{align*} \psi((1))&=(a),\\ \psi((1\; 2))&= (a\;d)(c\;e),\\ \psi((1\;3))&= (a\;f)(b\; e)),\\ \psi((2\; 3)&=(d\; f)(b\; c),\\ \psi((1\;2\;3))&=(a\;d\;f)(b\;e\;c),\\ \psi((1\;3\;2))&=(a\;f\;d)(b\;c\;e). \end{align*}
• Tästä saamme sykli-indeksiksi \[ \frac 16\bigl(t_1^6+3\cdot t_1^2\cdot t_2^2+2\cdot t_3^2\bigr ). \]
• Pólyan lauseen mukaan termin $y^4n^2$ kerroin lauseekkeessa on ei-isomorfisten verkkojen, joissa on $3$ solmua ja $4$ kaarta, lukumäärä ja tämä kerroin on
   

• Tämä väite, että on mahdollista valita järjestys siten että minimi saavutetaan, pätee jos $\card{V}=1$.
• Oletamme seuraavaksi, että väite pätee verkon solmujen lukumäärä on korkeintaan $k$ ja olkoon $[V,E]$ verkko missä $\card{V}=k+1$ ja tämän verkon kromaattinen luku on $m\geq 1$.
• Jos $m=1$ niin $\card{E}=0$ ja ahne väritysalgoritmi käyttää aina myös vain yhden värin.
• Jos $m>1$ niin on olemassa solmujen väritys, joka käyttää $m$ väriä, eli funktio $\omega:V\to \{c_1,c_2, \ldots, c_m\}$ siten, että $\set{v\in V\mid \omega(v)=c_j}\neq \emptyset$ kaikilla $j=1,2\ldots,m$ (ja $\omega(v)\neq \omega(v')$ jos $\{v,v'\}\in E$). Nyt muodostamme aliverkon $[V^*,E^*]$ siten, että $V^*=\set{v\in V\mid \omega(v)\neq c_m}$ ja $E^*\!=\!\set{\!\{v,v'\}\!\in\! E\!\mid\! \omega(v)\neq c_m, \omega(v')\neq c_n}.$ Nyt $\card{V^*}\leq k$ ja ja verkon $[V^*,E^*]$ kromaattinen luku on korkeintaan $m-1$. Induktio-oletuksen nojalla voimme järjestää verkon $[V^*,E^*]$ solmut siten, että ahne väritysalgoritmi käyttää tähän verkkoon korkeintaan $m-1$ väriä. Joukon $V\setminus V^*$ solmut eivät ole toistensa naapureita joten jos lisäämme joukon $V^*$ solmujen jonon loppuun joukon $V\setminus V^*$ solmut mielivaltaisessa järjestyksessä niin silloin ahne väritysalgoritmi käyttää (korkeintaan, mutta kromaattisen luvun takia täsmälleen) $m$ väriä verkon $[V,E]$ solmujen vätittämiseen.
• Induktioperiaatteen nojalla väite, että on mahdollista valita solmujen järjestys siten että minimi saavutetaan ahneen väritysalgoritmin avulla pätee siis aina kun $\card{V}<\infty$.

Tehtävänä on määrittää jokin alla olevan verkon solmujen väritys:

Ahneen väritysalgoritmin mukaisesti toimimme seuraavalla tavalla: Järjestämme solmut ja värit jollain tavalla ja käymme läpi solmut järjestyksessä ja annamme jokaiselle solmulle ensimmäisen mahdollisen värin joka siis ei ole sama kuin sen jollekin naapurille jo annettu väri. Tässä tapauksessa värien järjestykseksi otetaan punainen, sininen, vihreä, keltainen.

Koska jokaisella solmulla tässä verkossa on kolme naapuria niin ahne väritysalgoritmi käyttää korkeintaan neljä väriä. Toisaalta, koska verkossa on kaareja, niin kromaattinen luku on vähintään $2$.

Riippuen valitusta solmujen järjestyksesestä ahne väritysalgoritmi käyttää joko $2$, $3$ tai $4$ väriä:
9, 10, ..., 15, 16, 1, 2, ..., 7, 8 1, 2, ..., 7, 8, 9, 10, ..., 15, 16 7, 9, 11, 14, 3, 12, 4, 6, 1, 2, 5, 7, ..., 15, 16

• Määrittelemme funktion $s$ kaavalla $ s(v)= \min\{\sum_{j=1}^k w(\{v_{j-1},v_j\}\mid [ v_0, v_1,\ldots,v_k]$ on polku solmusta $ v_0$ solmuun $ v_k=v\}$ kun $v\neq v_0$ ja $s(v_0)=0$.
• Valitsemme $V_0=\{v_0\}$, $V_{-1}=\emptyset$ ja määrittelemme testiarvot $t_0(v)=\infty$ kaikilla $v\in V\setminus \{v_0\}$. Jos $j\geq 0$ ja tunnemme funktion $s$ arvot joukon $V_j$ solmuissa ja testifunktion $t_j(v)=\min_{v'\in V_{j-1}}(s(v')+w(\{v',v\})$ arvot kaikissa muissa solmuissa niin meidän pitää laskea uusi testifunktio ja lisätä joukkoon $V_{j}$ seuraava piste.
• Koska määrittelemme $t_{j+1}(v)=\min_{v'\in V_j}(s(v')+w(\{v',v\})$, $v\in V\setminus V_j$, niin $t_{j+1}(v)=t_j(v)$ jos $v$ ei ole viimeksi lisätyn solmun $v_j$ naapuri joten meidän täytyy ainoastaan laskea $t_{j+1}(v)= \min\{t_j(v),s(v_j)+ w(\{v_j,v\})\}$ kun $v\in V\setminus V_j$ on $v_j$:n naapuri. Sitten valitsemme solmun $v_{j+1}$ joukosta $V\setminus V_j$ siten että $t_{j+1}(v_{j+1}) = \min_{v\in V\setminus V_j} t_{j+1}(v)$.
• Nyt joko $s(v_{j+1})= t_{j+1}(v_{j+1})$ ja induktioaskel toimii tai $s(v_{j+1}) < t_{j+1}(v_{j+1})$ ja meidän pitää osoittaa, että jälkimmäinen vaihtoehto johtaa ristiriitaan.
• Jos $s(v_{j+1}) < t_{j+1}(v_{j+1})$ niin on olemassa polku $[\tilde v_0,\tilde v_1, \ldots ,\tilde v_k]$ siten että $\tilde v_0=v_0$, $\tilde v_k=v_{j+1}$ ja $\sum_{i=1}^{k} w(\{\tilde v_{i-1},\tilde v_i\}) < t_{j+1}(v_{j+1})$.
• Silloin on olemassa suurin indeksi $i_0 < k$ siten, että $\tilde v_{i_0} \in V_j$ jolloin siis $\tilde v_{i_0+1}\in V\setminus V_j$ ja funktion $t_{j+1}$ määritelmästä ja oletuksesta $w(e)\geq 0$ seuraa, että joka on ristiriita. Näin ollen $s(v_{j+1}) = t_{j+1}(v_{j+1})$, voimme valita $V_{j+1}= V_j\cup\{v_{j+1}\}$ ja induktio toimii.

Huomaa, että tässä päättelyssä on oleellista, että $w(e)\geq 0$ kaikilla $e\in E$.

• Oletamme, että $G=[V,E]$ on yhtenäinen verkko, jossa jokaiselle kaarelle $e\in E$ on annettu paino $w(e)\geq 0$ (ja $w(\{v_j,v_k\})=\infty$ jos $\{v_j,v_k\}\notin E$) ja tehtävänä on löytää polku $[v_0,v_1,\ldots,v_k]$ kahden annetun solmun $v_*$ ja $v_{**}$ välillä siten, että $\sum_{j=1}^k w(\{v_{j-1},v_j\})$ on mahdollisimman pieni.
• Jos $\card{V}=n$ ja kaikkien solmujen välillä on kaari niin on olemassa $\sum_{j=2}^n\frac {(n-2)!}{(n-j)!} \geq (n-2)!$ eri vaihtoehtoa mutta yleensä vaihtoehtojen lukumäärä on kuitenkin paljon pienempi.
• Jos käytämme dynaamista optimointia ja olemme laskeneet optimiarvon $j$:hen solmuun niin meidän pitää laskea korkeintaan $n-j$ uutta testiarvoa käyttäen korkeintaan $(n-j)$ yhteenlaskua ja yhtä monta vertailua ja sitten valita pienin mikä vaatii korkeintaan $n-j-1$ vertailua.
• Näin ollen meidän pitää laskea korkeintaan $ \sum_{j=1}^{n-1}(n-j)= \tfrac 12 n(n-1)$ yhteenlaskua ja tehdä $\sum_{j=1}^{n-1}(n-j+n-j-1)= (n-1)^2$ vertailua. Yhteenlaskujen ja vertailujen lukumäärät ovat siis joukossa $O(n^2)$.

Jos $[V,E]$ on yksinkertainen ja yhtenäinen (suuntaamaton) verkko ja jokaiselle kaarelle $\{v_j,v_k\}$ on annettu paino $w(\{v_j,v_k\})$ (ja $w(\{v_j,v_k\})=\infty$ jos $\{v_j,v_k\}\notin E$) niin minimaalinen virittävä puu on verkko $[V,E_T]$ missä $E_T\subseteq E$ (eli aliverkko) joka on puu ja sellainen, että $\sum_{\{v_j,v_k\}\in E_T}w(\{v_j,v_k\})$ on mahdollisimman pieni.

Minimaalinen virittävä puu voidaan konstruoida esimerkiksi seuraavalla ahneella algoritmilla:

• Valitse $T_1=[\{v_1\},\emptyset]$ missä $v_1$ on $V$:n mielivaltainen alkio.
• Jos $T_{m} =[V_m,E_m]$ on valittu ja $V_m\neq V$ niin valitse $v_j\in V_{m}$ ja $v_k\in V\setminus V_m$ siten, että $w(\{v_j,v_k\})$ on mahdollisimman pieni jolloin $T_{m+1}=[V_{m}\cup\{v_k\},E_m\cup\{\{v_j,v_k\}\}]$, eli verkon $T_m$ solmuihin lisätään solmu $v_k$ ja kaareihin solmujen $v_j$ ja $v_k$ välinen kaari.

Miksi tämä algoritmi antaa optimin? [+]

• Olkoon $[V,E]$ yksinkertainen ja yhtenäinen verkko, jossa jokaiselle kaarelle $\{v_j,v_k\}$ on annettu paino $w(\{v_j,v_k\})$ ja $T_*=[V,E_*]$ on puu siten, että $w(T_*)=\sum_{e\in E_*} w(e)$ on mahdollisimman pieni.
• Primin ahneella algoritmilla konstruoimme puut $T_j=[V_j,E_j]$, $j=1,\ldots, n$ (missä $\card{V_1}=1$, $\card{V}=n$ ja $E_1=\emptyset$).
• Jos $E_*=E_n$ niin tämä algoritmi on optimaalinen ja jos $E_*\neq E_n$ niin on olemassa suurin luku $m$, $1\leq m < n$ siten, että $E_m\subseteq E_*$.
• Olkoon $\{x,y\}\in E_{m+1}\setminus E_m$ missä $x\in V_m$ ja $y\in V_{m+1}\setminus V_m$ jolloin siis $\{x,y\}\notin E_*$.
• On olemassa polku verkossa $T_*$ solmusta $x$ solmuun $y$ (koska $T_*$ on puu). Tähän polkuun sisältyy kaari $\{a,b\}$ siten, että $a\in V_m$ ja $b\in V\setminus V_{m}$. Jos nyt vaihdamme $T_*$:n kaaren $\{a,b\}$ kaareksi $\{x,y\}$ niin uusi verkko $T_{**}$ on myös puu.
• Lisäksi algoritmin mukainen $\{x,y\}$:n valinta takaa että $w(T_{**})\leq w(T_*)$. Tästä seuraa, että meillä on optimaalinen puu $T_{**}=[V,E_{**}]$ siten, että $E_{m+1}\subset E_{**}$. Koska voimme tarvittaessa toistaa edellistä päättelyä niin voimme osoittaa, että $T_n$ on verkon $[V,E]$ optimaalinen virittävä puu.

Jos $[V,E]$ on yksinkertainen ja yhtenäinen (suuntaamaton) verkko ja jokaiselle kaarelle $\{v_j,v_k\}$ on annettu paino $w(\{v_j,v_k\})$ (ja $w(\{v_j,v_k\})=\infty$ jos $\{v_j,v_k\}\notin E$) niin minimaalinen virittävä puu voidaan konstruoida myös seuraavalla ahneella algoritmilla:

• Valitse $E_1=\emptyset$.
• Jos $m\geq 1$ ja $[V,E_m]$ ei ole puu niin valitse $e\in E\setminus E_m$ siten, että $w(e)$ on mahdollisimman pieni ja verkko $[V,E_{m+1}]$, missä $E_{m+1}=E_m\cup \{e\}$, on metsä.

Miksi tämäkin algoritmi antaa optimin? [+]

• Olkoon $[V,E]$ on yksinkertainen ja yhtenäinen verkko, jossa jokaiselle kaarelle $\{v_j,v_k\}$ on annettu paino $w(\{v_j,v_k\})$ ja $T_*=[V,E_*]$ on puu siten, että $w(T_*)=\sum_{e\in E_*} w(e)$ on mahdollisimman pieni.
• Kruskalin ahneella algoritmilla konstruoimme metsät $F_j=[V,E_j]$, $j=1,\ldots, n$. Jos $F_n$ ei ole puu niin on olemassa solmut $a$ ja $b$ niin ettei niiden välillä ole polku verkossa $F_n$. Mutta verkossa $[V,E]$ on olemassa polku $[v_0,v_1,\ldots,v_k]$ missä $v_0=a$ ja $v_k=b$. Olkoon $j$ pienin luku, siten, että solmujen $v_{j-1}$ ja $v_j$ välillä ei ole polku verkossa $F_n$ eikä erityisesti $\{v_{j-1},v_j\}\in E_n$. (Jos sellainen pari ei löydy niin solmujen $a$ ja $b$ välillä on polku.) Nyt voimme lisätä kaaren $\{v_{j-1},v_j\}$ joukkoon $E_n$ siten että $[V,E_n\cup\{\{v_{j-1},v_j\}\}$ edelleen on metsä koska muuten solmujen $v_{j-1}$ ja $v_j$ välillä olisi jo kaari verkossa $F_n$. Näin ollen algoritmi antaa varmasti tulokseksi puun.
• Jos $E_*=E_{n}$ niin tämä algoritmi on optimaalinen ja jos $E_*\neq E_n$ niin on olemassa suurin luku $m$, $1\leq m < n$ siten, että $E_m\subseteq E_*$ jolloin siis $\{x,y\}\notin E_*$ jos $\{x,y\}\in E_{m+1}\setminus E_m$.
• Puussa $T_*$ on polku solmusta $x$ solmuun $y$. Koska $F_n$ on puu ja $\{x,y\}\notin E_*$ niin tähän polkuun sisältyy kaari $\{a,b\}$ siten, että $\{a,b\}\notin E_n$. Jos $E_{**}= (E_{*}\cup\{x,y\})\setminus \{a,b\}$ niin $[V,E_{**}]$ on myös puu ja koska $T_*$ on optimaalinen niin pätee $w(\{x,y\})\geq w(\{a,b\})$. Koska otimme kaaren $\{x,y\}$ mukaan joukkoon $E_{m+1}$, vaikka $\{a,b\}$ olisi ollut mahdollinen valinta koska $E_m\cup\{\{a,b\}\} \subseteq E_*$ josta seuraa, että myös $[V,E_m\cup\{\{a,b\}\}]$ on metsä, niin täytyy olla $w(\{x,y\})= w(\{a,b\})$ eli $T_{**}$ on myös optimaalinen puu ja $E_{m+1} \subseteq E_{**}$. Koska voimme tarvittaessa toistaa edellistä päättelyä niin voimme osoittaa, että $F_n$ on verkon $[V,E]$ minimaalinen virittävä puu.