Graf Petersena – w teorii grafów, szczególny graf kubiczny o 10 wierzchołkach i 15 krawędziach. 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.
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.
Przypisy
Linki zewnętrzne
Petersen graph , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-12-14].
Petersena