Hãy chỉ ra một ví dụ chứng tỏ rằng điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 𝑛/2 trong Định lí Dirac, không thể thay bằng điều kiện “bậc của mỗi đỉnh không nhỏ hơn (𝑛−1)/2”.

Cho đồ thị G như Hình 27. Tìm một đường đi Hamilton từ S đến R.

Cho đồ thị G như Hình 2.26. Tìm một chu trình Hamilton xuất phát từ đỉnh S của G.

Có thể nào đi dạo chơi qua các cây cầu trong Hình 2.25, mỗi cây cầu vừa đúng một lần?

Mỗi đồ thị sau có một chu trình Euler hoặc một chu trình Hamilton hay không? Hãy vẽ một chu trình Euler hoặc một chu trình Hamilton khi có thể.

Đồ thị nào trong Hình 2.2.3 có đường đi Hamilton? Hãy chỉ ra một đường đi Hamiton của nó.

Có 5 thành phố du lịch A, B, C, D, E và các con đường nối các thành phố này như Hình 2.20. Hãy chỉ ra một cách để đi tham quan cả 5 thành phố đó, mà không cần đến địa điểm nào quá một lần.

Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó.

Hãy thử vẽ mỗi hình trên Hình 2.16 bằng một nét liền.

Trong lí thuyết đồ thị, bài toán Bảy câu cầu ở Königsberg (nay là thành phố Kaliningrad, nước Nga) được phát biểu như sau: Thành phố có 7 cây cầu bắc qua sông như Hình 2.15a dưới đây, có thể nào đi dạo qua khắp các cây cầu nhưng mỗi cầu chỉ đi qua một lần không?

Nếu ta coi mỗi khu vực A, B, C, D của thành phố là một đỉnh, mỗi cầu qua lại hai khu vực như một cạnh nối hai đỉnh, thì bản đồ thành phố Königsberg là một đa đồ thị như Hình 2.15b. Vấn đề đặt ra chính là: Có thể vẽ được Hình 2.15b bằng một nét liền hay không?

Cho đồ thị G như Hình 2.14.

a) Tìm một đường đi từ đỉnh A đến đỉnh B.

b) G có liên thông không?

c) Trong G có chu trình sơ cấp nào không?

Chứng minh rằng không tồn tại đồ thị với các đỉnh có bậc là 2, 3, 3, 4, 4 và 5. 

Chứng minh rằng một đồ thị đầy đủ có n đỉnh thì có n(n−1)2𝑛𝑛−12 cạnh.

Một đồ thị con của đồ thị G là một đồ thị mà mọi đỉnh của nó đều là đỉnh của G và mọi cạnh của nó cũng là cạnh của G.

Những đồ thị nào trong các hình a), b), c) dưới đây là đồ thị con của đồ thị G?

Hãy vẽ một đồ thị có 4 đỉnh và:

a) có đúng hai đỉnh cùng bậc và bậc là 1;

b) có đúng hai đỉnh cùng bậc và bậc là 2.

Vẽ hình biểu diễn của đồ thị G với tập đỉnh V(G) = {1; 2; 3; 4; 5} và tập cạnh

E(G) = {12; 14; 23; 25; 34; 35}.

Đồ thị G có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?

Chứng minh đồ thị ở Hình 2.12 là liên thông. Hãy chỉ ra một đường đi nối đỉnh 1 và đỉnh 6.

Trong đồ thị ở Hình 2.10, hãy:

a) Tìm một đường đi từ đỉnh A đến đỉnh E.

b) Có tồn tại một đường đi từ đỉnh A đến đỉnh F hay không?

Cho đồ thị đầy đủ có 5 đỉnh như Hình 2.9. Tìm những chu trình sơ cấp xuất phát từ đỉnh A và có: độ dài 4; độ dài 5.

Cho đồ thị như Hình 2.7. Bằng cách đi dọc theo các cạnh, với điều kiện không đi qua cạnh nào quá một lần (có thể có cạnh không cần đi qua), hãy chỉ ra các cách để:

a) Đi từ đỉnh A đến đỉnh E.

b) Đi từ đỉnh A và lại quay về đỉnh A.

Chứng minh rằng không có đơn đồ thị với 12 đỉnh và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 4.

Cho đồ thị như Hình 2.5. Tìm các đỉnh là đầu mút của: 0 cạnh; 1 cạnh; 2 cạnh; 3 cạnh.

Vẽ các đồ thị đầy đủ có 5 đỉnh, có 6 đỉnh.

Xét đồ thị nhận được trong Luyện tập 1. Có cặp đỉnh nào của đồ thị này mà không có cạnh nào nối chúng không?

Vẽ đồ thị G với các đỉnh và các cạnh như sau:

V(G) = {U, W, X, Z} và E(G) = {UW, WX, WZ, XZ}.

G có phải là một đơn đồ thị không?

Xét đồ thị cho trong Hình 2.2.

a) Đồ thị trên có khuyên không?

b) Có hai đỉnh nào của đồ thị được nối với nhau bằng nhiều hơn một cạnh không?

