분수색소

분수 색소는 분수 그래프 이론으로 알려진 그래프 이론의 어린 가지에 있는 주제다.일반 그래프 컬러링의 일반화다.전통적인 그래프 컬러링에서, 그래프의 각 꼭지점에는 약간의 색상이 할당되며, 인접한 꼭지점(가장자리로 연결된 꼭지점)에는 다른 색상이 할당되어야 한다.그러나 부분 컬러링에서 색상 집합은 그래프의 각 꼭지점에 할당된다.인접 정점에 대한 요건은 여전히 유지되므로 두 정점이 가장자리로 결합되는 경우 공통적인 색상이 없어야 한다.

부분 그래프 색상은 전통적인 그래프 색상의 선형 프로그래밍 완화로 볼 수 있다.사실, 소수 색채 문제는 전통적인 색채 문제보다 선형 프로그래밍 접근법에 훨씬 더 잘 적응한다.

정의들

그래프 G의 b-폴드 색상은 인접 정점이 분리 집합을 수신하도록 그래프의 정점에 b 크기의 집합을 할당하는 것이다.a:b-색상은 사용 가능한 색상으로 b-폴드 색상을 말한다.동등하게 Kneser 그래프 KG에_a,b 대한 동형성으로 정의할 수 있다.b-폴드 색도수 ${\displaystyle \chi }$ b${\displaystyle {}_{}}$( G${\displaystyle }$) ${\displaystyle \chi _{b}(G)}$는 a:b-coloring이 존재할 수 있는 최소값이다.

분수 색도 번호 ${\displaystyle \chi }$ f${\displaystyle {}_{}}$( G${\displaystyle }$) ${\displaystyle \chi _{f}(G)}$은(는) 다음과 같이 정의된다$$.

${\displaystyle \chi _{f}(G)=\lim _{b\to \inflt }{b}}{b}=\inf _{b}{b}{b}}}}}}$

Note that the limit exists because ${\displaystyle \chi _{b}(G)}$ is subadditive, meaning ${\displaystyle \chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G).$$}$

분수 색도 숫자는 확률론적 용어로 동등하게 정의될 수 있다.${\displaystyle {\chi }_{}}$ ${\displaystyle f_{}}$( ${\displaystyle G}$) ${\displaystyle \chi _{f}(G)}$은 G의 독립된 집합에 대해 확률 분포가 존재하는 가장 작은 k로, 분포에서 추출된 독립된 집합 S가 주어진다.

${\displaystyle \Pr(v\in S)\geq {\frac {1}{k}}.}$

특성.

우리는 가지고 있다.

${\displaystyle \chi _{f}(G)\geq {\frac {n(G)}{\alpha(G)},}$

$\displaystyle \omega(G)\leq \chi _{f}(G)\leq \chi(G),}$

여기서 n(G)은 G의 순서, α(G)는 독립 번호, Ω(G)은 클릭 번호, $\chi {\displaystyle (}$G${\displaystyle )}$는 χ(${\displaystyle G}$ ) ${\displaystyle \chi(G)}$은 색도 번호다.

또한, 부분 색도 숫자는 로가리듬 인자 내의 색도 숫자에 근사하다.^[1] 사실:

${\displaystyle {\frac {\ln(G)}{1+\ln \alpha(G)}\leq \chi _{f}(G)\leq {\frac}{b}}}}\leq \chi(G)}}$

Kneser graphs give examples where ${\displaystyle \chi (G)/\chi _{f}(G)}$ is arbitrarily large, since ${\displaystyle \chi (KG_{m,n})=m-2n+2,}$ while ${\displaystyle \chi _{f}(KG_{m,n})={\tfrac {m}{n}}.$$}$

선형 프로그래밍(LP) 공식

