Graphs of bounded treewidth
Lax119563.TreewidthClasses · concepts/Lax119563/TreewidthClasses.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
For , the class consists of all finite simple graphs of treewidth at most . It is closed under isomorphism, so it is a graph class.
Concept map
Lean source view on GitHub
| 1 | import Lax228581.Treewidth |
| 2 | import Lax871432.GraphClasses |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Graphs of bounded treewidth |
| 7 | type: definition |
| 8 | --- |
| 9 | For , the class consists of all finite simple graphs of treewidth at |
| 10 | most . It is closed under isomorphism, so it is a graph class. |
| 11 | |
| 12 | # Implementation notes |
| 13 | |
| 14 | Tree decompositions and treewidth are those of `Lax228581.Treewidth`, and graph classes those |
| 15 | of `Lax871432.GraphClasses`. Isomorphism invariance holds since an isomorphism carries a tree |
| 16 | decomposition to one with the same tree and bags of the same sizes. |
| 17 | -/ |
| 18 | |
| 19 | open Lax228581.Treewidth Lax871432.GraphClasses |
| 20 | |
| 21 | namespace Lax119563.TreewidthClasses |
| 22 | |
| 23 | /-- An isomorphism `e : F ≃g F'` carries a tree decomposition of `F` to one of `F'` with the |
| 24 | same tree and the images of the bags. -/ |
| 25 | private def mapTreeDecomposition {V W : Type} {F : SimpleGraph V} {F' : SimpleGraph W} (e : F ≃g F') |
| 26 | (D : TreeDecomposition F) : TreeDecomposition F' where |
| 27 | Node := D.Node |
| 28 | nodeFintype := D.nodeFintype |
| 29 | tree := D.tree |
| 30 | isTree := D.isTree |
| 31 | bag i := (D.bag i).map e.toEquiv.toEmbedding |
| 32 | vertex_mem_bag v := by |
| 33 | obtain ⟨i, hi⟩ := D.vertex_mem_bag (e.symm v) |
| 34 | exact ⟨i, Finset.mem_map.2 ⟨e.symm v, hi, by simp⟩⟩ |
| 35 | edge_mem_bag u v huv := by |
| 36 | obtain ⟨i, hu, hv⟩ := D.edge_mem_bag (e.symm.map_adj_iff.2 huv) |
| 37 | exact ⟨i, Finset.mem_map.2 ⟨e.symm u, hu, by simp⟩, Finset.mem_map.2 ⟨e.symm v, hv, by simp⟩⟩ |
| 38 | bag_indices_connected v := by |
| 39 | have h : {i | v ∈ (D.bag i).map e.toEquiv.toEmbedding} = {i | e.symm v ∈ D.bag i} := by |
| 40 | ext i |
| 41 | simp only [Set.mem_ofPred_eq, Finset.mem_map_equiv] |
| 42 | rfl |
| 43 | rw [h] |
| 44 | exact D.bag_indices_connected (e.symm v) |
| 45 | |
| 46 | private theorem hasTreewidthAtMost_congr {V W : Type} {F : SimpleGraph V} {F' : SimpleGraph W} |
| 47 | (e : F ≃g F') (w : ℕ) : HasTreewidthAtMost F w → HasTreewidthAtMost F' w := by |
| 48 | rintro ⟨D, hD⟩ |
| 49 | exact ⟨mapTreeDecomposition e D, fun i => by |
| 50 | simpa [mapTreeDecomposition] using hD i⟩ |
| 51 | |
| 52 | /-- The class `𝒯_k` of finite simple graphs of treewidth at most `k`. -/ |
| 53 | def treewidthClass (k : ℕ) : GraphClass where |
| 54 | Mem F := HasTreewidthAtMost F k |
| 55 | mem_congr := by |
| 56 | rintro V W _ _ F F' ⟨e⟩ |
| 57 | exact ⟨hasTreewidthAtMost_congr e k, hasTreewidthAtMost_congr e.symm k⟩ |
| 58 | |
| 59 | end Lax119563.TreewidthClasses |
| 60 |
Implementation notes
Tree decompositions and treewidth are those of , and graph classes those of . Isomorphism invariance holds since an isomorphism carries a tree decomposition to one with the same tree and bags of the same sizes.
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments