Degeneraatio (graafiteoria)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. lokakuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

K -degeneroitu graafi on suuntaamaton graafi , jossa jokaisella aligraafilla on pisteitä, joiden aste on enintään k . Graafin rappeutuminen on k : n pienin arvo,jolle graafi on k -degeneroitunut. Kuvaajan rappeutuminen heijastaa sitä, kuinka harva kaavioja (vakiokerroin asti) heijastaa muita harveuden mittareita, kuten kaavion puuisuutta .

Degeneraatio tunnetaan myös k - ytimen numeroina [1] [2] [3] , leveydenä [4] ja linkkinä [5] , ja se on olennaisesti sama kuin väritysluku [6] tai Szekeres-luku − Wilf . k -Degeneroituneita graafeja kutsutaan myös k -induktiivisiksi graafiksi [7] . Graafin degeneraatio voidaan laskea lineaarisessa ajassa käyttämällä algoritmia, joka poistaa peräkkäin pisteitä minimiasteella [8] . Kaikkien alle k -asteisten kärkien poistamisen jälkeen jäljellä olevaa yhdistettyä komponenttia kutsutaan graafin k - ytimeksi ja graafin degeneraatio on yhtä suuri kuin suurin k:n arvo, jolle on k -ydin .

Esimerkkejä

Jokaisella metsällä on joko eristetty kärki (ei vierekkäisiä reunoja) tai lehtipiste (joka osuu täsmälleen yhteen reunaan), joten metsät ja puut ovat 1-degeneroituneita graafisia.

Minkä tahansa äärellisen tasograafin kärkipiste on aste viisi tai vähemmän, joten mikä tahansa tasograafi on 5-degeneroitunut ja minkä tahansa tasograafin degeneraatio ei ylitä viittä. Vastaavasti minkään ulkotason graafin degeneraatio ei ylitä kahta [9] ja Apolloniuksen graafien degeneraatio on yhtä suuri kuin kolme.

Barabasi-Albert-mallissa satunnaisten skaalattomien verkkojen generoimiseksi [10] on luku m parametrina siten, että jokainen graafiin lisätty kärki on yhdistetty reunoilla aiemmin lisättyyn m pisteeseen . Tästä seuraa, että minkä tahansa tällä tavalla saadun verkon aligraafin kärkiaste on vähintään m (tämä on graafiin viimeksi lisätyn kärjen aste), joten Barabasi-Albert-verkot ovat automaattisesti m -degeneroituneita.

Jokaisella k -säännöllisellä graafilla on täsmälleen k degeneraatio . Tarkemmin sanottuna graafin degeneraatio on yhtä suuri kuin kärjen suurin aste, jos ja vain jos ainakin yksi graafin yhdistetyistä komponenteista on säännöllinen ja sillä on itse graafin aste. Kaikkien muiden graafien degeneraatio on tiukasti pienempi kuin graafin kärkien suurin aste [11]

Määritelmät

Erdős ja Hajnal [6] esittelivät graafin G väritysluvun suurimmaksi κ:ksi, jolle on olemassa graafin G kärkien järjestys siten, että jokaisella kärjellä on vähemmän kuin κ naapureita, jotka edeltävät kärkeä järjestyksessä. Tämä numero tulee erottaa graafin G kromaattisesta numerosta, joka on värien vähimmäismäärä, joka vaaditaan huippupisteen värjäykseen siten, että kahdella vierekkäisellä kärjellä ei ole samaa väriä. Väritysnumeron määrittelevä järjestys antaa järjestyksen, jossa graafin G kärjet värjätään värimäärää vastaavalla määrällä värejä, mutta yleensä kromaattinen luku voi olla tätä lukua pienempi.

Lick and White [9] määritteli graafin G rappeutumisen pienimmäksi luvuksi k , jolle mikä tahansa G :n generoitu osagraafi sisältää kärjen, jossa on k tai vähemmän naapureita. Määritelmä ei muutu, jos generoitujen osagraafien sijasta otetaan mielivaltaiset osagraafit, koska generoimattomalla osagraafilla voi olla kärkiasteita, jotka eivät ylitä samalla pistejoukolla generoidun aligraafin kärkiasteita.

Kaksi käsitettä, väritysluku ja rappeutuminen, ovat samanarvoisia – missä tahansa äärellisessä graafissa degeneraatio on yksi vähemmän kuin väritysluku [12] [13] . Jos graafissa on järjestys, jonka väritysluku on κ, niin kussakin osagraafissa H H : lle kuuluvalla ja järjestyksen viimeisellä kärjellä on korkeintaan κ − 1 naapuria H :ssä . Toisessa suunnassa, jos G on k -degeneroitunut, niin järjestys väritysluvulla k  + 1 saadaan etsimällä peräkkäin kärki v , jolla on enintään k naapuria, poistamalla v graafista, järjestämällä loput kärjet ja lisäämällä v tilauksen loppuun asti.

