典型タグ

2-SAT・含意グラフ

二値選択のclauseを含意辺へ変換し、literalと否定literalのSCC関係から可解性と代入を得る。

この典型を扱う単元: 2-SAT・含意グラフ

検索別名: 2-SAT、implication graph、含意グラフ

未知問からこの典型を見つける手掛かり

扱う対象
  • boolean
  • clause
  • literal
使う手掛かり
  • threshold boolean
  • 二択
  • 少なくとも一方
保つ不変量
  • SCC順
  • 否定literal
求めるもの
  • 充足可能性
  • 具体代入
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: グラフモデルと構造

関連する典型

    学習成果と学習単位

    • 整数変数をthreshold命題列へ符号化し、単調性と二項制約をimplication graphへ張り、SCCから可否と充足割当を復元できる。

      2-SAT・含意グラフで学ぶ

    代表問題

    この典型の考え方を具体的な問題で確かめるための入口です。

    関連問題

    この典型が主タグまたは補助タグとして付いている問題です。