Khái niệm đường đi và chu trình trong lí thuyết đồ thị - Toán 11

Trong một đồ thị G, một dãy cạnh nối tiếp (hai cạnh nối tiếp là hai cạnh có chung một đầu mút) AB, BC, CD, …, MN, NP gọi là một đường đi nối A với P, kí hiệu là ABCD…MNP. Điểm A gọi là đầu đường, điểm P gọi là cuối đường.

Một đường đi qua n cạnh gọi là một đường đi có độ dài n.

Một đường đi là sơ cấp nếu nó không đi qua đỉnh nào hai lần trở lên.

Một đường đi là đơn giản nếu nó không đi qua cạnh nào hai lần trở lên.

Ví dụ minh hoạ:

Một đường đi từ đỉnh A đến đỉnh E là: ABCE.

Một đường đi khép kín (đầu đường trùng với cuối đường) gọi là một chu trình.

Một chu trình qua n cạnh gọi là một chu trình có độ dài n.

Một chu trình là sơ cấp nếu nó không đi qua đỉnh nào hai lần trở lên.

Một chu trình là đơn giản nếu nó không đi qua cạnh nào hai lần trở lên.

Ví dụ minh hoạ:

Cho đồ thị đầy đủ có 4 đỉnh như hình dưới.

Những chu trình sơ cấp có độ dài 3 xuất phát từ đỉnh A là: ABCA, ABDA, ACBA, ACDA, ADBA, ADCA.

Những chu trình sơ cấp có độ dài 4 xuất phát từ đỉnh A là: ABCDA, ABDCA, ACBDA, ACDBA, ADBCA, ADCBA.