Grfen nedan är enkel och sammanhängande, dvs. det finns inte någon båge från en nod till samma nod och från varje nod finns det en väg till varje annan nod.

Visa ett exempel på en väg, som inte är enkel enkel väg cykel, som inte är enkel enkel cykel Euler-väg Euler-cykel Hamilton-väg Hamilton-cykel

Den första grafen (eller den första sammanhängande delgrafen) är ett träd och den andra är bipartit. I båda graferna bildar de röda bågarna en matchning och det är inte möjligt att lägga till någon båge till dessa matchningar så att de förblir matchningar.

Grafens

grannmatris är \[ 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}.\] Nu är \[ 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{och}} \] \[ 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}. \] Elementet $(A^3)(1,2)=3$ i matrisen $A^3$ säger att det finns $3$ vägar från nod $1$ till nod $2$ med längd $3$ dvs. $[1,3,1,2]$, $[1,2,1,2]$ och $[1,2,3,2]$.

I matlab/octave [+]

kan vi skriva 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] eller 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] och matriserna $A^2$ och $A^3$ kan vi räkna med kommandona A^2 och A^3.

Är graferna nedan isomorfa?

Svar [+]

I båda graferna finns det $4$ noder som har tre grannar och $2$ som har $2$ grannar men med stöd av det kan vi inte dra slutsatsen att graferna sulle vara isomorfa. Däremot finns det inte i grafen till vänster någon cykel med längden $3$ men sådana finns i grafen till höger. Det betyder att graferna inte är isomorfa.

Och hur är det graferna nedan?

Svar [+]

I båda graferna finns $2$ noder som har $3$ grannar, dvs. noderna $2$ och $4$ och noderna $c$ och $e$. Om graferna är isomorfa så kan isomorfismen $\psi$ vara sådan att $\psi(2)=c$ och $\psi(4)=e$ (eller tvärtom). Eftersom nod $1$ är granne till både nod $2$ och nod $4$ och eftersom nod $d$ är granne både till nod $c$ och node $e$ så måste vi ha $\psi(1)=d$. Av de återstående noderna är nod $3$ granne till nod $2$ men inte till nod $4$ och nod $b$ är granne till nod $c$ men inte till nod $e$, så vi får $\psi(3)=b$ och då måste $\psi(5)=a$. Den här funktionen $\psi$ är en isomorfism och graferna är isomorfa.

• Om vi kräver att grafen är enkel finns det inte en enda för i en enkel graf med $3$ noder finns det högst $3$ bågar.
• I grafens grannmatris finns det $3$ rader och kolumner och eftersom grafen är icke-riktad så är matrisen symmetrisk vilket betyder att det räcker att känna till elementen på rad $i$ och kolumn $j$ då $1\leq i\leq j\leq 3$. Eftersom det finns $4$ bågar i grafen så är $4$ av de här $6$ elementen ovanför diagonalen $1$ och resten $0$. Det betyder att antalet alternativ är $\binom 64=15$ men en del av de här näten är förstås isomorfa.
• Eftersom vi skall bestämma antalet icke-isomorfa grafer kan vi göra en lista över alla alternativ:
  Först konstaterar vi som ovan att åtminstone en nod är sin egen granne så vi har alternativen att $1$, $2$ eller $3$ noder är sin egen granne. antalet bågar mellan olika noder blir då $3$, $2$ och $1$ för respektive fall.
• Om $1$ eller $3$ noder är sin egen granne så har vi bara ett alternativ och de är
• Om $2$ noder är sin egen granne så får vi två icke-isomorfa grafer och de är:
• Således finns det $4$ icke-isomorfa grafer med $3$ noder och $4$ bågar.

Hur löser man det här problemet med Pólyas teorem?

Svar [+]

• Om nodmängden är $\{1,2,3\}$ så permutationerna av noderna $(1)$, $(1\; 2)$, $(1\; 3)$, $(2\; 3)$, $(1\;2\;3)$ och $(1\;3\;2)$.
• För att se hur permutationerna verkar på graferna beskriver vi graferna med hjälp av grannmatriser i vilka vi inte bryr oss om elementen under diagonalen: $\begin{bmatrix} a & b &c \\ & d & e \\ & & f\end{bmatrix}$. Dessutom ser vi att en graf med $3$ noder och $4$ bågar är en "färgning" av en matris av detta slag med ettor och nollor så att $4$ element blir $14 och $2$ blir $0$.
• Kravet att grannar förblir grannar ger en homomorfism från permutationerna av noderna till permutationer av mängden $\{a,b,c,d,e,f\}$ och den här homomorfismen är följande: \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*}
• Av detta får vi cykelindexet \[ \frac 16\bigl(t_1^6+3\cdot t_1^2\cdot t_2^2+2\cdot t_3^2\bigr ). \]
• Enligt Pólyas teorem är koefficienten för termen $e^4n^2$ i polynomet antalet icke-isomorfa grafer med $3$ noder och $4$ bågar och den här koefficienten är
   

   

