Graf Petersena

Graf Petersena – w teorii grafów, szczególny graf kubiczny o 10 wierzchołkach i 15 krawędziach[1]. Nazwany na cześć matematyka Juliusa Petersena, który w 1898 podał go jako przykład grafu regularnego stopnia 3 bez mostów, którego krawędzi nie można pokolorować trzema kolorami[2][3].

  • Graf Petersena
    Graf Petersena
  • Graf Petersena narysowany z dwoma przecięciami.
    Graf Petersena narysowany z dwoma przecięciami.
  • Graf Petersena narysowany tak, że wszystkie krawędzie są tej samej długości.
    Graf Petersena narysowany tak, że wszystkie krawędzie są tej samej długości.

Własności

Graf Petersena...

Własności grafu Petersena:

liczba wierzchołków 10
liczba krawędzi 15
Stopień 3
liczba chromatyczna 3
indeks chromatyczny 4
promień 2
średnica 2
obwód 5
widmo −2, −2, −2, −2, 1, 1, 1, 1, 1, 3

Inne cechy

  • jest najmniejszym żmirłaczem.
  • jest najmniejszym grafem kubicznym bez mostów i cykli Hamiltona.
  • jest największym grafem kubicznym o średnicy 2.
  • jest najmniejszym grafem hipohamiltonowskim.

Przypisy

  1. ↑ Eric W.E.W. Weisstein Eric W.E.W., Petersen Graph [online], Wolfram MathWorld [dostęp 2024-04-28]  (ang.).
  2. ↑ AndriesA. Brouwer AndriesA., The Petersen graph [online] [dostęp 2024-04-28]  (ang.).
  3. ↑ JuliusJ. Petersen JuliusJ., Sur le théorème de Tait, „L'Intermédiaire des mathématiciens”, 1898, s. 225-227 [dostęp 2024-04-28]  (fr.).

Linki zewnętrzne

Eric W.E.W. Weisstein Eric W.E.W., Petersen Graph, [w:] MathWorld, Wolfram Research [dostęp 2024-04-28]  (ang.).