Меню
Главная
Случайная статья
Настройки
|
Эта статья тематически связана с вики-проектом «Математика», цель которого — создание и улучшение статей по темам, связанным с математикой. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями.
А точно ли любое дерево является рамочным, а значит и двудольным графом? — infovarius (обс.) 22:58, 12 мая 2020 (UTC)[ответить]
- А в чём сомнение? Любое дерево можно раскрасить в два цвета (начиная с корня каждый нечётный уровень одним цветом, каждый чётный - другим цветом). Вершины одного цвета считаем одной долей, другого цвета - другой долей. Получаем двудольный граф. Или у Вас сомнение, что деревья являются рамочными? Так это по определению - у деревьев НЕТ ОГРАНИЧЕННЫХ ГРАНЕЙ, а потому любая ограниченная грань дерева является четырёхугольником...Jumpow (обс.) 16:48, 14 мая 2020 (UTC)[ответить]
|
|