Beroende på i vilken ordning kan den här algoritmen använda ett antal färger som är större än det kromatiska talet som är minimiantalet. Men det är alltid möjligt att välja ordningen så att minimiantalet uppnås. Varför? [+]

• Påståendet att minimiantalet kan uppnås gäller (förstås) när $\card{V}=1$.
• Vi antar nu att påståendet gäller då antalet noder i grafen är högst $k$ och vi antar att $[V,E]$ är en graf med $\card{V}=k+1$ och kromatiskt tal $m\geq 1$.
• Om $m=1$ så är $\card{E}=0$ och den giriga algoritmen använder alltid också bara en färg.
• Om $m>1$ så finns det en nodfärgning som använder $m$ färger, dvs. en funktion $\omega:V\to \{c_1,c_2, \ldots, c_m\}$ så att $\set{v\in V\mid \omega(v)=c_j}\neq \emptyset$ för alla $j=1,2\ldots,m$ (och $\omega(v)\neq \omega(v')$ när $\{v,v'\}\in E$). Nu bildar vi delgrafen $[V^*,E^*]$ så att $V^*=\set{v\in V\mid \omega(v)\neq c_m}$ och $E^*\!=\!\set{\!\{v,v'\}\!\in\! E\!\mid\! \omega(v)\neq c_m, \omega(v')\neq c_n}.$ Nu är $\card{V^*}\leq k$ och grafens $[V^*,E^*]$ kromatiska tal är högst $m-1$. Enligt induktionsantagandet kan vi ordna noderna i grafen $[V^*,E^*]$ så att den giriga färgningsalgoritmen använder högst $m-1$ färger. Noderna i mängden $V\setminus V^*$ är inte grannar med varandra så om vi lägger noderna i $V\setminus V^*$ efter noderna i $V^*$ i en godtycklig ordning så kommer den giriga algoritmen att använda (högst men på grund av det kromatiska talet, precis) $m$ färger för nodfärgningen av grafen $[V,E]$.
• Enligt induktionsprincipen har vi nu visat att det alltid när $\card{V}<\infty$ är möjligt att ordna noderna så att den giriga färgningsalgoritmen använder minimiantalet färger.

Vi skall bestämma någon nodfärgning av av grafen nedan:

I enlighet med den giriga färgningsalgoritmen ordnar vi noderna och färgerna på något sätt och går genom noderna i ordning och ger varje nod den första möjliga färgen som alltså inte är samma som någon granne till noden redan har. I det här fallet låter vi färgernas ordning vara . röd blå, grön, gul.

Eftersom varje nod i den här grafen har $3$ grannar så använder den giriga färgningsalgoritmen högst $4$ färger. Eftersom det finns bågar så är det kromatiska talet minsta $2$.

Beroende på den valda ordningen av noderna använder den giriga f'rgningsalgoritmen $2$, $3$ eller $4$ färger:
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

   

