Zvezda (teorija grafov)

Zvezda (oznaka S_n) je v teoriji grafov polni dvodelni graf K_1,n, drevo z enim notranjim stičiščem (centrom) in n listi. Zvezda s 3 povezavami se imenuje šapa (Predloga:Jezik-en). Zvezda, ki po definiciji ni drevo, je S₀.

Zvezda S_n 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 S₀, ki je prazni graf (nima povezav in zato ni povezan), in S₁, kjer imata obe točki stopnji 1. Grafi S₀, S₁ in S₂ so enaki ustreznim potem P₁, P₂ in P₃.

Glej tudi

• graf brez šap

Zunanje povezave

• Predloga:MathWorld