Bảng F của giải vô địch bóng đá thế giới World Cup 2018 gồm bốn đội: Đức, Hàn Quốc, Mexico và Thuỵ Điển. Biểu diễn các đội này bằng các điểm phân biệt kí hiệu lần lượt là D, H, M, T (vẽ sao cho không có ba điểm nào thẳng hàng để dễ quan sát) và nếu hai đội nào đấu với nhau thì ta nối hai điểm tương ứng bằng một đoạn thẳng, ta sẽ được một đồ thị G.

Viết tập hợp các đỉnh và tập hợp các cạnh của đồ thị G.

Có bốn bạn học sinh khối 11 là An, Bình, Cường và Dung, trong đó: An là bạn của Bình và Cường, nhưng không là bạn của Dung; Dung là bạn của Cường, nhưng không là bạn của Bình; Bình là bạn của Cường.

a) Hãy biểu diễn mỗi bạn An, Bình, Cường, Dung bằng một điểm trên mặt phẳng và dùng chữ cái đầu (in hoa) trong tên của họ để đặt tên cho các điểm này.

b) Nếu hai người là bạn của nhau, hãy nối các điểm biểu diễn tương ứng bằng một đoạn thẳng (hay đoạn đường cong).

c) Từ hình vẽ thu được ở HĐ1b, hãy cho biết: ai có nhiều bạn nhất và ai có ít bạn nhất?

Trước khi vào một hồi nghị, các đại biểu bắt tay nhau (hai người bắt tay nhau nhiều nhất 1 lần). Có một đại biểu không bắt tay ai hết và thấy rằng có 4 người bắt tay 4 lần, 5 người bắt tay 5 lần và 6 người bắt tay 6 lần. Nếu hội nghị có đúng 16 đại biểu thì ông ta đếm nhầm. Vì sao có thể kết luận như vậy?

Bằng quan sát và đo đạc, hãy cho biết hai hình sau (H.1.55) có đồng dạng với nhau hay không.

Cho nửa đường tròn tâm O, đường kính AB và điểm M trên nửa đường tròn đó. Dựng về phía ngoài của tam giác ABM tam giác AMN vuông cân tại M. Chứng minh rằng khi M thay đổi trên nửa đường tròn thì điểm N luôn thuộc một nửa đường tròn cố định.

Cho tam giác ABC nội tiếp đường tròn tâm O. Các đỉnh B, C cố định còn đỉnh A thay đổi trên đường tròn đó. Vẽ hình bình hành ABCD. Chứng minh rằng điểm D luôn thuộc một đường tròn cố định.

Cho đường thẳng d và hai điểm A, B cùng thuộc một nửa mặt phẳng bờ d. Hai điểm E, F thay đổi trên d sao cho $\overrightarrow{EF}$ không đổi. Xác định vị trí của hai điểm E, F để AE + BF nhỏ nhất.

Trong mặt phẳng tọa độ Oxy, cho đường tròn (C): (x – 1)² + (y + 2)² = 9. Phép vị tự tâm O(0; 0) với tỉ số k = – 2 biến đường tròn (C) thành đường tròn (C'). Viết phương trình đường tròn (C').

Trong mặt phẳng tọa độ Oxy, cho đường tròn (C): x² + y² – 2x – 4y – 4 = 0. Viết phương trình của đường tròn (C') là ảnh của đường tròn (C) qua phép đối xứng tâm A(3; – 3).

Trong mặt phẳng tọa độ Oxy, cho đường thẳng d: 2x – y + 5 = 0. Viết phương trình đường thẳng d' là ảnh của đường thẳng d qua phép tịnh tiến theo vectơ $\overrightarrow{u}\left(-3;4\right)$.

Trong mặt phẳng tọa độ Oxy, cho đường thẳng ∆: 2x – y – 1 = 0 và hai điểm A(– 1; 2), B(– 3; 4).

a) Tìm tọa độ điểm A' là ảnh của điểm A qua phép đối xứng trục ∆.

b) Xác định điểm M thuộc đường thẳng ∆ sao cho MA + MB đạt giá trị nhỏ nhất.

Hai hình ℋ  và ℋ ' trong Hình 1.52 được vẽ trên mặt phẳng tọa độ Oxy. Bằng quan sát, hãy chỉ ra một phép đối xứng trục f và một phép vị tự g sao cho phép đồng dạng có được bằng cách thực hiện liên tiếp hai phép f và g (thực hiện f trước, g sau) biến hình ℋ  thành hình ℋ '.

Trong mặt phẳng tọa độ Oxy, cho phép biến hình f biến mỗi điểm M(x; y) thành điểm M'(3x; – 3y).

a) Tìm ảnh của các điểm O(0; 0), N(2; 1).

b) Chứng minh rằng f là một phép đồng dạng. Tìm tỉ số đồng dạng.

Một phép đồng dạng biến ba đỉnh A, B, C của tam giác ABC tương ứng thành A', B', C'. Chứng minh rằng

$\frac{BC}{B\text{'}C\text{'}}=\frac{CA}{C\text{'}A\text{'}}=\frac{AB}{A\text{'}B\text{'}}$.