• Vi defininierar funktionen $s$ med formeln $s(v)= \min\{\sum_{j=1}^k w(\{v_{j-1},v_j\}\mid [ v_0, v_1,\ldots,v_k]$ är en stig från noden $v_0$ till noden n $ v_k=v\}$ när $v\neq v_0$ och vi har $s(v_0)=0$.
• Vi väljer $V_0=\{v_0\}$, $V_{-1}=\emptyset$ och definierar testvärden $t_0(v)=\infty$ för alla $v\in V\setminus \{v_0\}$. Om $j\geq 0$ och vi känner till funktionens $s$ värden för noder i mängden $V_j$ och testfunktionens $t_j(v)=\min_{v'\in V_{j-1}}(s(v')+w(\{v',v\})$ värden i alla andra noder så skall via beräkna en ny testfuntkion och lägga till nästa nod till mängden $V_{j}$.
• Eftersom vi definierar $t_{j+1}(v)=\min_{v'\in V_j}(s(v')+w(\{v',v\})$, $v\in V\setminus V_j$, så är $t_{j+1}(v)=t_j(v)$ om $v$ inte är granne till den nod $v_j$ för vilken funktionens $s$ värde senast bestämts så vi skall bara beräkna $t_{j+1}(v)=\min\{t_j(v),s(v_j)+ w(\{v_j,v\})\}$ då $v\in V\setminus V_j$ är granne till $v_j$. Sedan väljer vi noden $v_{j+1}$ ur mängden $V\setminus V_j$ så att $t_{j+1}(v_{j+1}) = \min_{v\in V\setminus V_j} t_{j+1}(v)$.
• Nu gäller antingen $s(v_{j+1})= t_{j+1}(v_{j+1})$ och och induktionssteget fungerar elelr så är $s(v_{j+1}) < t_{j+1}(v_{j+1})$ och vi skall visa att detta senare alternativ leder till en motsägelse.
• Om $s(v_{j+1}) < t_{j+1}(v_{j+1})$ så finns det en väg $[\tilde v_0,\tilde v_1, \ldots ,\tilde v_k]$ så att $\tilde v_0=v_0$, $\tilde v_k=v_{j+1}$ och $\sum_{i=1}^{k} w(\{\tilde v_{i-1},\tilde v_i\}) < t_{j+1}(v_{j+1})$.
• Då finns det ett största index $i_0 < k$ så att $\tilde v_{i_0} \in V_j$ vilket betyder att $\tilde v_{i_0+1}\in V\setminus V_j$ och av definitionen av funktionen $t_{j+1}$ och av antagandet att $w(e)\geq 0$ följer att vilket är en motsägelse. Det här betyder att $s(v_{j+1}) = t_{j+1}(v_{j+1})$, vi kan välja $V_{j+1}= V_j\cup\{v_{j+1}\}$ och induktionen fungerar.

Observera att det är väsenmtligt för det här resonemanget att $w(e)\geq 0$ för alla $e\in E$.

• Vi antar att $G=[V,E]$ är en sammanhängande graf i vilken varje båge $e\in E$ givits en vikt $w(e)\geq 0$ (och $w(\{v_j,v_k\})=\infty$ om $\{v_j,v_k\}\notin E$) och uppgiften är att bestämma en väg $[v_0,v_1,\ldots,v_k]$ kmellan två givna noder $v_*$ och $v_{**}$ så att $\sum_{j=1}^k w(\{v_{j-1},v_j\})$ är så liten som möjligt.
• Om $\card{V}=n$ och och det finns en båge mellan alla noder så finns det $\sum_{j=2}^n\frac {(n-2)!}{(n-j)!} \geq (n-2)!$ olika alternativ för vägen men vanligtvis är antalet alternativ mycket mindre.
• Om vi använder dynamisk optimering och vi har beräknat optimivärdet till $j$ noder så skall vi räkna ut nya testvärden för högst $n-j$ noder och då använder vi högst $n-j$ additioner och lika många jämförelser och sedan skall vi välja det minsta med $n-j-1$ jämförelser.
• Det här betyder att att vi skall räkna högst $\sum_{j=1}^{n-1}(n-j)= \tfrac 12 n(n-1)$ additioner och göra högst \sum_{j=1}^{n-1}(n-j+n-j-1)= (n-1)^2$ jämförelser. Antalet additioner och jämförelser hör alltså till mängden $O(n^2)$.

   

Om $G=[V,E]$ är en enkel och sammanhängande (icke-riktad) graf och varje båge $\{v_j,v_k\}$ har getts en vikt $w(\{v_j,v_k\})$ (och $w(\{v_j,v_k\})=\infty$ när $\{v_j,v_k\}\notin E$) så är ett minimalt uppspännande träd för $G$ en delgraf $[V,E_T]$ som är ett träd och sådan att $\sum_{\{v_j,v_k\}\in E_T}w(\{v_j,v_k\})$ är minsta möjliga.

Ett minimalt uppspännande träd kan konstrueras tex. med följande giriga algoritm:

• Välj $T_1=[\{v_1\},\emptyset]$ där $v_1$ är en godtycklig nod i $V$.
• Om $T_{m} =[V_m,E_m]$ har valts och $V_m\neq V$ så att $w(\{v_j,v_k\})$ är minsta möjliga så är $T_{m+1}=[V_{m}\cup\{v_k\},E_m\cup\{\{v_j,v_k\}\}]$, dvs. trädets $ T_m$ noder utökas med $v_k$ och bågar med bågen mellan $v_j$ och $v_k$.

Varför ger den här algoritmen ett optimalt resultat? [+]

• Låt $[V,E]$ vara en enkel och sammanhängande graf där varje båge $\{v_j,v_k\}$ har getts en vikt $w(\{v_j,v_k\})$ och antag att $T_*=[V,E_*]$ är ett träd så att $w(T_*)=\sum_{e\in E_*} w(e)$ är minsta möjliga.
• Med Prims giriga algoritm konstruerar vid träden $T_j=[V_j,E_j]$, $j=1,\ldots, n$ (där $\card{V_1}=1$, $\card{V}=n$ och $E_1=\emptyset$).
• Om $E_*=E_n$ så fungerar algoritmen som den skall och om och om $E_*\neq E_n$ så finns det ett största tal $m$, $1\leq m < n$ så att $E_m\subseteq E_*$.
där
• Antag att $\{x,y\}\in E_{m+1}\setminus E_m$ där $x\in V_m$ och $y\in V_{m+1}\setminus V_m$ och alltså $\{x,y\}\notin E_*$.
• Det finns en väg i grafen $T_*$ fråm noden $x$ till noden $y$ eftersom $T_*$ är ett träd. I den här vägen ingår en båge $\{a,b\}$ så att $a\in V_m$ och $b\in V\setminus V_{m}$. Om vi nu ersätter bågen $\{a,b\}$ i $T_*$ med bågen $\{x,y\}$ så är den nya grafen $T_{**}$ ocksåp ett träd.
• Algoritmens val av $\{x,y\}$ garanterar att $w(T_{**})\leq w(T_*)$. Det här betyder att vi har ett optimalt träd $T_{**}=[V,E_{**}]$ så att $E_{m+1}\subset E_{**}$. Eftersom vi kan upprepa den här konstruktionen om det behövs så har vi visat att $T_n$ är ett minimalt uppspännande träd för grafen $[V,E]$.

Om $G=[V,E]$ är en enkel och sammanhängande (icke-riktad) graf och varje båge $\{v_j,v_k\}$ har getts en vikt $w(\{v_j,v_k\})$ (och $w(\{v_j,v_k\})=\infty$ när $\{v_j,v_k\}\notin E$) så kan ett minimalt uppspännande träd också konstrueras med följande giriga lagoritm:

• Välj $E_1=\emptyset$.
• Om $m\geq 1$ och $[V,E_m]$ inte är ett trräd så välj $e\in E\setminus E_m$ så att $w(e)$ är minsta möjliga och så att grafen $[V,E_{m+1}]$, där $E_{m+1}=E_m\cup \{e\}$, är en skog.

Varför ger också den här algoritmen ett optimalt resultat? [+]

• Låt $[V,E]$ vara en enkel och sammanhängande graf där varje båge $\{v_j,v_k\}$ har getts en vikt $w(\{v_j,v_k\})$ och antag att $T_*=[V,E_*]$ är ett träd så att $w(T_*)=\sum_{e\in E_*} w(e)$ är minsta möjliga.
• Med Kruskals giriga algoritm konstruerar vi skogarna $F_j=[V,E_j]$, $j=1,\ldots, n$. Om $F_n$ inte är ett träd så finns det noder $a$ och $b$ ågon väg mellan dem i grafen $F_n$. Men i grafen $[V,E]$ finns det en väg $[v_0,v_1,\ldots,v_k]$ där $v_0=a$ och $v_k=b$. Låt $j$ vara minsta möjliga index så att det inte finns en väg mellan noderna $v_{j-1}$ och $v_j$ i grafen $F_n$ vilket i synnerhet betyder att $\{v_{j-1},v_j\}\notin E_n$. (Om ett sådant. Nu kan vi utöka mängden $E_n$ med bågen $\{v_{j-1},v_j\}$ så att $[V,E_n\cup\{\{v_{j-1},v_j\}\}$ fortfarande är en skog för annars skulle det redan finnas en väg mellan noderna $v_{j-1}$ och $v_j$ i grafen $F_n$. Dethär betyder att algoritmen garanterat ger som svar ett träd när den inte längre kan utöka mängden bågar i skogen.
• Om $E_*=E_{n}$ så ger den här algoritmen ett optimalt resultat och om $E_*\neq E_n$ så finns det ett största tal $m$, $1\leq m < n$ så att $E_m\subseteq E_*$ och därför gäller $\{x,y\}\notin E_*$ om $\{x,y\}\in E_{m+1}\setminus E_m$.
• I trädet $T_*$ finns en väg från noden $x$ till noden $y$. Eftersom $F_n$ är ett träd och $\{x,y\}\notin E_*$ så finns på den här vägen en båge $\{a,b\}$ så att $\{a,b\}\notin E_n$. Om $E_{**}= (E_{*}\cup\{x,y\})\setminus \{a,b\}$ så är också $[V,E_{**}]$ ett träd och eftersom $T_*$ är optimalt så gäller $w(\{x,y\})\geq w(\{a,b\})$. Eftersom vi tog med bågen $\{x,y\}$ i mängden $E_{m+1}$, fastän $\{a,b\}$ också kunde ha varit ett möjligt val eftersom $E_m\cup\{\{a,b\}\} \subseteq E_*$ av vilket följer att också $[V,E_m\cup\{\{a,b\}\}]$ är en skog, så måste vi ha $w(\{x,y\})= w(\{a,b\})$ dvs. $T_{**}$ är också ett optimalt träd och $E_{m+1} \subseteq E_{**}$. Eftersom vi kan upprepa det här resonemanget om det behövs så har vi visat att $F_n$ är ett minimalt uppsännande träd för grafen $[V,E]$.