Kolmas vastaava määritelmä graafin G k -degeneraatiolle (tai sille, että värjäysluku ei ylitä k  + 1:tä) on, että graafi on k -degeneroitunut silloin ja vain jos G :n reunat voidaan suunnata muodostamaan suunnattu asyklinen graafi . ulkoasteen kanssa enintään k [14 ] . Tällainen orientaatio voidaan saada suuntaamalla kukin reuna järjestyksen mukaisesti reunan kahdesta kärjestä aikaisempaan suuntaan. Toisessa suunnassa, kun on annettu orientaatio lähtöpuolisaatolla k , järjestys väritysluvulla k  + 1 voidaan saada suunnatun asyklisen graafin topologisena järjestyksenä .

k -Ytimet

G :n k -ydin on G :n maksimaalinen yhdistetty aligraafi, jossa kaikkien kärkien aste on vähintään k . Vastaavasti se on yksi aligraafin G yhdistetyistä komponenteista, joka muodostuu poistamalla peräkkäin kaikki kärjet, joiden aste on pienempi kuin k . Jos on ei-tyhjä k - ydin, on selvää, että G :llä on degeneraatio vähintään k ja G :n degeneraatio on suurin luku k , jolle G : llä on k - ydin.

Huipulla on ydinvoima , jos kärki kuuluu -ytimeen , mutta ei kuulu -ytimeen .

K -ytimen käsite otettiin käyttöön tutkimaan ryhmittelyä sosiaalisissa verkostoissa [15] ja kuvaamaan satunnaisten kaavioiden käyttöä [16] [17] [18] . Konsepti on myös siirtynyt bioinformatiikkaan [1] [2] ja verkkovisualisointiin [19] [20] .

Algoritmit

Kuten Matula ja Beck [8] kuvaavat , voidaan lineaarisessa ajassa löytää äärellisessä graafissa G järjestyspiste, joka optimoi järjestysväritysluvun käyttämällä konttijonoa pienimmän asteen pisteiden etsimiseen ja poistamiseen. Degeneraatio on sitten minkä tahansa kärjen suurin aste sen poistamishetkellä.

Tarkemmin sanottuna algoritmi toimii seuraavasti:

Algoritmin lopussa k sisältää graafin G degeneraation ja lista L sisältää kärjet väritysluvun optimaalisessa järjestyksessä. Graafissa G i -ytimet ovat listan L alilistoja, jotka koostuvat pisteistä, jotka on lisätty L: ään sen jälkeen, kun k saa ensimmäistä kertaa arvon, joka on suurempi tai yhtä suuri kuin i .

Muuttujien L , d v , D ja k alustus voidaan tehdä helposti lineaarisessa ajassa. Seuraavan poistetun kärjen v löytäminen ja kärjen v naapurit sisältävien D :n alkioiden uudelleenlaskenta vie aikaa, joka on verrannollinen d v :n arvoon tässä vaiheessa, mutta tällaisten arvojen summa on yhtä suuri kuin graafin reunojen lukumäärä, joten kokonaisaika on lineaarinen.

Suhde muihin kaavioparametreihin

Jos graafi G on suunnattu asykliseen k :n ulkopuolella , niin sen reunat voidaan jakaa k metsään valitsemalla yksi metsä kullekin kärkipisteen lähtevälle kaarelle. Siten graafin G puuisuus ei ylitä sen degeneraatiota. Päinvastaisessa suunnassa graafissa, jossa on n kärkeä ja joka voidaan jakaa k metsään, on korkeintaan k ( n  − 1) reunaa, ja siksi sillä on pisteitä, joiden aste on enintään 2k − 1. Eli degeneraatio on puolet kaavio puu. On myös mahdollista laskea polynomiajassa graafin suuntaus, joka minimoi puolittumisasteen ilman, että kuvaajan on oltava asyklinen. Tässä suunnassa olevan graafin reunat voidaan jakaa samalla tavalla k pseudometsään . Sitä vastoin mikä tahansa graafin reunojen jakaminen k pseudometsään johtaa orientaatioon, jolla on suurin ulkoaste k (valitsemalla orientaatio, jonka ulkoaste on 1 kullekin näennäismetsälle), joten tällaisen orientaation pienin ulkoaste on näennäispuuisuus , joka taas , ei ylitä degeneraatiota [14 ] [21] [22] [23] [24] . Paksuus on myös (vakiokertoimeen asti) verrannollinen puumaisuuteen, joten sama pätee rappeutumiseen [25] .

K -degeneroituneen graafin kromaattinen luku on korkeintaan k  + 1. Tämä voidaan osoittaa yksinkertaisella induktiolla pisteiden lukumäärästä, aivan kuten tasograafien kuuden värin lauseen todistuksessa. Koska kromaattinen luku on yläraja suurimman klikkin järjestyksessä, tämä järjestys ei ylitä degeneraatiota plus yksi. Ahneella järjestysväritysalgoritmilla optimaalisella värjäysmäärällä on mahdollista värittää k - degeneroitunut graafi käyttämällä enintään k  + 1 väriä [6] [26] .

