Graf Petersena
Graf Petersena to szczególny graf kubiczny składający się z 10 wierzchołków i 15 krawędzi. Został opisany przez matematyka Juliusa Petersena w 1898 roku jako przykład regularnego grafu o stopniu 3, który nie zawiera mostów, a jego krawędzie nie mogą być pokolorowane trzema kolorami.
Reklama
Własności
Graf Petersena charakteryzuje się następującymi cechami:
- Jest silnie regularny o stopniu 3.
- Jest trójspójny oraz trójspójny krawędziowo.
- Zawiera ścieżkę Hamiltona, ale nie ma cyklu Hamiltona.
- Jest grafem trójdzielnym.
- Stanowi dopełnienie grafu K5.
- Jest symetryczny, co oznacza, że jest zarówno krawędziowo, jak i wierzchołkowo tranzytywny.
- Nie jest grafem planarnym.
Inne cechy
- Najmniejszy żmirłacz.
- Najmniejszy graf kubiczny bez mostów i cykli Hamiltona.
- Największy graf kubiczny o średnicy 2.
- Najmniejszy graf hipohamiltonowski.
Przypisy
Graf Petersena jest istotnym obiektem badań w teorii grafów, a jego unikalne właściwości sprawiają, że jest często wykorzystywany w różnych dziedzinach matematyki.
Reklama
Linki zewnętrzne
Więcej informacji można znaleźć w literaturze dotyczącej teorii grafów oraz na stronach internetowych poświęconych matematyce.
Reklama
