Просмотр кода страницы Equistable graph

'''Equistable graph''' --- эквиустойчивый граф. 

A graph <math>G = (V,E)</math> is '''equistable''' if there is a non-negative
weight function <math>w</math> on <math>V</math> such that a set <math>S \subseteq V</math> satisfies
<math>w(S) = \sum_{v \in S} w(e) = 1</math> if and only if <math>S</math> is maximal stable.
The problem of recognizing equistable graphs in polynomial time is
still open.

A graph <math>G</math> is '''strongly equistable''' if for each set <math>\emptyset
\neq T \subseteq V</math> such that <math>T</math> is not maximal stable, and for
each constant <math>c \leq 1</math>, there is a non-negative weight function <math>w</math>
on <math>V</math> such that <math>w(S) = 1</math> for each maximal stable set <math>S</math>, and <math>w(T)
\neq c. </math>