쉬옹나무

쉬옹나무.트리 이외의 가장자리(빨간색 성분)의 한 성분만 이 그래프에 대해 가능한 최소인 홀수 수의 가장자리를 가지고 있다.

그래프 이론에서 쉬옹 트리는 주어진 그래프 $G{\displaystyle }$ ${\displaystyle G}$의 스패닝 $트리{\displaystyle }$ T ${\displaystyle T}$이며, 나머지$$ $그래프{\displaystyle }$ ${\displaystyle G}$- T ${\displaystyle G-T}$에서$$가장자리 수가 홀수인 연결된 성분의 수는 가능한 한 작다.^[1]그것들은 가장 큰 속들을 가진 주어진 그래프의 세포 임베딩을 특징 짓기 위해 Nguyen Huy Shuong의 이름을 따왔다.^[2]

According to Xuong's results, if ${\displaystyle T}$ is a Xuong tree and the numbers of edges in the components of ${\displaystyle G-T}$ are ${\displaystyle m_{1},m_{2},\dots ,m_{k}}$, then the maximum genus of an embedding of ${\displaystyle G}$ is ${\displaystyle \sum _{i=1}^k\lfloor m_i/}$${\displaystyle \textstyle \sum _{i=1}^{k}\lfloor m_{i}/2\rfloor }$.^[1][2] Any one of these components, having ${\displaystyle m_{i}}$ edges, can be partitioned into ${\displaystyle \lfloor m_{i}/2\rfloor }$ edge-disjoint two-edge paths, with possibly one additional left-over edge.^[3]최대 내장은 쉬옹나무의 평면 내장을 통해 각 2개의 가장자리 경로를 내장에 추가하여 내장을 1개씩 증가시키는 방법으로 얻을 수 있다.^[1][2]

쉬옹 나무와 그것에서 파생된 최대 유전자를 포함하는 것은 다항식 시간의 모든 그래프에서 선형 매트로이드에 대한 매트로이드 패리티 문제인 매트로이드에 대한 보다 일반적인 계산 문제로 변환함으로써 찾을 수 있다.^[1][4]

참조