hypergraph (805B)
1 # Hypergraph 2 3 generalizes [graph] 4 5 ## Basic definitions 6 7 - [vertex] 8 - [hyperedge] 9 - [primal_graph] aka "Gaifman graph" 10 11 ## Classes 12 13 - [hypergraph_uniform] 14 - [hypergraph_reduced] "reduced": no incomparable edges 15 - [hypergraph_laminar]: cf [delpia2018multilinear] 16 - [fagin1983degrees]: degrees of acyclicity 17 - also [degree_of_acyclicity]: [alpha_acyclic], etc. 18 - cyclic hypergraph contains one of: 19 - (k,k-1)-hyperclique: k vertices, each k-1 contains an edge 20 - cf [hypergraph_conformal] 21 - induced k-cycle 22 - [hypergraph_balanced] 23 - [koenig_property] 24 25 ## Problems 26 27 - [hyperclique_detection] / [hyperclique_hypothesis] 28 29 See also: [generalized_hypertree_width], [conjunctive_query], [relational_instance], [simplicial_complex] 30 31 Up: [data_structure], [computer_science] 32 33 Aliases: hypergraphs