Stjärngraf
Inom grafteori är en stjärngraf Sk den kompletta bipartita grafen K1,k: ett träd med en intern nod och k blad (löv) för k>1, men utan interna noder och med k + 1 blad för k ≤ 1. Vissa författare definierar däremot Sk som trädet av ordning k med största diameter 2, i vilket fall en stjärngraf med k>2 i stället har k − 1 blad.
En stjärngraf med tre kanter kallas klograf.
En stjärngraf kan också beskrivas som en graf med högst en nod som har en högre grad än ett. En stjärngraf är en kanttransitiv tändsticksgraf, har ett kromatiskt tal som är 2 och ett kantkromatiskt tal som är k.
Prüfersekvensen för en orotad märkt stjärngraf K1,k består av k − 1 upprepningar av centralnoden.[1]
Referenser
- ^ Gottlieb, J.; Julstrom, B. A.; Rothlauf, F.; Raidl, G. R. (2001), ”Prüfer numbers: A poor representation of spanning trees for evolutionary search”, Proc. Genetic and Evolutionary Computation Conference, Morgan Kaufmann, s. 343–350, arkiverad från ursprungsadressen den 2006-09-26, https://web.archive.org/web/20060926171652/http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf Arkiverad 26 september 2006 hämtat från the Wayback Machine. ”Arkiverade kopian”. Arkiverad från originalet den 26 september 2006. https://web.archive.org/web/20060926171652/http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf. Läst 28 november 2014..
Media som används på denna webbplats
