Biểu_diễn đồ_thị Ma_trận kề Khái_niệm Giả_sử G V E là một đơn đồ_thị có n đỉnh Khi đó ta có_thể biểu_diễn đồ_thị bằng một ma_trận vuông A a cấp n Trong đó a 1 nếu i j E a 0 nếu i j E Quy_ước a 0 với i Tính_chất Nếu nửa tam_giác trên và nửa tam_giác dưới đối_xứng nhau qua đường_chéo chính là đồ_thị vô hướng Ngược_lại nếu có một phần_tử không giống nhau ma_trận có hướng Nếu G là đồ_thị vô hướng thì bậc của đỉnh i bằng tổng phần_tử khác 0 trên hàng i Nếu G là đồ_thị có hướng thì nửa bậc ngoài của đỉnh i bằng tổng các phần_tử khác 0 trên dòng i và nửa bậc trong của đỉnh i bằng tổng các phần_tử khác 0 trên cột i Ưu_điểm và nhược_điểm Ưu_điểm Đơn_giản dễ biểu_diễn Nhìn vào ma_trận ta biết được 2 đỉnh nào kề nhau Biết được bậc của từng đỉnh nếu là đồ_thị đơn Nhược_điểm Không biểu_diễn được những cạnh song_song Ma_trận trọng_số Khái_niệm Cho G V E là đơn đồ_thị có trọng_số Ma_trận trọng_số của G là một ma_trận vuông A a cấp n a w i j nếu i j E a 0 nếu i j E Quy_ước a 0 với i Ưu_điểm Đồ_thị có khuyên vẫn biểu_diễn được Nhược_điểm Đồ_thị có cạnh song_song không biểu_diễn được Ma_trận liên thuộc Khái_niệm Giả_sử G V E là một đồ_thị vô hướng với các đỉnh v v v và các cạnh là e e e Khi đó ma_trận liên thuộc M m kích_thước n x m trong đó m 0 nếu cạnh e không nối với đỉnh v m l nếu cạnh e nối với đỉnh v Giả_sử G V E là một đồ_thị có hướng với các đỉnh v v v và các cạnh là e e e Khi đó ma_trận liên thuộc M m kích_thước n x m trong đó m 0 nếu cạnh e không nối với đỉnh v m l nếu cạnh e đi ra khỏi đỉnh v m l nếu cạnh e đi vào đỉnh v Tính_chất Trong ma_trận của đồ_thị có hướng tổng bậc ra của các đỉnh Tổng bậc vào của các đỉnh Đỉnh Trong ma_trận của đồ_thị vô hướng tổng bậc của tất_cả các đỉnh 2 lần số cạnh Ưu_điểm Nhìn vào ma_trận ta biết được số_lượng cạnh số_lượng đỉnh bậc trong và bậc ngoải của đỉnh đó Biết được hướng của 1 cạnh xuất_phát từ đỉnh nào đi tới đỉnh nào Nhược_điểm Biểu_diễn phức_tạp nếu đồ_thị có số_lượng cạnh nhiều khó biểu_diễn Ma_trận bậc Ma_trận bậc degree matrix là một ma_trận đường_chéo chứa thông_tin về bậc của mỗi đồ_thị Định_nghĩa Cho một đồ_thị formula _ 1 ma_trận bậc formula _ 2 của đồ_thị formula _ 1 mà một ma_trận vuông formula _ 4 được định_nghĩa như sau Tính_chất Ma_trận bậc của đồ_thị chính_quy bậc k có một đường_chéo chứa toàn các hằng_số formula _ 6 Ma_trận dẫn nạp Khái_niệm Ma_trận dẫn nạp hay còn gọi là ma_trận Laplace hoặc ma_trận Kirchhoff_Cho một đồ_thị G với n đỉnh ma_trận dẫn nạp formula _ 7 được định_nghĩa như sau Trong đó formula _ 2 là ma_trận bậc được định_nghĩa như sau formula _ 11 là ma_trận kề được định_nghĩa như sau Từ các điều trên ta được Tính_chất Mọi hàng và mọi cột đều có tổng bằng 0 Nguồn tham_khảo T Sunada_Discrete geometric analysis Proceedings of Symposia in Pure_Mathematics ed by P Exner_J_P_Keating P Kuchment_T_Sunada_A Teplyaev 77 2008 51 86
Biểu_diễn đồ_thị