Zvezda (teorija grafov)
Jump to navigation
Jump to search
Zvezda | |
---|---|
![]() 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]
![]() |
Wikimedijina zbirka ponuja več predstavnostnega gradiva o temi: Zvezda (teorija grafov |
- Weisstein, Eric Wolfgang. "Star Graph". MathWorld (angleščina).