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 \infty\!\,
Kromatično število 2
Kromatični indeks n
Značilnosti povezavno-prehoden
drevo
z enotsko razdaljo
dvodelen
Označba S_{n}\!\,

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 povezavno-prehoden, ima enotsko razdaljo, premer 2, notranji obseg ∞, kromatično število 2 in kromatični indeks n.

Zvezde lahko opišemo 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]