Zvezda (teorija grafov)

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Zvezda
Star network 7.svg
Zvezda S7.
Točke n+1
Povezave n
Premer 2
Notranji obseg
Kromatično število 2
Kromatični indeks n
Značilnosti povezavnoprehoden
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]