신장 부분 그래프: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) |
Osteologia (토론 | 기여) 잔글 →정의 |
||
3번째 줄:
== 정의 ==
[[무향 그래프]] <math>G</math>의 '''생성나무'''는 <math>G</math>의 모든 꼭지점을 포함하고, [[나무 (그래프 이론)|나무]]를 이루는 <math>G</math>의 [[부분그래프]]이다.
한 그래프에는 수많은 생성나무가 있을 수 있다. 모든 유한 [[연결그래프]]는 적어도 하나의 생성나무가 존재하며, [[선택 공리]]를 가정하면 모든 연결그래프에서는 적어도 하나의 생성나무가 존재한다. 비연결그래프의 경우 생성나무가 존재하지 않는다. (그러나 이 경우 생성숲이 존재한다.)
| |||