wiki_research

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

dual_graph (448B)

      1 # Dual graph
      2 
      3 An [undirected_graph] constructed from a [CNF]:
      4 - [vertices] are [clauses]
      5 - [edges] connect two [clauses] that share a [variable]
      6 
      7 if [conjunctive_normal_form] has unbounded [degree] then contains a large [clique]
      8 
      9 There is also a notion of dual graph for [planar_graphs], cf https://en.wikipedia.org/wiki/Dual_graph
     10 
     11 Up: [graph_undirected] of [conjunctive_normal_form]
     12 
     13 See also: [primal_graph], [incidence_graph], [dual_treewidth]