Йывăç (графсен теорийĕ)

Ку терминăн урăх пĕлтерĕшсем пур, Йывăç (пĕлтерĕшсем) пăхăр.

Йывăç — это çыхăнуллă тата циклла мар граф[1]. Çыхăнуллă тени тăрăсен хуть те мĕнле мăшăрĕ хушшинче маршрут пуррине пĕлтерет, циклла мар тени — циклсем çуккине. Кунтан, уйрăмман илсен, çакă тухса тăрать: йывăçра аяксен шучĕ тăрăсен шутĕнчен пĕрре чухлă пĕчĕкрех тата хуть те мĕнле икĕ тăрăна та пĕр маршрутпа çеç çыхăнтарма пулать.

Tree graph

Вăрман — йывăçсен йышĕнчен тăрать.

Каçăсем тӳрлет

  • Ton Kloks: Treewidth. Springer-Verlag, Berlin/ Heidelberg 1994, ISBN 3-540-48672-0.
  • A. Yamaguchi, H. Mamitsuka: Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of *Spanning Trees. Springer, Berlin/ Heidelberg 2003, ISBN 3-540-24587-1.

Асăрхавсем тӳрлет

  1. ^ § 13. Определение дерева // Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.. — М.: Наука, Физматлит, 1990. — С. 53. — 384 с. — 22 000 экз. — ISBN 5-02-013992-0.