Bài giảng lý thuyết đồ thị - Chương 2

CÁC PH ƯƠNG PHÁP BIỂU DIỄN ĐỒ THị2.1 Biểu diễn bằng hình họcCho đồ thị G = (V, E), khi đó ta có thể biểu diễn G bằng phương pháp hình học như sau: Mỗi v ∈ V ta đặt tương ứng với một điểm trong mặt phẳng, điểm đó gọi là đỉnh của đồ thị. a) Trường hợp G là đồ thị vô hướng, nếu e = (u,v) ∈ V thì trong mặt phẳng, các đỉnh u, v được nối với nhau bởi một cạnh không có hướng. Đồ thị vô hướng G = ({v1, v2, v3, v4},...
Nội dung trích xuất từ tài liệu:
Bài giảng lý thuyết đồ thị - Chương 2 Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞChương 2 CÁC PH ƯƠNG PHÁP BIỂU DIỄN ĐỒ THN (6 tiết)2.1 Biểu diễn bằng hình học Cho đồ thị G = (V, E), khi đó ta có thể biểu diễn G bằng phương pháp hình học như sau:Mỗi v ∈ V ta đặt tương ứng với một điểm trong mặt phẳng, điểm đó gọi là đỉnh của đồ thị. a) Trường hợp G là đồ thị vô hướng, nếu e = (u,v) ∈ V thì trong mặt phẳng, các đỉnh u, v đượcnối với nhau bởi một cạnh không có hướng. Nếu e = (u,u) ∈ V thì tại đỉnh u sẽ có một khuyên. b) Trường hợp G là đồ thị có hướng, Nếu e = (u,v) ∈ V thì trong mặt phẳng sẽ có một cung cóhướng đi từ u đến v. Nếu u = v thì tại đỉnh u sẽ có một khuyên có hướng vào chính nó.Ví dụ 1: Đồ thị vô hướng G = ({v1, v2, v3, v4}, {(v1,v2), (v2,v3), (v2,v4), (v3,v4), (v4,v4)}) được biểu diễnhình học như sau: v1 v3 v4 v2 Đồ thị có hướng G = ({v1, v2, v3}, {(v1,v1), (v1,v2), (v2,v3), (v3,v1), (v3, v2)}) được biểu diễn hìnhhọc như sau: v2 v1 v3 Biểu diễn đồ thị bằng hình học là một cách biểu diễn đơn giản, trực quan nhưng không có nhiều ýnghĩa trong việc xử lý bằng máy tính.2.2 Biểu diễn bằng ma trận kề (liền kề), ma trận trọng số Xét đơn đồ thị vô hướng G = (V,E), với tập đỉnh V = {v1, v2, ..,vn}, tập cạnh E = {e1, e2, .., em}.Ta gọi ma trận kề của đồ thị G là ma trận: A = {aij: i,j = 1,2,...,n}với các phần tử aij được xác định theo quy tắc sau: aij = 1 nếu (vi,vj) ∈ E aij = 0 nếu (vi,vj) ∉ E , i,j = 1, 2, .., nVí dụ 2: Cho đồ thị vô hướng G = ({v1, v2, v3},{(v1,v1), (v1,v2), (v1,v3), (v2,v3)}) Ma trận kề của G là 13NguyÔn Minh §øc - §HQG Hµ Néi Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ V1 v2 v3 v1 1 1 1 v2 1 0 1 v3 1 1 0Ví dụ 3: Cho đồ thị vô hướng G như sau: 1 2 3 4 5 Ma trận kề của G là 1 2 3 4 5 1 0 1 0 1 0 2 1 0 1 0 1 3 0 1 0 1 0 4 1 0 1 0 1 5 0 1 0 1 0Chú ý: Ma trận kề của một đồ thị tuỳ thuộc vào thứ tự liệt kê các đỉnh. Do vậy có tới n! ma trận kề khácnhau của một đồ thị n đỉnh vì có n! cách sắp xếp n đỉnh.Các tính chất của ma trận kề của đồ thị đơn vô hướng: a) Ma trận kề của đơn đồ thị vô hướng n đỉnh là một ma trân vuông đối xứng cấp nxn. b) Tổng các phần tử trên hàng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j). c) Nếu kí hiệu a ijp , i, j = 1,2,.., n là các phần tử của ma trận tích A p = 123 A. A... A p Khi đó a , i, j = 1,2,.., n cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung p ijgian. Ma trận kề của đồ thị đơn có hướng cũng được định nghĩa tương tự, nhưng lưu ý ma trận này làkhông đối xứng.Ví dụ 4: Cho đơn đồ thị có hướng G 2 3 1 14NguyÔn Minh §øc - §HQG Hµ Néi Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ 4 Ma trận kề của G là 1 2 3 4 1 0 1 1 0 2 0 0 0 1 3 0 1 0 0 4 1 0 0 0 Trên đây ta chỉ mới xét các đơn đồ thị, đối với đa đồ thị thì ma trận kề cũng được xây dựng hoàntoàn tương tự, chỉ khác là thay vì ghi 1 vào vị trí aij nếu (vi,vj) là cạnh (cung) của đồ thị, ta sẽ ghi klà số cạnh (cung) nối hai đỉnh vi và vj.Ví dụ 5: Cho đa đồ thị vô hướng G như sau: 3 2 1 ...