Graafin erillisten kaariparien laskeminen

Olkoon G=(V, E) yksinkertainen suuntaamaton, äärellinen graafi. Haluamme laskea kuinka monella tapaa E:stä voidaan valita kaksi kaarta e_1 ja e_2 siten että näiden päätepisteiden joukot \{v_{11}, v_{12}\} ja \{v_{21}, v_{22}\} ovat pistevieraat. (Suuntaamaton kaarihan itse asiassa on päätepisteidensä joukko, joten asian voisi ilmaista myös niin, että kaaret ovat pistevieraat.)

Halutunlaisten kaariparien laskeminen voidaan tehdä käymällä läpi kaikki kaaret ja summaamalla kullekin kaarelle sen pariksi sopivien kaarien lukumäärä. Tämä lukumäärä kaarelle e=\{v_1, v_2\} on |E|-\deg(v_1) - \deg(v_2) + 1.

Summan sieventämiseksi voidaan yhdistää saman lukumäärän antavat kaaret. Tätä varten muodostetaan graafista polynomi p_E(x) asettamalla jokaista kaarta e = \{v_1, v_2\} \in E vastaamaan termi x^{\deg(v_1)+\deg(v_2)-1}, jossa eksponentti siis laskee kaaren päätepisteisiin liittyvien kaarien lukumäärän. Nämä summataan yhteen. Esimerkki:

Merkitään p_E(x) = a_m x^m + \dots +a_1 x (huom. vakiotermi on 0, sillä jokaiseen kaareen liittyy ainakin yksi kaari nimittäin se itse). Nyt haluttu lukumäärä saadaan kätevästi:

\begin{aligned} \sum_{k=1}^{m} a_k (|E|-k). \end{aligned}

Ylläolevalle esimerkille saadaan (|E|=9)

\begin{aligned}   4(9-5) + 4(9-4) + 1(9-3) = 42. \end{aligned}

Huomiota

  • Tämä erillisten kaariparien lukumäärä on itse asiassa verkon ”2-paritusten” lukumäärä https://en.wikipedia.org/wiki/Matching_(graph_theory)
  • Olisi voitu määritellä myös polynomi q_E, asettamalla jokaiseen kaareen suoraan termi x^{|E|-\deg(v_1)-\deg(v_2)+1} eli siihen liittymättömien kaarien lukumäärä. Tällöin haluttu summa saa helposti ilmaistavan muodon: q_E' (1).
  • Ja koska yleensä vielä halutaan että derivaatta pitää ottaa nollassa, olisi voitu tehdä siirto x\mapsto x+1. Tällöin esimerkin polynomi olisi ollut \begin{aligned} q(x) = 4(x+1)^{9-5} + 4(x+1)^{9-4} + (x+1)^{9-3} = x^6 + 10 x^5 + 39 x^4 + 76 x^3 + 79 x^2 + 42 x + 9 \end{aligned} ja kuten huomataan, tämän derivaatta nollassa eli ensimmäisen asteen kerroin on 42.

Yksi vastaus artikkeliiin “Graafin erillisten kaariparien laskeminen

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