Siêu đồ_thị Trong toán_học một siêu đồ_thị là sự tổng_quát của 1 đồ_thị trong đó một cạnh có_thể nối với bất_kỳ đỉnh nào Về mặt hình_thức một siêu đồ_thị formula _ 1 là một cặp formula _ 2 mà formula _ 3 là một tập_hợp của các yếu_tố được gọi là các nút hay đỉnh và formula _ 4 là một tập_hợp các tập con khác rỗng của formula _ 3 gọi là siêu cạnh hoặc cạnh Do_đó formula _ 4 là một tập_hợp_con của formula _ 7 mà formula _ 8 là power set của formula _ 3 Trong khi cạnh đồ_thị là các cặp nút siêu cạnh là bộ tuỳ_ý của các nút Do_đó có_thể chứa một số_lượng tuỳ_ý các nút Tuy_nhiên nó thường là mong_muốn để nghiên_cứu các siêu đồ_thị nơi mà tất_cả siêu cạnh có cùng hướng một siêu đồ_thị k cùng kiểu dữ_liệu là một siêu đồ_thị như là tất_cả siêu cạnh của nó có kích_thước k Nói cách khác nó là một sự kết_hợp các bộ kích_thước k Vì_vậy siêu đồ_thị có 2 đồng_dạng là một đồ_thị Siêu đồ_thị có 3 đồng_dạng cùng kiểu dữ_liệu là sự kết_hợp tập_hợp tập bộ ba không có thứ_tự và tiếp_tục như_vậy Thuật_ngữ Do các liên_kết của siêu đồ_thị có_thể có bất_kỳ số các yếu_tố trong một tập_hợp có một_vài ký_hiệu của các khái_niệm về một đồ_thị con được gọi là siêu đồ_thị con siêu đồ_thị bộ_phận và siêu đồ_thị phần Cho formula _ 10 là siêu đồ_thị bao_gồm đỉnh và có Nơi formula _ 13 và formula _ 14 là bộ chỉ_số của các đỉnh và các cạnh tương_ứng Một siêu đồ_thị con là một siêu đồ_thị với một_số đỉnh bị loại_bỏ Về mặt hình_thức các siêu đồ_thị con formula _ 15 sinh ra bởi một tập_hợp_con formula _ 16 của formula _ 3 được định_nghĩa là Các phần siêu đồ_thị là một siêu đồ_thị với một_số cạnh bị loại_bỏ Cho một tập_hợp_con formula _ 19 tập_hợp_con của tập chỉ_số cạnh siêu đồ_thị một phần được tạo ra bởi formula _ 20 là siêu đồ_thị Cho một tập_hợp_con formula _ 22 siêu đồ_thị được chọn là siêu đồ_thị bộ_phận Đối_ngẫu formula _ 24 của formula _ 1 là một siêu đồ_thị mà các đỉnh và các cạnh được thay_đổi cho nhau vì_vậy mà các đỉnh được cho bởi formula _ 26 và có các cạnh được cho bởi formula _ 27 Khi một khái_niệm về phép bằng được xác_định đúng như thực_hiện dưới đây phép_toán lấy đối_ngẫu một siêu đồ_thị là một_phép nâng lên luỹ_thừa Một đồ_thị kết_nối G có tập đỉnh giống tập đỉnh của một siêu đồ_thị kết_nối H là một đồ_thị chính của H nếu mỗi siêu đồ_thị H sinh ra một đồ_thị con được kết_nối trong G Đối_với đồ_thị không kết_nối H G là một đồ_thị chính nếu có một song ánh giữa thành_phần kết_nối của G và H sao cho mỗi kết_nối thành_phần G của G là một loạt các tương_ứng với H Một siêu đồ_thị là song_phương hai bên khi và chỉ khi các đỉnh của nó có_thể được phân_chia thành hai loại U và V mà mỗi siêu cạnh với số các yếu_tố trong một tập_hợp ít_nhất 2 chứa tối_thiểu một đỉnh từ cả hai lớp Đồ_thị nguyên_thuỷ của siêu đồ_thị là đồ_thị với đỉnh giống nhau của siêu đồ_thị và các cạnh giữa các cặp đỉnh được chứa trong cùng một siêu cạnh Đồ_thị nguyên_thuỷ đôi_khi còn được gọi là đồ_thị Gaifman_Mô hình đồ_thị song_phương Một siêu đồ_thị H có_thể là đại_diện cho bởi một đồ_thị song_phương BG như sau bộ X và E là phân_vùng của BG Và x e được nối với cạnh nếu và chỉ nếu đỉnh x chứa trong cạnh e trong H Ngược_lại đồ_thị xong phương nào với bộ_phận cố_định và không có các nút không liên_quan trong phần thứ hai đại_diện cho một_số siêu đồ_thị theo cách mô_tả ở trên Đồ_thị song_phương này cũng được gọi là đồ_thị tỷ_lệ Tính không tuần_hoàn Tương_phản với đồ_thị vô hướng thường theo đó có một khái_niệm tự_nhiên của tuần_hoàn và đồ_thị không tuần_hoàn có nhiều định_nghĩa tương_đương không tự_nhiên của tính không tuần_hoàn cho nhiều siêu đồ_thị Định_nghĩa thứ nhất của tính không tuần_hoàn cho nhiều siêu đồ_thị được tính bằng cách lấy Claude_Berge một siêu đồ_thị là không tuần_hoàn Berge nếu nó là đồ_thị liên thuộc đồ_thị song_phương định_nghĩa ở trên là không tuần_hoàn nếu đồ_thị nguyên_thuỷ của nó là không tuần_hoàn Định_nghĩa này là rất hạn_chế ví_dụ nếu siêu đồ_thị có vài cặp formula _ 30 của các đỉnh và một_vài cặp formula _ 31 của các siêu đồ_thị sao cho formula _ 32 and formula _ 33 thì nó là chu_kỳ Berge_Chu kỳ Berge có_thể một_cách rõ_ràng hiển_nhiên là phép thử kiểm_định trong thời_gian tuyến_tính bằng khám_phá đồ_thị liên thuộc Chúng_ta có_thể định_nghĩa khái_niệm yếu của tính không tuần_hoàn siêu đồ_thị chậm hơn số_hạng tính không tuần_hoàn α Khái_niệm này của tính không tuần_hoàn tương_đương với siêu đồ_thị được bảo giác mỗi đẳng phái của đồ_thị nguyên_thuỷ được che_phủ bằng một_vài siêu đồ_thị và đồ_thị nguyên_thuỷ của nó đang có hình sợi dây nó cũng tương_đương đến tính khả quy đến đồ_thị trống_rỗng qua thuật_toán GYO cũng gọi là thuật_toán của Graham_Trong lý_thuyết lĩnh_vực cơ_sở_dữ_liệu ta biết rằng lược_đồ cơ_sở_dữ_liệu thích một_số tính_chất hấp_dẫn nếu siêu đồ_thị bên dưới nó là không tuần_hoàn α Hơn_nữa tính không tuần_hoàn α cũng là liên_quan đến hàm_ý của đoạn được che theo thứ_tự lôgic Chúng_ta có_thể phép thử kiểm_định trong thời_gian tuyến_tính nếu siêu đồ_thị là không tuần_hoàn α Lưu_ý là tính không tuần_hoàn α có tính_chất trái với mong_đợi mà thêm các siêu cạnh vào siêu đồ_thị có chu_trình α có_thể làm nó không tuần_hoàn α chẳng_hạn như cộng vào siêu cạnh chứa toàn_bộ các đỉnh của siêu đồ_thị luôn_luôn làm nó không tuần_hoàn α Thúc_đẩy phần_nào bằng khiếm_khuyết được nhìn_nhận này Ronald_Fagin định_nghĩa khái_niệm mang tính không tuần_hoàn β và tính không tuần_hoàn γ Chúng_ta có_thể phát_biểu rằng tính không tuần_hoàn β khi yêu_cầu toàn_bộ siêu đồ_thị con của siêu đồ_thị là không tuần_hoàn α là tương_đương để định_nghĩa trước_đây bằng Graham_Khái niệm của tính không tuần_hoàn γ là hạn_chế hơn điều_kiện mà tương_đương với vài yêu_cầu của lược_đồ cơ_sở_dữ_liệu và được liên_quan đến đồ_thị Bachman_Cả hai tính không tuần_hoàn β và tính không tuần_hoàn γ có_thể kiểm_định trong thời_gian đa_thức Chúng_ta có_thể phép thử kiểm_định trong thời_gian tuyến_tính nếu siêu đồ_thị là không tuần_hoàn α Phép đẳng_cấu và đẳng_thức Một đồng_cấu Siêu đồ_thị là một xạ ảnh từ tập đỉnh của một Siêu đồ_thị khác như_vậy mà mỗi cạnh của xạ ảnh tới một cạnh khác Một siêu đồ_thị formula _ 10 là đẳng_cấu với một siêu đồ_thị formula _ 35 được viết như formula _ 36 nếu tồn_tại một song ánh và một hoán_vị formula _ 38 của formula _ 39 như_vậy mà Các song ánh formula _ 41 sau đó được gọi là đẳng_cấu của các đồ_thị lưu_ý rằng Khi các cạnh của một siêu đồ_thị được dán nhãn rõ_ràng ta có một khái_niệm bổ_sung đẳng_cấu mạnh Ta nói rằng formula _ 44 là đẳng_cấu mạnh với formula _ 45 nếu hoán_vị là phân_biệt Sau đó người ta viết formula _ 46 Lưu_ý rằng tất_cả các đồ_thị đẳng_cấu mạnh là đẳng_cấu nhưng không phải ngược_lại Khi các đỉnh của một siêu đồ_thị được dán nhãn rõ_ràng chúng_ta có các khái_niệm về tính tương_đương và cũng về phép bằng Ta nói rằng formula _ 1 là tương_đương với formula _ 48 và viết formula _ 49 nếu đẳng_cấu formula _ 41 có và Ghi_chú rằng Ngoài_ra hoán_vị formula _ 38 là đồng_nhất người ta nói rằng formula _ 1 bằngformula _ 48 và viết formula _ 58 Lưu_ý rằng với định_nghĩa về tính tương_đồng đồ_thị là tự đối_ngẫu Một siêu đồ_thị tự đẳng_cấu là một đẳng_cấu từ một tập đỉnh vào chính nó đó là ghi nhãn lại các đỉnh Tập_hợp các tự đẳng_cấu của một siêu đồ_thị H X E là một nhóm thuộc thành_phần được gọi là nhóm tự đẳng_cấu của siêu đồ_thị và được viết thành Aut_H_Ví dụ Xem_xét các siêu đồ_thị formula _ 1 với các cạnh và Thì rõ_ràng formula _ 44 và formula _ 45 là đẳng_cấu với formula _ 65 v v nhưng chúng không phải là đẳng_cấu mạnh Vì_vậy ví_dụ trong formula _ 1 đỉnh formula _ 67 đáp_ứng các cạnh 1 4 và 6 vì_vậy Trong đồ_thị formula _ 48 không tồn_tại bất_kỳ đỉnh đáp_ứng các cạnh 1 4 và 6 Trong ví_dụ này formula _ 44 và formula _ 45 là tương_đương formula _ 73 và các đối_ngẫu là đẳng_cấu mạnh formula _ 74 Đồ_thị đối_xứng Hạng formula _ 75 của siêu đồ_thị formula _ 1 là số_lượng cực_đại của bất_cứ cạnh nào trong Siêu đồ_thị Nếu toàn_bộ cạnh biên có cùng số_lượng k siêu đồ_thị được cho là đồng_dạng hay là đồng_dạng k hay_là được gọi là Siêu đồ_thị k Đây chính_xác là siêu đồ_thị đồng_dạng 2 Độ d v của đỉnh v là số cạnh chứa nó Siêu đồ_thị H gọi là k đều nếu mỗi đỉnh đều có độ k Siêu đồ_thị đối_ngẫu là đều và ngược_lại Hai đỉnh x và y của siêu đồ_thị H được gọi là đối_xứng nếu ở H tồn_tại tính tự đẳng_cấu sao cho formula _ 77 Hai cạnh formula _ 78 và formula _ 79 được cho là đối_xứng nếu ở đó tồn_tại tính tự đẳng_cấu sao cho formula _ 80 Siêu đồ_thị được cho là được bắc_cầu đỉnh hay_là đối_xứng đỉnh nếu tất_cả các đỉnh của nó là đối_xứng Nếu siêu đồ_thị có cạnh song_song và đối_xứng đỉnh thì siêu đồ_thị đó gọi là đối_xứng đơn_giản Vì tính đối_xứng của siêu đồ_thị tính_chất bắc_cầu của cạnh giống như tính_chất bắc_cầu ở các đỉnh Đường Hoành_Đường hoành của hypergraph H X E là tập_hợp có formula _ 81 giao với mỗi cạnh Đường hoành T được gọi là cực_tiểu nếu tập_hợp_con của nó cũng là một đường hoành Siêu đồ_thị đường hoành của H là siêu đồ_thị X F mà tập_hợp cạnh F của nó gồm tất_cả đường hoành cực_tiểu của H Tính_toán siêu đồ_thị đường hoành được ứng_dụng trong tối_ưu_hoá tổ_hợp trí_tuệ_nhân_tạo trong game và vài lĩnh_vực khoa_học máy_tính như là máy học chỉ_số của cơ_sở_dữ_liệu bài_toán thực_nghiệm khai_thác dữ_liệu và tối_ưu_hoá chương_trình tính Ma_Trận Liên_Thuộc_Cho formula _ 82 và formula _ 83 mỗi siêu đồ_thị có formula _ 84 ma_trận liên thuộc formula _ 85 trong đó formula _ 86 Chuyển_vị formula _ 87 của ma_trận liên thuộc định_nghĩa một siêu đồ_thị formula _ 88 gọi là đối_ngẫu của H formula _ 89 là một tập_hợp gồm m phần_tử và formula _ 90 là một tập con gồm n phần_tử của formula _ 89 Ta có formula _ 92 và formula _ 93 nếu và chỉ nếu formula _ 94 Tô_Màu_Siêu_Đồ Thị_Tô màu siêu đồ_thị được định_nghĩa như sau Giả_sử formula _ 95 là siêu đồ_thị sao cho formula _ 96 Sau đó formula _ 97 là màu chính của nếu formula _ 1 và nếu chỉ nếu tất_cả formula _ 99 ở đó tồn_tại formula _ 100 sao cho formula _ 101 Nói cách khác không_thể có siêu cạnh đơn_sắc với bản số_lượng phần_tử tối_thiểu là 2 Các siêu đồ_thị mà có tồn_tại một_cách tô màu sao cho sử_dụng hết k màu được gọi_là tô được k màu Siêu đô_thị tô được 2 màu chính là siêu đồ_thị song_phương Phân hoạch Định_lý phân hoạch của E Dauber phát_biểu như sau cho cạnh biên bắc_cầu của Siêu đồ_thị formula _ 10 ở đó tồn_tại phân hoạch formula _ 103 của tập_hợp đỉnh formula _ 3 sao cho siêu đồ_thị con formula _ 105 tạo ra bởi formula _ 106 là bắc_cầu đối_với mỗi formula _ 107 và sao cho formula _ 108 mà formula _ 75 là hạng của H Hệ_quả là một siêu đồ_thị có cạnh bắc_cầu thì không phải là đỉnh bắc_cầu tô được 2 màu Phân hoạch đồ_thị nói_riêng là phân hoạch siêu đồ_thị có ứng_dụng trong thiết_kế IC và tính_toán song_song Định_lý Nhiều định_lý và khái_niệm liên_quan tới đồ_thị vẫn được áp_dụng cho siêu đồ_thị Một_số phương_pháp nghiên_cứu tính đối_xứng của các đồ_thị được mở_rộng cho siêu đồ_thị Hai định_lý nổi_tiếng là định_lý Erdős_Ko_Rado và định_lý Kruskal_Katona nói về siêu đồ_thị đồng_dạng Vẽ siêu đồ_thị Mặc_dù siêu đồ_thị khó vẽ trên giấy hơn đồ_thị thường nhưng các nhà_nghiên_cứu đã tìm ra phương_pháp cho việc hình_dung về nó Một_cách nhìn trực_quan về siêu đồ_thị tương_tự như cách vẽ của một đồ_thị thường các đường_cong trong mặt_phẳng dùng để vẽ các cạnh Các đỉnh của siêu đồ_thị được vẽ như các điểm hình_tròn hay hình_chữ_nhật và các siêu cạnh được vẽ như cây với lá là các đỉnh Nếu đỉnh được vẽ như các điểm thì siêu cạnh có_thể được biểu_diễn như những đường_cong nối với các điểm đó hoặc những đường_cong khép_kín chứa tập_hợp các điểm Một_cách nhìn khác về siêu đồ_thị chia nhỏ khuôn_mẫu của siêu đồ_thị chia mặt_phẳng thành các vùng mỗi vùng là một siêu cạnh có_thể được đánh_dấu bằng màu_sắc đường viền xung_quanh hoặc cả hai Các đỉnh thì được mô_tả như phần giao nhau của các vùng Một biểu_đồ Venn tập n là một điển_hình có_thể được xem như một phần nhỏ của bức tranh về siêu đồ_thị với n siêu cạnh biểu_diễn bởi các hình cong và 2 1 đỉnh biểu_diễn bởi các vùng được sinh ra do những hình cong cắt nhau Tổng_quát Nhìn_chung siêu đồ_thị cho_phép các cạnh có_thể nối với nhau Có hai cách nhìn về vấn_đề này Một là các cạnh không_chỉ bao_gồm tập_hợp các đỉnh mà_còn có_thể chứa tập con các đỉnh Mỗi phần_tử trong tập_hợp tuân theo một thứ_tự nhưng thứ_tự này không phải partial order mà cũng không phải preorder vì nó không bắc_cầu Đồ_thị đúng với đồ_thị Levi trong cách nhìn này là đồ_thị có hướng và không có chu_trình Xét ví_dụ sau một siêu đồ_thị có tập đỉnh là formula _ 110 và các cạnh formula _ 111 và formula _ 112 Mặc_dù formula _ 113 và formula _ 114 nhưng formula _ 115 thì không đúng Tuy_nhiên tính_chất bao đóng bắc_cầu của các phần_tử trong tập_hợp của siêu đồ_thị đó lại tạo nên thứ_tự riêng phần partial order và chia siêu đồ_thị thành một tập_hợp có thứ_tự riêng phần Lần_lượt một cạnh có_thể được nối với cạnh khác Bất_kể các cạnh có trật_tự theo hướng đồ_thị không chu_trình Điều này cho_phép độ thị có cạnh lặp không cần phải chứa tất_cả các đỉnh Ví_dụ xét một siêu đồ_thị gồm hai cạnh formula _ 116 và formula _ 117 không có đỉnh vì_thế formula _ 118 và formula _ 119 Dẫn đến việc lặp đệ quy vô_tận những tập_hợp mà các cạnh vi_phạm axiom of foundation Cụ_thể là không có tính_chất bao đóng bắc_cầu cho các phần_tử trong tập_hợp thuộc siêu đồ_thị Mặc_dù những cấu_trúc này có_thể trông khác với cái đầu_tiên nhưng chúng có_thể được hiểu một_cách dễ_dàng bởi việc tổng_quát_hoá tương_đương đồ_thị Levi của chúng không còn phân đôi nữa nhưng lại đúng hơn một_số đồ_thị có hướng Ma_trận liên thuộc của siêu đồ_thị này là ma_trận vuông có_hạng bằng tổng_số đỉnh và cạnh Vậy trong ví_dụ trên ma_trận liên thuộc chỉ đơn_giản là Ứng_dụng của siêu đồ_thị Cơ_sở_dữ_liệu quan_hệ Trong những năm qua một số_lượng đáng_kể các nhà_nghiên_cứu đã dành thời_gian và công_sức để nghiên_cứu phân_tích các quan_hệ cơ_sở_dữ_liệu bằng phương_pháp sử_dụng các kỹ_thuật liên_quan đến đồ_thị Một quan_hệ cơ_sở_dữ_liệu RDB thường được thể_hiện bằng một tập_hợp các mối quan_hệ trong một miền giá_trị nào đó cùng với tập_hợp các Functional_Dependencies_Functional_Dependencies đã được nghiên_cứu bằng cách dùng loại đồ_thị tổng_quát chẳng_hạn như FD Graphs_Implication_Graphs_Deduction Graphs_Hay_NBE có các tập thuộc_tính của RDB một sự phụ_thuộc vào chức_năng F X Y với cả hai X và Y đó là tập_hợp_con của N Định_nghĩa duy_nhất của các giá_trị thuộc_tính Y khi giá_trị X được đưa ra Functional_Dependencies có một_số quy_tắc cho_phép chúng_ta lấy thong tin mới_đó lưu_trữ một_cách rõ_ràng trong cơ_sở_dữ_liệu i Reflexivity ii Transitivity if and iii Conjunction_F_X_Y if F X Y F X Z Đấy là một tập_hợp của Functional_Dependencies_F chúng_ta có_thể cần phải giải_quyết các vấn_đề như Tìm xem một Functional_Dependencies cho F X Y có_thể xuất_phát từ F và dựa trên kết_luận của quy_định Cho một tập_hợp các thuộc_tính X ta phải tìm_kiếm điểm kết_thúc của nó so với F tức_là tìm thấy một thiết_lập X như_vậy rằng F X X thuộc về F Thủ_tục B Visit giải_quyết những vấn_đề a và b trong O size H O size F ở một khoảng thời_gian Trong cả hai trường_hợp tập Q được sử_dụng trong B visit được khởi tạo bởi X Cho X là một tập_hợp được ghé thăm bởi Đỉnh B kết_nối tới X Trong vấn_đề a câu trả_lời là một tập_hợp sinh ra bởi F X Y_sinh ra F chỉ khi Y khi và chỉ khi Y X trong khi vấn_đề kia là b khi X X Urban transit application ứng_dụng di_chuyển trong thành_phố Phân_tích quá_trình đi_lại vận_chuyển hành_khách trong một thành_phố luôn là một ứng_dụng thú_vị với mô_hình siêu đồ_thị Ở đây hệ_thống giao_thông được miêu_tả như một mô_hình_hoá mạng_lưới đặc_biệt trong đó những đường vận_chuyển được chồng lên hệ_thống mặt_đất Mỗi dòng chuyển là một_mạch tức_là một trình_tự xen_kẽ các node đại_diện cho các dòng và vòng_cung của một đại_diện trong đoạn đường đi đó Hệ thông đường đi dưới mặt_đất được hình_thành bởi các nút thể_hiện ở vị_trí địa_lý ở trọng_tâm của một khu_vực trong một khu đô_thị và vòng_cung của đó đại_diện cho con đường dành để đi bộ đến được trung_tâm Đổi với mỗi node I đang dừng trên mạng cơ_sở cho Li là một tập_hợp các đường đi sẽ dừng lại ở I Với mỗi node tôi sẽ được kết_nối với các node tương_ứng thuộc đường Li bởi một vòng_cung để lại và một vòng_cung ngược lên phía trên cao Ta có hình minh_hoạ sau đây Từ một quan_điểm của cá_nhân địa_phương có tuyến đường đi đó thì người nào đó ở những trạm dừng chân I đi đến những nơi mà họ muốn đến phải ít tốn_kém về mặt thời_gian và chi_phí Vấn_đề được đặt ra trong các tập con của công_thức sau tập trên được gọi là một tập hấp_dẫn đúng_đắn bởi_vì nó luôn_luôn lên những chuyến xe đầu_tiên đi đến các trạm dừng chân thời_gian di_chuyển dự_kiến sẽ được giảm đi rất là nhiều Nhìn_chung thời_gian di_chuyển trên chuyến xe và thời_gian chờ để đi tiếp quảng đường khác nó sẽ xảy ra trong những nhà chờ xe như_vậy Chuyến đi sẽ được bắt_đầu nếu hành khác đó bỏ tiền ra và leo lên xe ngồi
Siêu đồ_thị