Vertex-k-yhdistetty graafi on graafi, jota ei voida hajottaa useiksi komponenteiksi poistamalla vähemmän kuin k pistettä, tai vastaavasti, se on graafi, jossa kukin pistepari voidaan yhdistää k polulla, joilla ei ole yhteisiä pisteitä. Koska näiden kahden kärjen täytyy kulkea näillä poluilla eri reunojen läpi, k -vertex-liitetyllä graafilla on oltava vähintään k degeneraatio . K -ytimen kaltaista, mutta kärkien liitettävyyteen perustuvaa käsitettä tutkitaan sosiaalisten verkostojen teoriassa nimellä rakenneyhteydet [27] .

Jos graafin puunleveys tai polunleveys on enintään k , niin se on sointugraafin aligraafi , jonka eliminointijärjestys on täydellinen siten, että jokaisella kärjellä on enintään k edeltävää naapuria. Siten rappeutuminen ei ylitä puun leveyttä ja polun leveyttä. On kuitenkin olemassa kaavioita, joilla on rajoitettu rappeutuminen ja rajoittamaton puunleveys, kuten hilat [28] .

Erdős-Boer-oletus koskee yhteyttä graafin G rappeutumisen ja graafin G Ramsey - luvun välillä , suurin n , jolle n -pisteisen täydellisen graafin reunojen minkä tahansa kaksivärisen värityksen tulee sisältää yksivärinen kopio. kaaviosta G . Tarkemmin sanottuna olettamus väittää, että millä tahansa k :n kiinteällä arvolla k -degeneroituneiden graafien Ramsey-luku kasvaa lineaarisesti graafin kärkien lukumäärän kanssa [29] . Oletuksen todisti Lee [30] .

Äärettömät kaaviot

Vaikka degeneraation ja luvun värjäytymisen käsitteet viittaavat usein äärellisten graafien kontekstiin, Erdősin ja Hajnalin [6] alkuperäinen tavoite oli äärettömien graafien teoria. Äärettömälle graafille G väritysluku voidaan määritellä, kuten äärellisten graafien määritelmä, pienimmäksi kardinaaliluvuksi α, jolle on olemassa G :n kärkien järjestys, joka on hyvin järjestetty , jossa jokaisessa kärjessä on vähemmän kuin α-naapurit järjestyksen aiempien kärkien joukossa. Epäyhtälö väritysluvun ja kromaattisen luvun välillä pätee myös äärettömään tapaukseen. Erdős ja Hajnal [6] väittivät tämän, ja heidän julkaisunsa julkaisuhetkellä tosiasia oli hyvin tiedossa.

Äärettömän hilan satunnaisten osajoukkojen degeneraatiota tutkitaan teoriassa nimeltä initiating percolation .

Muistiinpanot

  1. ↑ 1 2 Altaf-Ul-Amin, Nishikata, Koma, Miyasato et ai., 2003 .
  2. ↑ 1 2 Wuchty, Almaas, 2005 .
  3. ↑ Bader, Hogue, 2003 .
  4. ↑ Freuder, 1982 .
  5. ↑ Kirousis, Thilikos, 1996 .
  6. ↑ 1 2 3 4 5 Erdős, Hajnal, 1966 .
  7. ↑ Irani, 1994 .
  8. ↑ 1 2 Matula, Beck, 1983 .
  9. ↑ 12 Lick , White, 1970 .
  10. ↑ Barabasi, Albert, 1999 .
  11. ↑ Jensen ja Toft ( Jensen, Toft 2011 ), s. 78 : "On helppo nähdä, että col( G ) = Δ( G ) + 1 jos ja vain jos G :llä on Δ( G ) -säännöllinen komponentti." Jensenin ja Toftin merkinnöissä col( G ) on yhtä suuri kuin degeneraatio + 1 ja Δ( G ) on yhtä suuri kuin kärjen maksimiaste.
  12. ↑ Matula, 1968 .
  13. ↑ Lick and White, 1970 , s. 1084 Ehdotus 1.
  14. ↑ 1 2 Chrobak, Eppstein, 1991 .
  15. ↑ Seidman, 1983 .
  16. ↑ Bollobás, 1984 .
  17. ↑ Luczak, 1991 .
  18. ↑ Dorogovtsev, Goltsev, Mendes, 2006 .
  19. ↑ Gaertler, Patrignani, 2004 .
  20. ↑ Alvarez-Hamelin, Dall'Asta, Barrat, Vespignani, 2005 .
  21. ↑ Gabow, Westermann, 1992 .
  22. ↑ Venkateswaran, 2004 .
  23. ↑ Asahiro, Miyano, Ono, Zenmyo, 2006 .
  24. ↑ Kowalik, 2006 .
  25. ↑ Dean, Hutchinson, Scheinerman, 1991 .
  26. ↑ Szekeres, Wilf, 1968 .
  27. ↑ Moody, White, 2003 .
  28. ↑ Robertson, Seymour, 1984 .
  29. ↑ Burr, Erdős, 1975 .
  30. ↑ Lee, 2017 .

Kirjallisuus