Chapter 1: CÁC KHÁI NIỆM CƠ BẢN

Định nghĩa đồ thị - Gọi V ≠ φ là tập đỉnh; E={e=(u,v): u,v∈ V} là tập cạnh; và G = (V,E) gọi là đồ thị. - Nếu mỗi cạnh là một cặp đỉnh không có thứ tự
Nội dung trích xuất từ tài liệu:
Chapter 1: CÁC KHÁI NIỆM CƠ BẢNCHƯƠNG 1CÁC KHÁI NIỆM CƠ BẢN1. Định nghĩa đồ thị- Gọi V ≠ φ là tập đỉnh; E={e=(u,v): u,v∈ V} là tập cạnh; và G = (V,E) gọi là đồ thị.- Nếu mỗi cạnh là một cặp đỉnh không có thứ tự thì gọi là đồ thị vô hướng, ngược lại gọi là đồ thị có hướng. Trong đồ thị vô hướng, nếu cạnh (u,v) thuộc E thì (v,u) cũng thuộc E. Trong đồ thị có hướng cạnh được gọi là cung.- Nếu mỗi cặp đỉnh chỉ tương ứng với một cạnh thì gọi là đơn đồ thị, ngược lại gọi là đa đồ thị.Ví dụ : b c d A E    B f g a e  C D Hình 1: Đồ thị vô hướng Hình 2: Đồ thị có hướngRất nhiều bài toán có thể mô hình hoá bằng đồ thị và giải quyết bằng các thuật toán trên đồthị.Ví dụ:Xếp lịch thi đấu là một đồ thị vô hướng với mỗi đội là đỉnh, hai đội thi đấu với nhau là cạnh.Mạng giao thông là một đa đồ thị có hướng với nút giao thông là đỉnh, đường đi giữa hai nútlà cung. Tương tự việc thiết kế mạng máy tính, mạng viễn thông có thể đưa về bài toán đồ thị.2. Các thuật ngữ- Khuyên: cạnh (cung) e gọi là khuyên nếu e có dạng (v,v).- Cạnh (cung) lặp: là hai cạnh (cung) cùng tương ứng với một cặp đỉnh.- Đỉnh kề: nếu (u,v) là cạnh (hoặc cung) của đồ thị thì v gọi là kề của u. Trong đồ thị vô hướng nếu v kề u thì u cũng kề v, nhưng trong đồ thị có hướng thì không chắc.- Cạnh liên thuộc: Trong đồ thị vô hướng, cạnh e=(u,v) gọi là cạnh liên thuộc với đỉnh u và liên thuộc với đỉnh v.- Bậc của đỉnh: Trong đồ thị vô hướng, số cạnh liên thuộc với v gọi là bậc của đỉnh v, kí hiệu là deg(v). v v Khuyên v2 v2 v1 v1 Ví dụ: Xét đồ thị hìnhCạnh 1,deg(a)=1, deg(b)=deg(c)=4, deg(d)=1, deg(e)=deg(f)=3, deg(g)=0 Cung lặp lặp- Đỉnh cô lập, đỉnh treo: Trong đồ thị vô hướng, đỉnh bậc 0 gọi là đỉnh cô lập , đỉnh bậc 1 gọi là đỉnh treo. 1 Ví dụ: Xét đồ thị hình 1, a là đỉnh treo, g là đỉnh cô lập- Cung vào, ra: Trong đồ thị có hướng, cung e=(u,v) gọi là cung ra khỏi u và là cung vào v.- Bán bậc của đỉnh: Trong đồ thị có hướng, số cung vào v gọi là bán bậc vào của đỉnh v, kí hiệu là: deg-(v), số cung ra khỏi v gọi là bán bậc ra của đỉnh v, kí hiệu là: deg+(v) Ví dụ: Xét đồ thị hình 1, deg-(A)=2, deg-(B)=3, deg-(C)=1, deg-(D)=2, deg-(E)=2 deg+(A)=3, deg+(B)=2, deg+(C)=2, deg+(D)=2, deg+(E)=1- Định lý 1: Trong đồ thị vô hướng thì tổng bậc của tất cả các đỉnh bằng 2 lần số cạnh. ∑ deg(v) v∈V = 2m (m là số cạnh) Chứng minh: Mỗi cạnh e=(u,v) được tính một lần trong deg(u) và một lần trong deg(v) nên trong tổng bậc của các đỉnh, mỗi cạnh được tính hai lần, mà có m cạnh nên suy ra tổng bậc bằng 2m. Ví dụ: đồ thị có n đỉnh, mỗi đỉnh có bậc là 6. Hỏi đồ thị có bao nhiêu cạnh? HD: 6n=2m ⇒ m=3n- Hệ quả: Trong đồ thị vô hướng, số đỉnh có bậc là số lẻ là một số chẵn Chứng minh: Gọi O là tập các đỉnh có bậc là số lẻ, và U là tập các đỉnh có bậc là số chẵn. Ta có: ∑ deg(v) = ∑ deg(v) v∈V ∑ deg(v) = 2m v∈O + v∈U Do ∀ v∈ U, deg(v) chẵn nên ∑ deg(v) ⇒ ∑ deg(v) chẵn v∈U v∈O Do ∀ v∈ O, deg(v) lẻ mà tổng ∑ deg(v) chẵn, nên tổng này phải gồm một số chẵn các v∈Osố hạng ⇒ số đỉnh có bậc là số lẻ là một số chẵn (đpcm).- Định lý 2: Trong đồ thị có hướng, tổng bán bậc ra của tất cả các đỉnh bằng tổng bán bậc vào của tất cả các đỉnh và bằng số cạnh của đồ thị ∑ deg v∈V + (v) = ∑ deg v∈V − (v) = m (m là số cạnh)Chứng minh: Hiển nhiên vì mỗi cung đều ra ở một đỉnh và vào ở một đỉnh khác.3. Đường đi, chu trình, liên thông* Đường đi, chu trình:- Đường đi: Đường đi có độ dài n từ đỉnh v0 đến đỉnh vn là dãy v0, v1, …,vn-1, vn ; với (vi vi+1)∈ E, ∀ i=0,…,n-1. Đường đi có thể biểu diễn bằng một dãy n cạnh (cung): (v0, v1),…, (v1, v2), …, (vn-1, vn). Đỉnh v0 gọi là đỉnh đầu, đỉnh vn gọi là đỉnh cuối ...