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

CÁC PH ƯƠNG PHÁP BIỂU DIỄN ĐỒ THị 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 đượ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},. | Giáo án môn Lý Thuyết Đô Thị Chương 2 CÁC PH ƯƠNG PHÁP BIỂU DIỄN ĐỒ THỊ 6 tiết 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 ve 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 e 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. Nếu e u u e 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 e 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ễn hình học như sau V1 ĩ v3 v4 v2 Đồ thị có hướng G vi V2 V3 V1 V1 V1 V2 V2 V3 V3 V1 V3 V2 được biểu diễn hình học như sau v2 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. 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 ịa 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 E aij 0 nếu vi Vj Ể E i j 1 2 . n Ví 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à 13 Nguyễ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 0 Ví dụ 3 Cho đồ thị vô hướng G như sau 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 0 Chú ý 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ác nhau 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 aj i j 1 2 . n là các phần tử của ma