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

«Википеди» ирĕклĕ энциклопединчи материал
Перейти к навигации Перейти к поиску
Disambig gray.svg Ку терминăн урăх пĕлтерĕшсем пур, пăхăр Йывăç (пĕлтерĕшсем).
Tree graph

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

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

Каçăсем[тӳрлет | кодне тӳрлет]

  • 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.