-
Chính quy
-
Đầy đủ
Sân chơi lý thuyết đồ thị
Đồ thị là một tập hợp các điểm, gọi là đỉnh, được nối với nhau bằng các đường, gọi là cạnh. Hãy vẽ một đồ thị ở đây chỉ với vài cú nhấp, sân chơi sẽ cho bạn biết đó là loại đồ thị gì: có bao nhiêu mảnh, có phải là cây không, cần ít nhất bao nhiêu màu, có vẽ được bằng một nét hay không, và nhiều điều khác nữa. Nhấp vào một tính chất để xem nó trên đồ thị của bạn, thay đổi một cạnh và xem các câu trả lời thay đổi theo. Nhấp vào chỗ trống để thêm một đỉnh. Nhấp vào một đỉnh rồi một đỉnh khác để nối chúng bằng một cạnh; làm lại lần nữa để bỏ cạnh đó. Kéo một đỉnh để di chuyển nó. Chuyển thao tác nhấp sang Xóa rồi nhấp vào một đỉnh hoặc một cạnh để xóa nó. Khi đang chọn một đỉnh, phím Delete xóa đỉnh đó, còn Escape bỏ chọn. Nhấp vào một tính chất để hiển thị nó trên đồ thị. Ví dụ tải một đồ thị nổi tiếng, Đồ thị ngẫu nhiên tạo một đồ thị mới, Dàn đều trải các đỉnh ra cho thoáng, còn Đồ thị bù nối đúng những cặp đỉnh trước đó chưa được nối. Ctrl+Z hoàn tác một bước.
Cách nó hoạt động
- Nhấp vào chỗ trống để thêm một đỉnh. Nhấp vào một đỉnh rồi một đỉnh khác để nối chúng; làm lại lần nữa để bỏ cạnh. Kéo một đỉnh để di chuyển nó.
- Xem các tính chất bên dưới đồ thị và nhấp vào một tính chất để hiển thị nó: một cách tô màu, hai phía, một đường Euler, một cây khung, chu trình ngắn nhất hoặc đường kính.
- Tải một ví dụ như đồ thị Petersen, tạo đồ thị ngẫu nhiên, lấy đồ thị bù, hoặc chuyển thao tác nhấp sang Xóa để xóa đỉnh và cạnh.
Ý nghĩa của các tính chất
Bậc của một đỉnh là số cạnh gắn với đỉnh đó. Đồ thị liên thông khi từ mỗi đỉnh có thể đi theo các cạnh tới mọi đỉnh khác, và là cây khi nó liên thông và không có chu trình. Đồ thị là hai phía khi các đỉnh chia được thành hai phía sao cho mọi cạnh đều nối phía này với phía kia, và điều đó xảy ra đúng khi đồ thị không có chu trình độ dài lẻ. Sắc số là số màu ít nhất cần dùng để hai đỉnh kề nhau luôn khác màu. Độ dài chu trình ngắn nhất được gọi là chu vi (girth) của đồ thị, còn đường kính là khoảng cách lớn nhất giữa hai đỉnh, tính bằng số cạnh.
Vẽ bằng một nét
Đường Euler đi qua mỗi cạnh đúng một lần. Năm 1736, với bài toán bảy cây cầu ở Königsberg, Leonhard Euler đã nhận ra trở ngại nằm ở đâu: mỗi lần đường đi qua một đỉnh, nó dùng hai cạnh của đỉnh đó. Vì vậy, hoặc mọi bậc đều chẵn, và đường có thể kết thúc tại nơi bắt đầu, hoặc có đúng hai bậc lẻ, và đường phải đi từ đỉnh lẻ này đến đỉnh lẻ kia. Về sau, Carl Hierholzer chứng minh rằng điều kiện này, cùng với việc mọi cạnh nằm trong một mảnh, cũng là đủ. Hãy tải ví dụ ngôi nhà và tìm xem nét vẽ phải bắt đầu từ đâu.
Câu hỏi thường gặp
Đồ thị trong lý thuyết đồ thị là gì?
Đó là một tập hợp các điểm, gọi là đỉnh hay nút, cùng các đường nối một số cặp điểm với nhau, gọi là cạnh. Nó không phải đồ thị của hàm số: nó chỉ mô tả cái gì được nối với cái gì. Bản đồ đường sá, mạng xã hội, phân tử và mạng máy tính đều là đồ thị.
Sắc số được tính như thế nào?
Sân chơi thử tô đồ thị bằng một màu, rồi hai, rồi ba màu và cứ thế tiếp tục; với mỗi số màu, nó duyệt qua mọi cách tô cần xét, và luôn tô tiếp đỉnh mà các đỉnh kề đang dùng nhiều màu nhất. Số màu đầu tiên tô được chính là sắc số. Với những đồ thị bạn có thể vẽ ở đây, việc này chỉ mất nhiều nhất là một thoáng; với đồ thị rất khó, phép tìm kiếm dừng sớm và giá trị được hiển thị như một cận trên.
Khi nào một đồ thị có đường đi Euler?
Khi mọi cạnh của nó nằm trong một mảnh và có không quá hai đỉnh bậc lẻ. Nếu không có đỉnh bậc lẻ nào, đồ thị có chu trình Euler kết thúc tại nơi bắt đầu; nếu có hai, mọi đường đi Euler đều bắt đầu ở một đỉnh và kết thúc ở đỉnh còn lại. Số đỉnh bậc lẻ luôn là số chẵn, nên không bao giờ có đúng một.
Đồ thị bù là gì?
Là đồ thị trên cùng tập đỉnh mà các cạnh chính là những cặp đỉnh trước đó chưa được nối. Đồ thị bù của đồ thị bù là đồ thị ban đầu. Ví dụ, đồ thị bù của đồ thị Petersen là đồ thị chính quy bậc 6, vì mỗi đỉnh vốn được nối với 3 trong số 9 đỉnh còn lại.
Vì sao đồ thị Petersen nổi tiếng?
Đó là một đồ thị nhỏ với 10 đỉnh và 15 cạnh, nhưng lại là phản ví dụ cho rất nhiều giả thuyết đầy kỳ vọng. Mọi đỉnh đều có bậc 3, chu trình ngắn nhất có độ dài 5, hai đỉnh bất kỳ cách nhau nhiều nhất 2 cạnh, và không thể vẽ nó mà không có cạnh cắt nhau. Sân chơi mở ra với chính đồ thị này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa