Лист и петля

Question

Может ли узел с самоциклом быть листовым узлом? Или, может быть, лист определяется только для простых графов (без самоконтроля, без нескольких ребер)? Я не могу найти ответ. Я нашел разные определения, но нигде не нашел ответа.

Answer 1

Граф с циклом - это не дерево , а граф с циклом. Листья определены только для деревьев.

Давайте рассмотрим более формальный подход. Самостоятельная петля добавляет 2 к степени вершины или 1 к степени и степени в случае ориентированных графов. Если предположить, что лист - это вершина с конечной степенью 0 (и степенью 1, но это гарантировано определением дерева), вершина с самциклом не может быть листом.