wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

primal_graph (608B)


      1 # Primal graph
      2 
      3 An [undirected_graph] defined from a [DNF] or from a [hypergraph] or from a [relational_structure].
      4 
      5 For a [DNF]:
      6 - vertices are variables
      7 - edge connects two variables if they co-occur in a clause
      8 
      9 If the [clause_width] of a [DNF] is unbounded then the primal graph contains arbitrarily large [cliques]
     10 
     11 For a [hypergraph]:
     12 - vertices are vertices
     13 - edge connects two variables if they co-occur in a [hyperedge]
     14 
     15 Likewise for [relational_structures]
     16 
     17 Up: [graph_undirected] for [conjunctive_normal_form]
     18 
     19 See also: [dual_graph], [incidence_graph], [primal_treewidth]
     20 
     21 Aliases: Gaifman graph