In graafiteoria , degeneraatio on parametri, joka liittyy suuntaamattoman graafin . Graafi on k -degenerated jos jokin aligraafi sisältää solmun astetta vähemmän kuin tai yhtä suuri kuin k , ja rappeutuminen kuvaaja, on pienin k siten, että se on k -degenerated. Voimme vastaavalla tavalla määritellä parametrin käyttämällä pisteiden järjestystä, sitten löydämme termien merkintöjen lukumäärän .
Degeneraatio on mittarin mittatiheyden mitta.
Kaavio sanotaan olevan k -degenerated jos jokin aligraafi sisältää solmun astetta pienempi kuin tai yhtä kuin k . Vastaavasti graafi k- rappeutuu, jos pisteissä on järjestys siten, että minkä tahansa kärjen kohdalla reunojen lukumäärä pienempiin pisteisiin on korkeintaan k .
Kutsumme pienimmän kokonaislukukaavion rappeutumista siten, että kaavio on rappeutunut. Termejä merkinnän numero ja värin numero käytetään joskus.
Rappeuma on kromaattisen luvun yläraja . Rappeutuminen liittyy muihin kuvaajan parametreihin, kuten arboriteetti ja puun leveys .
Erdős-Burr arveluihin sanoo, että minkä tahansa kokonaisluku p , on olemassa vakio c siten, että kaikki s -degenerated kuvaajan kanssa n kärjet on sen Ramsey määrä kasvoi cn .
Degeneraatio on mahdollista laskea lineaarisessa ajassa .
Rappeuma tapahtuu luonnollisesti kuvaajan väritysongelmissa. Hyvin lähellä oleva k -core- käsite on työkalu sosiaalisten verkostojen analysointiin .
Tilausta käyttävä määritelmä on vuodelta 1966, ja se johtuu Paul Erdősistä ja András Hajnalista . Toinen ilmestyi neljä vuotta myöhemmin Lick and Whitein artikkelissa.