Что такое квази-двудольный граф?

[longstreet]

Что такое двудольный граф я понимаю. А что такое квази-двудольный?

С английской Вики не смог разумно перевести и понять: http://en.wikipedia.org/wiki/Quasi-bipartite_graph

-- 13.06.2012, 12:49 --

Правильно ли такое понимание:
это такой граф, в котором все не-листья (вершины, инцидентные более чем одному ребру) попарно не соединены?

[Sender]

По-моему, там ясно сказано, что квазидвудольный граф - это граф, вершины которого разделяются на "терминальные" и "нетерминальные", причём нетерминальные образуют независимое множество (попарно не соединены). Вершины же двудольного графа можно разделить на два независимых множества.

[longstreet]

А терминалы - это которые инцидентны только одному ребру, т.е. "конечные" вершины?