Đồ thị Petersen

Đồ thị Petersen

Đồ thị Petersen được vẽ như 1 ngũ giác bao ngoài và hình ngôi sao bên trong.

số đỉnh: 10

số cạnh: 15

bán kính: 2

đường kính: 2

chu trình ngắn nhất: 5

ký hiệu:

số đồ thị đẳng cấu: 120 (S5)

sắc số: 3

số màu cạnh: 4

spectral_gap

tính chất khác đối xứng

Trong lý thuyết đồ thị, đồ thị Petersen là 1 đồ thị vô hướng với 10 đỉnh và 15 cạnh. Nó thường được sử dụng làm minh họa trong khi trình bày các lý thuyết đồ thị. Đồ thị này được đặt tên theo Julius Peterse,^[1] mặc dù nó đã được đưa ra 12 năm trước đó, vào năm 1886.

Cấu hình

Đồ thị Petersen là đồ thị bù của đồ thị đường (tiếng Anh: line graph) của đồ thị ${\displaystyle K_{5}}$.

Tính phẳng

Đây là đồ thị liên thông, không phẳng. Nó chứa đồ thị con đồng phôi với ${\displaystyle K_{5}}$, và đồ thị hai phía đầy đủ ${\displaystyle K_{3,3}}$

Chu trình và đường đi Hamilton

Đồ thị Petersen có đường đi Hamilton, nhưng không có chu trình Hamilton. Đặc biệt, đồ thị nhận được bằng cách xóa một đỉnh bất kì của đồ thị Petersen, luôn có chu trình Hamilton.

Tô màu đồ thị

Có thể tô màu các đỉnh bởi ít nhất 3 màu (sắc số), sao cho không có 2 đỉnh nào liền kề mà lại có cùng màu.

Các cạnh có thể tô bởi ít nhất 4 màu, sao cho không có 2 cạnh cùng liên thuộc với cùng một đỉnh lại có cùng màu.

Các tính chất khác

• Là đồ thị 3-chính quy (các đỉnh của nó đều có bậc 3).
• Có số độc lập bằng 4.
• Có bán kính bằng 2, và đường kính bằng 2.
• Có 2000 cây khung.

• 
  Bằng cách xóa một đỉnh bất kì của đồ thị Petersen, ví dụ đỉnh ở giữa trong hình vẽ này, đồ thị nhận được luôn có đường đi Hamilton. Hình vẽ này thể hiện tính đối xứng bậc ba của đồ thị.
• 
  Tô màu các cạnh bằng 4 màu
• 
  Tô màu các đỉnh bằng 3 màu

Ghi chú

1. Brouwer, Andries E., The Petersen graph

Tham khảo

• Exoo, Geoffrey; Harary, Frank; Kabell, Jerald (1981), “The crossing numbers of some generalized Petersen graphs”, Mathematica Scandinavica, 48: 184–188.
• Coxeter, H. S. M. (1950), “Self-dual configurations and regular graphs”, Bulletin of the American Mathematical Society, 56: 413–455, doi:10.1090/S0002-9904-1950-09407-5.
• Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, doi:10.2277/0521435943, ISBN 0-521-43594-3, Bản gốc lưu trữ ngày 8 tháng 2 năm 2008, truy cập ngày 10 tháng 10 năm 2010.
• Jakobson, Dmitry; Rivin, Igor (1999), On some extremal problems in graph theory, arXiv:math.CO/9907050.
• Keller, Mitch. “Kneser graphs”. PlanetMath.

• Lovász, László (1993), Combinatorial Problems and Exercises (ấn bản thứ 2), North-Holland, ISBN 0-444-81504-X.
• Petersen, Julius (1898), “Sur le théorème de Tait”, L'Intermédiaire des Mathématiciens, 5: 225–227.
• Valdes, L. (1991), “Extremal properties of spanning trees in cubic graphs”, Congressus Numerantium, 85: 143–160.
• Watkins, Mark E. (1969), “A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs”, Journal of Combinatorial Theory, 6: 152–164, doi:10.1016/S0021-9800(69)80116-X.
• Weisstein, Eric W., "Petersen Graph" từ MathWorld.