Lý thuyết đồ thị - Phần 2

Tài liệu tham khảo giáo trình toán rời rạc chuyên đề lý thuyết đồ thị
Nội dung trích xuất từ tài liệu:
Lý thuyết đồ thị - Phần 2 Chương3.Lýthuyếtđồthị 3.2.Biểudiễnđồthị 3.2.1.Cáchìnhthứcbiểudiễn  Biểudiễnhìnhhọc  Biểu diễn hình học là một minh họa trực quan về đồthị,trongđómỗiđỉnhđượccoilàmộtđiểm,còn cạnh (cung) là một đường (kèm theo mũi tên) nối từđỉnhnọđếnđỉnhkia.  Tuy nhiên BDHH có một nhược điểm là không được hỗ trợ bởi các công cụ tính toán (máy tính). Nóchỉgiúpđịnhhướng(trựcquan)chotưduytrên đồthị. 3.2.Biểudiễnđồthị  Danhsáchkề  Làdanhsáchgồm2cột.Cộtđầuliệtkêtấtcảcácđỉnhcủađồthị. Trên mỗi dòng của cột thứ hai lần lượt liệt kê các đỉnh liền kề với đỉnhtươngứngtrongcộtthứnhất.  Mộtcáchlưutrữdanhsáchkềlàdùngcácdanhsáchliênkết,trong đónodeđầutiêncủamỗidanhsáchđượccấttrongmộtmảngđược chỉsốhóabởicácđỉnh.  Vídụ: 1 235 1 2 3 5 3 4 2 135 2 1 3 5 3 124 3 1 2 4 4 356 4 3 5 61 6 5 1246 5 1 2 4 6 2 5 6 45 6 4 5 3.2.Biểudiễnđồthị  Danhsáchcạnh(cung)  Vídụ: 1 3  Danh sách cạnh (cung) của đồ thị có n cạnh (cung) là 1 5 danhsáchgồmndòngvà2 cột.Mỗidòngtươngứngvới 1 2 một cạnh (cung) của đồ thị. 3 4 Trên mỗi dòng, cột đầu ghi 3 4 đỉnh (đỉnh đầu), cột thứ hai ghi đỉnh kề (đỉnh cuối) của 3 2 cạnh,(cung)tươngứng. 1 6 4 6  Một cách lưu trữ danh sách cạnhlàdùngdanhsáchliên 2 5 4 5 kết, trong đó mỗi node tương ứng với một cạnh 2 5 (cung). 5 6 3.2.Biểudiễnđồthị  Matrậnkề  ChoG V, =( E) làmộtđồthịcónđỉnh,trongđótập đỉnhđãđượcsắpthứtự(mãhóatừ1đếnn).  MatrậnkềcủađồthịlàmatrậnA=[aik],trongđó aiklàsốcạnh(cung)nốitừđỉnhthứiđếnđỉnhthứ k.  Mộtsốtínhchấtđơngiảncủamatrậnkề:  Matrậnkềcủamộtđồthịlàmatrậnvuôngcấpn.  Nếuđồthịlàđồthịvôhướngthìmatrậnkềlàmatrậnđối xứng.  Nếuđồthịlàđơnđồthịthìmatrậnkềlàmatrận01.  Vídụ:Đađồthịsau 3 4 0 1 1 2 0 1 0  0 2 0 1 0  2 2 0 1 0 0 A=  1 6 0 0 1 0 3 1 1 1 0 3 0 1   5 Cómatrậnkềlà: 2 0 0 0 1 1 0     Vídụ:Đơnđồthịsau 3 4 0 1 1 0 1 0 0 0 1 0 0 0   0 0 0 1 0 0 1 6 A=  ...