Một số khái niệm cơ bản của lý thuyết đồ thị

Cho đồ thị. Tìm các khẳng định đúng

• Đồ thị có 8 đỉnh

• Đồ thị có 20 cạnh

• A là đỉnh bậc 3

• ADGBFCHEA là một chu trình sơ cấp của đồ thị

• Đây là một đồ thị liên thông

Một hội nghị có 16 đại biểu. 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ó 4 đại biểu không bắt tay ai hết, có 5 người bắt tay 4 lần, có 6 người bắt tay 6 lần và có 10 người bắt tay 3 lần. Khi đó số lần bắt tay của các đại biểu dự hội nghị là:

(a)  

Cho đồ thị G với 18 đỉnh và 30 cạnh. Biết rằng mỗi đỉnh của đồ thị G đều có bậc 6 hoặc bậc 5. Hỏi G có bao nhiêu đỉnh bậc 5?

(a)  

Cho đồ thị đầy đủ có 5 đỉnh như hình bên. Chọn các khẳng định đúng về chu trình sơ cấp xuất phát từ đỉnh A và có độ dài 5.

• ABCDEA

• ABCDA

• ABDECA

• ABEDCA

• ADCBEA

Cho đồ thị G như hình bên. Chọn các khẳng định đúng:

• Đường đi từ đỉnh A đến C là: AEHC

• Đường đi từ A đến F là: AEBGF

• G có chu trình Euler

• G có 8 đỉnh bậc hai

• G có 16 cạnh