리프와 셀프 루프

Question

셀프 루프가있는 노드를 리프 노드로 사용할 수 있습니까? 아니면 리프가 단순한 그래프에 대해서만 정의됩니다 (셀프 루프가없고 다중 에지가 없음)? 나는 답을 찾을 수 없다. 나는 다양한 정의를 찾았지만 아무 것도 대답하지 않았습니다.

Answer 1

루프가있는 그래프는 tree이 아니며주기가있는 그래프입니다. 나뭇잎은 나무에만 정의됩니다.

좀 더 공식적인 방법을 생각해 봅시다. 자체 루프는 정점의 정도에 2를 더하거나 방향성 그래프의 경우에는 1을 외. 외도 모두에 추가합니다. 잎이 outdegree 0 (그리고 indegree 1이지만 tree의 정의에 의해 보장되는) 인 정점이라고 가정하면, self-loop를 가진 정점은 잎이 될 수 없다.