그래프 G의 분수$$ 색도수 ${\displaystyle {\chi }_{}}$ f${\displaystyle {}_{}}$( ${\displaystyle G}$) ${\displaystyle \chi _{f}(G)}$는 선형 프로그램에 대한 해결책으로 얻을 수 있다.Let $I{\displaystyle \mathcal{}}$( ${\displaystyle G}$) ${\displaystyle {\mathcal {I}(G)}$은(는) 모든 독립된 G 집합의 집합이고$$, $I{\displaystyle \mathcal{}(G}$, x${\displaystyle }$) ${\displaystyle {\mathcal {I}(G,x)$은 정점 x를 포함하는 모든 독립 집합의 집합이 되도록$$ 한다.각 독립형 집합 I에 대해 음수가 아닌 실제 변수_I x를 정의하십시오.그러면 $\chi {\displaystyle {}_{}}$ ${\displaystyle f_{}}$( ${\displaystyle G}$) ${\displaystyle \chi _{f}(G)}$은(는)의 최소값이다$$.

${\displaystyle \sum _{I\in {\mathcal {I}(G)}x_{I}}$

의 대상이 되다

${\displaystyle \sum _{I\in {\mathcal {I}(G,x)}x_{I}\geq 1}$

각 $꼭지점{\displaystyle }$ x ${\displaystyle x}$에 대해 $.$

이 선형 프로그램의 이중은 클라이크 숫자의 정수 개념의 합리성에 대한 이완인 "프랙탈 클라이크 숫자"를 계산한다.즉, 어떤 독립된 집합에 할당되는 총 중량이 최대 1이 되도록 G 정점의 가중치를 부여한다.선형 프로그래밍의 강력한 이중성 정리는 두 선형 프로그램에 대한 최적 솔루션이 동일한 값을 갖는 것을 보장한다.그러나 각 선형 프로그램은 G의 정점 수가 기하급수적으로 큰 크기를 가질 수 있으며, 그래프의 부분 색도 수를 계산하는 것은 NP-hard라는 점에 유의한다.^[2]이는 다항식 시간에 해결할 수 있는 그래프의 가장자리를 부분적으로 채색하는 문제와 대조적이다.이것은 에드몬드의 일치 폴리토프 정리의 직접적인 결과물이다.^[3][4]

적용들

부분 그래프 색상의 적용에는 활동 스케줄링이 포함된다.이 경우 그래프 G는 충돌 그래프로서, 노드 u와 v 사이의 에지는 u와 v가 동시에 활성화될 수 없음을 나타낸다.그렇지 않으면 동시에 활성화된 노드 집합은 그래프 G에 독립된 집합이어야 한다.

그런 다음 G의 최적 부분 그래프 색상은 각 노드가 총 1회 단위 동안 활성화되고 어느 시점에서든 활성 노드 집합이 독립된 집합이 되도록 가능한 가장 짧은 일정을 제공한다.위의 선형 프로그램에 대한 솔루션 x가 있다면, 우리는 임의의 순서로 모든 독립된 세트 I을 그냥 통과시킨다.각 I에 대해 i의 노드를 ${\displaystyle {활성화}_{}}$하여 $x{\displaystyle {}_{}}$ I ${\$$I}$ 시간$$ 단위. 한편 I에 없는 각 노드는 비활성 상태임.

좀 더 구체적으로 말하면, G의 각 노드는 무선 통신 네트워크에서 무선 전송을 나타낼 수 있다; G의 가장자리는 무선 전송 사이의 간섭을 나타낸다.각 무선 전송은 총 1회 단위 동안 활성화되어야 한다. 최적의 부분 그래프 색상은 최소 길이 일정(또는 동등하게, 최대 대역폭 일정)을 제공하며, 충돌은 없다.

기존 그래프 색상과 비교

만약 각 노드가 1회 단위 동안 연속적으로 활성화되어야 한다고 추가로 요구한다면, 전통적인 그래프 정점 색상은 최적의 일정을 제공할 것이다: 먼저 1회 단위에서 컬러 1의 노드가 활성화되고, 1회 단위에서는 컬러 2의 노드가 활성화된다.다시 말하지만, 어느 시점에서든 활성 노드 집합은 독립된 집합이다.

일반적으로 부분 그래프 색상은 비수축 그래프 색소보다 짧은 일정을 제공한다. 통합성 차이가 있다.무선 송신기와 같은 전환 장치의 비용(무선 송신기)을 두 번 이상 켜거나 끄면 더 짧은 일정을 찾을 수 있을 것이다.

메모들

참조

• Scheinerman, Edward R.; Ullman, Daniel H. (1997), Fractional graph theory, New York: Wiley-Interscience, ISBN 978-0-471-17864-4.
• Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, New York: Springer-Verlag, ISBN 978-0-387-95241-3.

참고 항목

• 분수 일치