Vẽ hình bằng một nét Tình cờ tôi tìm ra cách vẽ hình trên bằng 1 nét (tổng cộng là 24 đường thẳng). Các bạn giải thử và đưa ra cách làm tổng quát cho các loại bài toán này. Hình như nó là 1 phần của hình học topo với các điểm chẵn, lẻ, quay phải, trái, lồi lõm, yên ngựa, ... gì đó mà tôi không còn nhớ nữa.
Chào nqh1! Mình nghĩ có thể giải bài này bằng graph như sau: Lấy 8 điếm A,B,C,D,E,F,G,H tren 1 đường tròn (có thể lấy đó là 8 đỉnh của 1 bát giác đều cho đẹp). Sau đó nối tương ứng mỗi đỉnh với tất cả các đỉnh khác trừ đỉnh đối diện với nó trên hình lập phương (ví dụ A không nối với G, B không nối với H,.....) Như thế chúng ta thu được 1 graph lồi ( là 1 graph mà với hai đỉnh bất kỳ của nó đều có thế từ đỉnh này đi đến đỉnh kia bằng các cạnh của graph). Hơn nữa bậc của mỗi đỉnh ( số đoạn thẳng có đỉnh là đỉnh này) đều chẵn (=6) Theo định lý Euler thì: Với 1 graph lồi, khi ấy tồn tại 1 chu trình Euler (đường đi qua tất cả các cạnh của graph một và chỉ 1 lần) khi và chỉ khi bậc của mỗi đỉnh đều chẵn. Nhận thấy rằng điều này tương đương với việc có thể vẽ graph đó mà không nhấc bút lên, đồng thời mỗi cạnh chỉ vẽ 1 lần. Theo mình được biết, chứng minh của định lý Euler không khó, nhưng để bạn tìm hiểu kỹ hơn về graph, bạn có thể đọc cuốn "Graph và giải toán phổ thông" của thầy Hoàng Chúng. Mình cũng nghĩ rằng việc xét 1 hình liệu có thể vẽ bằng 1 nét hay không chắc có thể đưa về graph để xét. Bài toán kiểu này cũng có rất nhiều ứng dụng trong cuộc sống, chắc là cũng được nghiên cứu nhiều rồi. Chúc bạn vui vẻ nhé, có gì chúng ta cùng trao đổi thêm!
Xin cảm ơn! đúng là theo định lý Euler bạn có thể chứng minh hình này có thể vẽ được bằng 1 nét. Nhưng cách chứng minh định lý Euler như thế nào? Bạn có còn nhớ không? (Hình như định lý này được chứng minh bằng qui nạp cho 1 đồ thị (Graph) lồi có n đỉnh và số bậc mỗi đỉnh là số chẵn - hình ngôi sao năm cánh chẳng hạn.) Còn hình số 2 có thể vẽ được ít nhất bằng bao nhiêu nét.
Chào bạn eiffel, Tưởng cái này là đồ thị liên thông chứ nhỉ ? Nếu không đòi hỏi phải quay trở về nơi xuất phát, thì có thể cho phép có 2 đỉnh có bậc lẻ. Được altus sửa chữa / chuyển vào 18:42 ngày 08/12/2003
Cho mình xin lỗi, đúng như bạn viết đấy, gọi là đồ thị liên thông mới đúng, tha lỗi cho mình nhé! Thực ra thì định lý Euler có hai phần, phần đầu chỉ phát biểu cho một đường đi (không biết có nhớ đúng không nữa): Cho graph liên thông G, khi ấy tồn tại 1 đường đi Euler khi và chỉ khi tất cả các đỉnh đều có bậc chẵn, trừ hai đỉnh bắt đầu và kết thúc của đường đi. Chứng minh cũng không khó, nhưng tuần này mình bận quá, chắc là phải để đến cuối tuần này mình mới post lên được, bạn nào biết thì post lên hộ mọi người với!
Giả sử ta có m đỉnh {Vi}m và n edge (mình cũng chả biết tiếng Việt gọi la gì nữa) {ei}n. gọi {fi}n là một hoán vị của {ei}n. Khi đấy tồn tại một Eulerian path nếu tồn tại một chu trình Vi f1 f2 f3 .... fn Vj Giả sử tồn tại Vk nằm trong path (ko kể 2 đầu mút) mà có bậc lẻ ==> ko thể vừa vào vừa ra khỏi Vk. Vì vậy Vk phải có bậc chẵn. Đối với 2 đầu mút thì cộng thêm 1 vào => 2 đầu mút phải có bậc lẻ. Đối với Eulerian Circuit thì chỉ cần chú ý Vi trùng với Vj. [topic]218302[/topic]
Nói thêm luôn về thuật toán Fleury để vẽ Eulerian Circuit. Cho graph G=<V, E> sao cho tất cả vertex của G đều có bậc chẵn. 1/Chọn bất kỳ V0 trong G và set C0=V0, set i:=0. 2/ Giả sử chúng ta có chu trình Ci=V0 e1 V1 e2... ei Vi - Tại đỉnh Vi chọn bất cứ edge ei+1 ko nằm trong Ci và trong Gi= G - E(Ci) trừ khi ko còn cách nào để chọn. -Define Ci+1= Ci ei+1 Vi+1 -Set i:=i+1 3/ Nếu i=|E(G)| thì ta có C=Ci, else làm lại bước 2. [topic]218302[/topic]
Người ta còn có công thức tính xem có bao nhiê u cách vẽ một đồ thị bằng 1 nét dựa vào số bậc của mỗi đỉnh và số "spaning tree" của graph. Matek
Hôm trước tớ cũng bị đố vẽ hình 2 bằng 5 nét!!!! Có thể chứng minh cần dùng ít nhất 6 nét như thế này: Có 12 đỉnh lẻ, và giả sử thay vì vẽ ta xoá các nét vẽ có sẵn đi. Khi xoá hết thì các đỉnh có bậc là 0 và do đó đều là chẵn. Chú ý rằng sau mỗi lần xoá thì có nhiều nhất 2 đinh mà bậc của chúng có thể thay đổi tính chẵn lẻ, là đỉnh xuất phát và đỉnh kết thúc, trong khi đó ta có tới 12 đỉnh lẻ cần thay đổi trạng thái thành chẵn.-->Đpcm
