1. Дать определение дерева. Показать, что следующее определение эквивалентно определению дерева «граф G ацикличен, но соединяя любую пару вершин новым ребром, получаем цикл».
2. Нарисуйте полный граф K6. Существует ли в нём цикл длины 7?
(ответ аргументировать)
3. Используя алгоритм поиска минимального основного дерева, найдите сеть дорог минимальной общей длины, связывающую все шесть городов (см. следующую страницу).
4. Можно ли раскрасить ребра куба в красный и чёрный цвет так,
чтобы муравей мог пройти из любой вершины в любую, гуляя только по
красным рёбрам, а жук — только по чёрным?

Пошаговое объяснение:

G — дерево.

Любые две вершины графа G соединены единственным простым путем.

G — связен и p=q+1, где p — количество вершин, а q количество ребер.

G — ацикличен и p=q+1, где p — количество вершин, а q количество ребер.

G — ацикличен и при добавлении любого ребра для несмежных вершин появляется один простой цикл.

G — связный граф, отличный от Kp для p>3, а также при добавлении любого ребра для несмежных вершин появляется один простой цикл.

G — граф, отличный от K3∪K1 и K3∪K2, а также p=q+1, где p — количество вершин, а q количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл