Bài 6: Đường đi và Chu trình

Tham khảo Video sau đây :

1.Định nghĩa

Đường đi

• Đường đi từ u với v trong một đồ thị vô hướng là một dãy cạnh e₁, e₂..eₙ của đồ thị sao cho f(e₁) = {x₀,x₁}, f(e₂) = {xₙ₋₁,xₙ} với x₀ = u và xₙ=v

• Khi đồ thị là đơn, ta ký hiệu đường đi này bằng dãy x₀,x₁..xₙ

Chu trình

• Đường đi được gọi là chu trình (cycle/circuit) nếu nó bắt đầu và kết thúc tại một đỉnh (nghĩa là u=v)

• Đường đi hay chu trình gọi là đơn nếu nó không đi qua cugn2 một cạnh quá một lần

Ví dụ

• {a,b,c,e,d} là đường đi có độ dài là 4

  a-b, b-c, c-e, e-d tồn tại cạnh

• {a,b,e,d} không là đường đi.

  b-c không tồn tại cạnh

• {a,b,c,e,a} là một chu trình

  a-b, b-c, c-e, e-a là cạnh

  đỉnh a đầu cuối giống nhau

• {c,e,d,e,c} không phải là một đường đi đơn

  nó là chu trình nhưng không phải đường đi đơn vì :

  => e-d và d-e là một cạnh và xuất hiện 2 lần

📇 Kiến thức Thêm

Nếu 2 đồ thị có các chu trình cùng độ dài k với nhau, với k > 2

=> 2 đồ thị này gọi là đẳng cấu với nhau

Liên thông

Đường đi giữa mọi cặp đình phân biệt của đồ thị gọi là liên thông (connected) ngược lại thì gọi là không liên thông (disconnected)

Ví dụ :

📇 Kiến thức Thêm

Đồ thị không liên thông sẽ bao gồm nhiều đồ thị con liên thông

Các đồ thị con này gọi là thành phần liên thông (connected component)

2. Định lý

Đường đi giữa 2 đỉnh bậc lẻ

Nếu đồ thị G (không quan tâm liên thông hay không) có đúng 2 đỉnh bậc lẻ, chắc chắn sẽ có đường nói 2 đỉnh này

📝 Chứng minh

• TH1 : G liên thông : rõ ràng có đường nối 2 đỉnh bậc lẻ này

• TH2 : G không liên thông: các thành phần liên thông của G là một đồ thị.`

  => Do đó, theo định lý về số đỉnh bậc lẻ => 2 đỉnh này phải thuộc về cùng một thành phần liên thông => có đường nối

Số cạnh của đồ thị

Số cạnh tối đa của một đồ thị không liên thông G gồm n đỉnh là

💡 GHI NHỚ

3.Tính chất

Đồ thị có hướng được gọi là :

Liên thông mạnh	Liên thông yếu	Liên thông một phần
đường đi từ a tới b và từ b tới a với mọi cặp đỉnh a và b của đồ thị	có đường đi giữa 2 đỉnh bất kỳ của đồ thị vô hướng nền	mọi cặp đỉnh a và b bất kỳ, có ít nhất một đỉnh đến được đỉnh còn lại