# `Yog.Property.TreeDecomposition`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/property/tree_decomposition.ex#L1)

Represents a tree decomposition of a graph.

A valid tree decomposition satisfies three properties:

1. **Vertex coverage**: The union of all bags equals all vertices of the graph.
2. **Edge coverage**: For each edge `(u, v)`, some bag contains both `u` and `v`.
3. **Running intersection**: For each vertex `v`, the bags containing `v` form a
   connected subtree.

The *width* of a tree decomposition is `max(|bag|) - 1`. The *treewidth* of a graph
is the minimum width over all valid tree decompositions.

## Examples

    iex> td = %Yog.Property.TreeDecomposition{
    ...>   bags: %{0 => MapSet.new([1, 2]), 1 => MapSet.new([2, 3])},
    ...>   tree: Yog.undirected() |> Yog.add_edge_ensure(0, 1, 1),
    ...>   width: 1
    ...> }
    iex> is_struct(td, Yog.Property.TreeDecomposition)
    true

# `bag`

```elixir
@type bag() :: MapSet.t(Yog.node_id())
```

A bag is a set of vertices from the original graph.

# `t`

```elixir
@type t() :: %Yog.Property.TreeDecomposition{
  bags: %{required(non_neg_integer()) => bag()},
  tree: Yog.Graph.t(),
  width: non_neg_integer()
}
```

A tree decomposition struct containing bags, a tree graph connecting bag indices,
and the decomposition width.

# `valid?`

```elixir
@spec valid?(t(), Yog.graph()) :: boolean()
```

Validates that a tree decomposition satisfies all three properties.

## Examples

    iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}])
    iex> {:ok, td} = Yog.Approximate.tree_decomposition(graph)
    iex> Yog.Property.TreeDecomposition.valid?(td, graph)
    true

---

*Consult [api-reference.md](api-reference.md) for complete listing*