Đồ thị Petersen

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Đồ thị Petersen
Petersen1 tiny.svg
Đồ 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[sửa | sửa mã nguồn]

Đồ thị Petersen là đồ thị bù của đồ thị đường (tiếng Anh: line graph) của đồ thị K_5.

Tính phẳng[sửa | sửa mã nguồn]

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

Chu trình và đường đi Hamilton[sửa | sửa mã nguồn]

Đồ 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ị[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

Ghi chú[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]