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ộ tùy ý của các nút. Do đó có thể chứa một số lượng tùy ý 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 lũy 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 thủy 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 thủy đô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à ("x1", "e1") được nối với cạnh nếu và chỉ nếu đỉnh "x1" chứa trong cạnh "e1" 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 thủy 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 thủy được che phủ bằng một vài siêu đồ thị) và đồ thị nguyên thủy 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"n" − 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 hóa 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
 Có một số nghiên cứu về hypergraphs như cung cấp các hình thức tự nhiên và thống nhất để đối phó với hầu hết các vấn đề phát sinh trong công việc phân tích Functional Dependencies trong RDB
 Một tập hợp F của FD trên các thuộc tính thiết lập tồn tại, có thể được đại diện bởi một Hypergraph H = (V,E) với V = N và E = {(X, Y)\X; F(X,Y F, Y }. Nó rất là dễ dàng để thấy rằng một B là một con đường trên H, nó tương đương với một chuỗi các tác động dựa trên nguyên tắc (°). Ví dụ B – con đường của hình bên dưới tương ứng 
 Với gốc F{ 1, 2, 3, 4 }, {9, 10} bắt đầu từ mối quan hệ ý nghĩa.
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 hóa 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 họa 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.