Siêu đồ thị

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  của các đỉnh và một vài cặp  của các siêu đồ thị sao cho  and  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 α.

Đồ thị đối xứng

Hạng  của siêu đồ thị  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 . Hai cạnh  và  được cho là đối xứng nếu ở đó tồn tại tính tự đẳng cấu sao cho . 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ó  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  và  mỗi siêu đồ thị có  ma trận liên thuộc  trong đó: . Chuyển vị  của ma trận liên thuộc định nghĩa một siêu đồ thị  gọi là đối ngẫu của H,  là một tập hợp gồm m-phần tử và  là một tập con gồm n phần tử của . Ta có  và  nếu và chỉ nếu .

Tô Màu Siêu Đồ Thị

Tô màu siêu đồ thị được định nghĩa như sau. Giả sử  là siêu đồ thị sao cho .Sau đó  là màu chính của nếu  và nếu chỉ nếu,tất cả  ở đó tồn tại  sao cho . 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ị , ở đó tồn tại phân hoạch: của tập hợp đỉnh  sao cho siêu đồ thị con  tạo ra bởi  là bắc cầu đối với mỗi , và sao cho: mà  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).

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.