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