Graafin naapuruus-polynomeja

Olkoon G=(V, E) yksinkertainen, suuntaamaton, äärellinen graafi.

Määritellään G:n ensimmäinen naapuruus-polynomi

\begin{aligned} p_1(x) = \sum_{v\in V} x^{\deg(v)} \end{aligned}.

Termin x^k kerroin kertoo kuinka monta k-asteista solmua graafissa on eli kuinka monella on (tasan) k naapuria. Esimerkki:

Polynomista p_1(x) = \sum_{k=0}^{m} a_k x^k voidaan laskea graafin kaarien määrä laskemalla \frac{1}{2}  p_1 '(1)

\frac{1}{2} \begin{aligned}  \sum_{k=1}^m k a_k\end{aligned}

Tämähän on tuttu kaava, että solmujen asteiden summa on kaksi kertaa kaarien määrä. Polynomi kuitenkin ryhmittelee solmut asteen mukaan, joten se on kätevä laskuissa. Esimerkin graafissa lasku on (4 + 3\times 3 + 2 \times 3 + 1)/2 = 10.

Mielenkiintoisempi ja enemmän graafista tietoa antava polynomi on toinen naapuruus-polynomi p_2(y_1, y_2, \dots). Muuttujia y_j on mielivaltaisen monta, mutta kuitenkin tietyssä polynomissa aina vain äärellisen monta. Se määritellään seuraavasti.

Tutkitaan jokaiselle solmulle v sen naapureita w_1, w_2, \dots , w_t ja muodostetaan termi \begin{aligned} \prod_{j=1}^{t} y_{\deg(w_j)} \end{aligned}. Nämä summataan yhteen. Esimerkki:

Keltaisella korostetut solmut tuottavat saman termin. Niillä sattuu tässä esimerkissä olemaan täysin samat naapurit, mutta samanlaiset termit voi syntyä muutenkin, riittää että naapuruston ”tyyppi” eli asteiden suurusjärjestykseen järjestetty vektori on sama.

Polynomin p_2 avulla voidaan laskea esimerkiksi kolmio-vapaan (ei sisällä 3-sykliä) graafin 4-ketjujen lukumäärä seuraavasti: Olkoon 4-ketju (x_1, x_2, x_3, x_4). Kiinnitetään x_2. Nyt x_1 ja x_3 ovat jotkin sen naapurit. Annetaan siis niiden juosta kaikkien naapuri-kaksikkojen (a_1, a_2), a_1 \neq a_2 läpi. Lopuksi x_4 täytyy olla jokin x_3:n naapuri. Tässä graafin kolmio-vapaus tulee tarpeeseen: meidän täytyy tietää vain se kuinka monta naapuria x_3:lla on x_1:n lisäksi. Solmu x_1 ei voi olla x_3:n naapuri sillä muuten muodostuisi kolmio. Seuraava JavaScript funktio suorittaa tämän laskun, kun sille antaa polynomin p_2 objektina, johon termin \prod_{j=1}^t y_{i_j} kerroin on koodattu avaimen ”i_1, i_2, \dots , i_t” arvoksi (huom. jokainen i_j on siis avaimessa niin monta kertaa kuin se termissä esiintyy eli ”potenssit kirjoitetaan tuloina”).

/** @param p: The second neighbor polynomial of the graph */
function count4PathsInTriangleFreeGraph(p) {
    let s = 0;
    for (let key in p) {
        let a = key.split(",").map(x=>+x);
        for (let k1=0; k1<a.length; k1++) {
            for (let k2=0; k2<a.length; k2++) {
                if (k2===k1) continue;
                //x4 can be any nbr of x3 except x2 (hence -1)
                //x1 can't be a neighbor of x3, since no triangles
                s += p[key]*(a[k2]-1);
            }
        }
    }
    return s;
}

Edellisen esimerkin graafi on kolmio-vapaa, joten funktiota voi käyttää. Parametriksi annettava objekti on:

{"4":1, "2,3,4":2, "3,3":1, "2,3,3":1, "2,3":1, "2,4":1, "1,2,3,3":1}

Koodi antaa tulokseksi 60. Näin pienessä esimerkissä tämän funktion hyödyllisyys ei ehkä tule ilmi; voisimmehan käydä kaikki solmu-nelikot läpi ja tarkastaa kuinka moni niistä on 4-ketju. Sen hyödyt nähdään suuremmille graafeille, joille polynomi p_2 on laskettavissa helposti ja sen termien lukumäärä säilyy pienenä (eli niissä on jokin sellainen säännönmukaisuus joka helpottaa laskemista). Esimerkki:

Ratsun graafi 8×8-laudalla. Säännönmukaisuuksia merkitty väreillä. Tässä esimerkissä sitä ei vielä itse asiassa näe, mutta kun laudan koko kasvaa yli 8, keskelle syntyy neliö, jonka kaikki solmut ovat p_2:n mielessä samanlaisia: niillä on 8 naapuria, joilla jokaisella on 8 naapuria. Suurilla n termi y_8^8 tulee siis hallitsevaksi: sen kerroin on (n-8)^2.

Huomioita

  • Jos polynomissa p_2 asettaa y_j = x kaikilla j, niin saadaan polynomi p_1. Tämä johtuu siitä, että p_2 jaottelee solmut tarkemmin niiden naapureiden asteiden mukaan, kun p_1 vain solmun oman asteen mukaan. Jokainen solmu v tuo p_2:een astetta \deg(v) oleven y-termin, joten asetettassa y_j = x, \forall j, tämä redusoituu x^{\deg(v)}:ksi, kuten p_1:ssä.
  • Kun edellä puhuttiin 4-ketjuista, tarkoitettiin vain solmu-nelikkoja, joiden välillä on kaaret ensimmäisestä toiseen, toisesta kolmanteen ja kolmannesta neljänteen. Muista kaarista ei välitetä (esim. vaikka neljännestä olisi takaisin ensimmäiseen). Ei siis puhuta indusoiduista ketjuista.
  • Kolmio-vapaus on oleellinen vaatimus 4-ketjulaskelmassa. Esimerkiksi 3-solmuiselle täydelle graafille K_3, joka on itse kolmio, saadaan p_2(y) = 3y_2^2, joka antaisi tulokseksi 4. Mutta tietenkään siellä ei voi olla yhtään 4-ketjua, kun solmuja on vain 3.
  • Funktiota count4PathsInTriangleFreeGraph voi yksinkertaistaa jättämällä k1:n iteraation pois ja vain kertomalla sisimmässä silmukassa lisättävän lukumäärän (a.length-1):llä.

Tehtäviä

  1. Laske graafista sellaisten solmu-kolmikkojen (v_1, v_2, v_3) lukumäärä, joille v_1 ja v_2 ovat rinnakkaiset (eli niitä yhdistää kaari) sekä v_1 ja v_3 ovat rinnakkaiset.
  2. Entäpä vastaavasti nelikot, jossa kaikki v_j, j>1 ovat rinnakkaisia v_1:lle?

Yksi vastaus artikkeliiin “Graafin naapuruus-polynomeja

Vastaa

Täytä tietosi alle tai klikkaa kuvaketta kirjautuaksesi sisään:

WordPress.com-logo

Olet kommentoimassa WordPress.com -tilin nimissä. Log Out /  Muuta )

Google photo

Olet kommentoimassa Google -tilin nimissä. Log Out /  Muuta )

Twitter-kuva

Olet kommentoimassa Twitter -tilin nimissä. Log Out /  Muuta )

Facebook-kuva

Olet kommentoimassa Facebook -tilin nimissä. Log Out /  Muuta )

Muodostetaan yhteyttä palveluun %s