Pojdi na vsebino

Zvezda (teorija grafov)

Iz Wikipedije, proste enciklopedije
Zvezda
Zvezda S7.
Točken+1
Povezaven
Premer2
Notranji obseg
Kromatično število2
Kromatični indeksn
Značilnostipovezavnoprehoden
drevo
z enotsko razdaljo
dvodelen
Označba

Zvezda (oznaka Sn) je v teoriji grafov polni dvodelni graf K1,n, drevo z enim notranjim stičiščem (centrom) in n listi. Zvezda s 3 povezavami se imenuje šapa (angleško claw). Zvezda, ki po definiciji ni drevo, je S0.

Zvezda Sn je po povezavah elegantna pri sodem n, in neelegantna pri lihem n. Graf zvezda je povezavnoprehoden, ima enotsko razdaljo, premer 2, notranji obseg ∞, kromatično število 2 in kromatični indeks n.

Zvezde se lahko opiše tudi kot edine povezane grafe v katerih ima največ ena točka stopnjo večjo kot 1. Izjemi sta S0, ki je prazni graf (nima povezav in zato ni povezan), in S1, kjer imata obe točki stopnji 1. Grafi S0, S1 in S2 so enaki ustreznim potem P1, P2 in P3.

Glej tudi

[uredi | uredi kodo]

Zunanje povezave

[uredi | uredi kodo]
  • Weisstein, Eric Wolfgang. »Star Graph«. MathWorld.