Graf Petersena
Niniejszy artykuł jest częścią cyklu teoria grafów. |
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
Graf Petersena to graf o ciekawych własnościach często używany w teorii grafów. Nazwa pochodzi od nazwiska matematyka J. Petersena, któremu przypisuje się pierwszą publikację na temat grafu w 1898 roku.
Graf Petersena
Graf Petersena narysowany z dwoma przecięciami.
Graf Petersena narysowany tak, że wszystkie krawędzie są tej samej długości.
Własności
Graf Petersena...
- jest silnie regularny stopnia 3.
- jest trójspójny i trójspójny krawędziowo.
- ma ścieżkę Hamiltona, ale nie ma cyklu Hamiltona.
- jest grafem trójdzielnym.
- jest dopełnieniem grafu krawędziowego grafu K5.
- jest symetryczny, to znaczy krawędziowo tranzytywny i wierzchołkowo tranzytywny.
- nie jest grafem planarnym.
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.