평활화를 통해 주어진 그래프에 동종 형으로 가장 작은 그래프 생성
동 종파 클래스 $ \mathcal{H}(G) $ 그래프 $G$ 토폴로지 적으로 동종인 그래프의 동형 클래스 집합입니다. $G$. 다음과 같은 질문은 당연합니다. 동종 형성 클래스에 "가장 작은"대표자가 있습니까? 그렇다면 어떻게 찾을 수 있습니까? 불행히도 빠른 Google 검색 후이 문제에 대한 유용한 결과를 찾지 못했습니다.
그럼에도 불구하고 직감에 따라 다음과 같은 가설이 있습니다.
그래프에 동종인 가장 작은 그래프는 모든 최대 귀를 부드럽게하여 얻습니다.
이 포스트에서는 증명을 스케치하려고하는데 증명에 틈이있어서 제 가설이 실제로 옳은지 모르겠습니다. 내 실수를 지적하고 공백을 채워 주신 분들께 감사드립니다.
경고 : 이것은 긴 게시물입니다.
먼저 몇 가지 용어를 정리해 보겠습니다. "귀"라는 용어는 그래프 이론 교과서마다 다른 것을 의미합니다. 이 게시물에서는 다음 정의를 채택합니다.
정의 1
그래프의 귀는 다음 중 하나입니다.
- 하나의 정점을 제외한 모든 것이 각도 인주기 $2$, 또는
- 모든 내부 정점이 각도 인 경로 $2$.
최대 귀는 더 큰 귀의 적절한 부분 그래프가 아닌 귀입니다. 마찬가지로 최대 귀는 다음 중 하나입니다.
- 자체적으로 전체적으로 연결된 구성 요소 인주기
- 정확히 하나의 꼭지점이 정도 인주기 $ \geq 3 $, 다른 모든 정점은 차수입니다. $2$
- 모든 내부 정점이 차수인 경로 $2$, 양쪽 끝 정점이 각도 $ \neq 2 $
그래프에서 토폴로지를 유지하는 두 가지 일반적인 작업은 세분화 및 평활화입니다.
정의 2
가장자리를 세분화한다는 것은 귀로 대체하는 것을 의미합니다. 더 정확하게는$e = uv$ 가장자리가 되십시오.
만약 $u = v$, 다음 자체 루프 세분화 $e$ 주기로 교체하는 것을 의미합니다. $C$, 및 $u = v$ 의 정점이됩니다. $C$, 학위가 있거나 없을 수 있습니다. $2$, 여부에 따라 $e$ 격리되어 있습니다.
반면에 $u \neq v$, 세분화 $e$ 경로로 대체하는 것을 의미합니다. $P$, 및 $u, v$ 끝 정점이된다 $P$.
그래프를 세분화한다는 것은 가장자리에서 일련의 세분화를 미리 형성하는 것을 의미합니다.
정의 3
귀를 매끄럽게하는 것은 귀를 단일 모서리로 교체하는 것을 의미합니다. 더 정확하게는$C$ 귀가 되십시오.
만약 $C$ 순환이고 매끄럽게 $C$ 자체 루프로 대체하는 것을 의미합니다. $e$및 도의 꼭지점 $ \neq 2 $ 의 위에 $C$ 유일한 정점 사건이됩니다 $e$ (모든 정점이 $C$ 정도이다 $2$, 아무 정점이나 선택하십시오).
반면에 If $C$ 실제로 경로입니다 $P$, 스무딩 $P$ 루프가없는 가장자리로 교체하는 것을 의미합니다. $e$및 끝 정점 $P$ 끝 정점이된다 $e$.
그래프를 매끄럽게하는 것은 귀를 매끄럽게하는 순서를 미리 형성하는 것을 의미합니다.
다음으로, 그래프 토폴로지에 대한 다음과 같은 고전적인 결과가 있습니다.
정리 1
두 그래프는 다른 하나에 대한 세분화 및 평활화 작업 시퀀스에서 하나를 얻을 수있는 경우에만 동종입니다.
증거 : 이 게시물을 참조하십시오 .
정리 2
허락하다 $G$ 과 $H$두 개의 동종 그래프입니다. 그때$ |V(G)| = |V(H)| $ 경우에만 $ |E(G)| = |E(H)| $.
증명 스케치 : 세분화 (각각 스무딩)는 항상 정점과 가장자리의 수를 같은 수만큼 증가 (감소)합니다.$\square$
정리 2에 비추어, 그래프의 동종 성 클래스에 대한 순서를 정의 할 수 있습니다.
정의 4
허락하다 $ \mathcal{H}(G) $ 그래프의 동종 성 클래스 $G$. 주문 정의$\preceq$ 의 위에 $ \mathcal{H}(G) $ 으로: $$ G_1 \preceq G_2 \iff |V(G_1)| \leq |V(G_2)| $$ 어떠한 것도 $ G_1, G_2 \in \mathcal{H}(G) $.
만약 $ G_1 \preceq G_2 $ 과 $ G_2 \preceq G_1 $, 그러면 우리는 $ G_1 \sim G_2 $.
주문 $\preceq$전 이적이며 두 개의 동종 그래프가 비교할 수 있음을 의미합니다. 불행히도 총 주문이 아닙니다.$ G_1 \sim G_2 $ 암시하지 않는다 $ G_1, G_2 $ 정리 2를 통해서도 동형은 $ |E(G_1)| = |E(G_2)| $.
정리 3
분리 된 정점이없는 모든 그래프는 최대 귀의 가장자리 분리 결합으로 고유하게 분해 될 수 있습니다.
증거 스케치 :
허락하다 $G$분리 된 정점이없는 그래프입니다. 관계 정의$R$ 의 위에 $E(G)$ 으로: $$ eRf \iff \exists \text{ ear } C \subseteq{G} \text{ s.t. } e, f \in E(C) $$ 어떠한 것도 $ e, f \in E(G) $.
그때 $R$ 에 대한 등가 관계 $E(G)$, 여기서 각 등가 클래스는 정확히 하나의 최대 귀의 가장자리를 포함합니다. 그러므로,$R$ 분해를 유도 $G$최대 귀의 가장자리가 분리 된 결합으로. 반대로, 그러한 분해는 다음에 의해 유도되어야합니다.$R$이므로 분해가 고유합니다. $\square$
위의 분해를 기반으로 다음을 정의 할 수 있습니다.
정의 5
모든 최대 귀가 길이 인 경우 격리 된 꼭지점이없는 그래프를 매끄럽게라고합니다. $1$. 그래프의 경우$G$ 고립 된 꼭지점없이 모든 최대 귀를 부드럽게하여 얻은 부드러운 그래프 $G$ 다음과 같이 표시됩니다. $ \text{Smooth} (G) $.
"부드러운 그래프"라는 용어는 표준이 아니지만 이러한 그래프에 대한 기존 용어를 찾을 수 없어서 스스로 구성합니다.
정리 4
허락하다 $G$ 고립 된 정점이없는 부드러운 그래프 $ H \in \mathcal{H}(G) $, 다음 $ G \preceq H $. 게다가,$ G \sim H $ 경우에만 $H$ 부드러운 그래프입니다.
증거 스케치 :
정리 1에 의해, $H$ 일련의 세분화 및 평활화 작업에서 얻을 수 있습니다. $G$. 작업의 각 단계는 최대 귀 중 하나를 가능한 다른 길이의 다른 최대 귀로 만 변경할 수 있습니다.
반면에 부드러운 그래프에서 모든 최대 귀는 이미 가능한 가장 짧은 길이 (즉, $1$), 따라서 세분화 및 스무딩 시퀀스는 정점 수를 더 이상 줄일 수 없습니다. 그러므로,$ |V(G)| \leq |V(H)| $ 평등은 $H$ 부드럽습니다. $\square$
다음 주장은 직관에 근거한 것이지만 어떻게 증명해야할지 모르겠습니다. 내 전체 증거의 차이가있는 곳입니다.
클레임 0
허락하다 $G$ 과 $H$분리 된 정점이없는 두 개의 부드러운 그래프입니다. 동형 인 경우 동형입니다.
마지막으로 위의 주장을 가정하면 주요 가설을 증명할 수 있습니다.
주요 가설
클레임 0이 정확하다고 가정하고 $G$분리 된 정점이없는 그래프입니다. 그때$ \text{Smooth} (G) $ 유일한 가장 작은 그래프입니다 $ \mathcal{H} (G) $ 주문과 관련하여 $ \preceq $.
증명:
사실 그 $ \text{Smooth} (G) \preceq H $ 모든 $ H \in \mathcal{H} (G) $ 정리 4에서 이어집니다.
독창성을 증명하기 위해 $ H \in \mathcal{H} (G) $ 그렇게 될 $ \text{Smooth} (G) \sim H $. 이후$ \text{Smooth} (G) $ 부드럽고 $ H \in \mathcal{H} (\text{Smooth} (G)) $, 정리 4에 의해, $H$부드럽습니다. 클레임 0은 다음을 의미합니다.$H$ 동형이다 $ \text{Smooth} (G) $. $\square$
질문 :
- 클레임 0이 맞습니까? 그것을 증명하는 방법?
- 클레임 0이 틀린 경우에도 내 주된 가설이 여전히 옳습니까?
- 내 증명에 다른 실수가 있습니까?
- 모든 최대 귀가 길이 인 그래프에 대한 더 나은 용어가 있습니까? $1$, "부드러운 그래프"외에?
답변
당신의 증거는 나에게 맞는 것 같습니다. 그래프에 고립 된 꼭지점이 없다고 가정하는 이유를 모르겠습니다. 어디에서나 차이가 있습니까? 또한 "부드러운 그래프"는 2 차 정점이없는 그래프의 멋진 이름 인 것 같습니다. (더 정확하게는 2 차 정점은 루프가있는 분리 된 정점뿐입니다.)
당신의 주장에 대한 증거를 드릴게요. 문제의 그래프가 연결되어 있고 가장자리가 하나 이상 있다고 가정 할 수 있습니다. 모든 그래프$G$, 정점 색상 그래프 연결 $Ear(G)$ 다음과 같은 방식으로 :
- 의 정점 $Ear(G)$ 독특한 분해의 귀에 해당 $G$최대 귀로. 귀가 경로인지 순환인지에 따라 파란색과 빨간색으로 표시됩니다.
- 해당 귀에 공통 정점이 있으면 두 정점이 인접 해 있습니다. 두 개의 공통 정점이 있으면 두 개의 평행 모서리를 그립니다. (해당 귀가 경로 인 경우에만 발생할 수 있습니다.)
정리 4의 증명에 어느 정도 암시적인 두 가지 관찰이 있습니다.
- 만약 $G$ 과 $H$ 동종인 경우 $Ear(G)$ 과 $Ear(H)$동형은 정점 색상을 유지하는 동형입니다. 이것은 평활화와 세분화 모두가$Ear(G)$.
- 만약 $G$ 부드럽습니다 (색상은 무시) $Ear(G)$그냥 선 그래프 입니다$G$, 루프 및 다중 간선이있는 그래프에 적합하게 정의됩니다.
편리하게도 Whitney의 정리는 두 개의 연결된 단순 그래프의 선 그래프가 동형 인 경우 그래프가 삼각형 인 경우를 제외하고는 그래프 자체가 동형이라고 말합니다.$K_3$ 그리고 발톱 $K_{1,3}$. 삼각형은 부드럽 지 않습니다. 루프와 평행 모서리가있는 그래프의 경우 상황이 더 복잡합니다 ( 이 기사 에 따르면 끔찍하지는 않지만 페이 월 링크 만 찾을 수있었습니다. 재미있게도 Whitney의 이름이 제목에 잘못 표기되어 있습니다). 하지만 우리의 경우에는 정점 채색과 정리 4가 원래 그래프를 고유하게 재구성하기에 충분한 정보를 제공합니다. 당신은 아마도 이것을 스스로 분류 할 수있을 것이다. 그러나 나는 완전성을 위해 세부 사항을 줄 것이다.
그래서 가정 $G$ 과 $H$ 부드럽고 $Ear(G)$ 과 $Ear(H)$동형입니다. 먼저 루프를 다룹니다.이 루프는 정확히 다음의 빨간색 정점에 해당합니다.$Ear(G)$ 과 $Ear(H)$. 다음과 같이 표시하면$G'$ 과 $H'$ 루프를 삭제하여 얻은 그래프 $G$ 과 $H$, 다음 $Ear(G')$ 과 $Ear(H')$ 빨간색 정점을 삭제하여 얻습니다. $Ear(G)$ 과 $Ear(H)$; 특히 동형입니다. 이제 그것을 보여주는 것으로 충분합니다$G'$ 과 $H'$ 루프의 위치는 다음과 같이 고유하게 결정되므로 동형입니다. $Ear(G)$: 정점 $G'$ 빨간색 정점에 인접한 가장자리가 입사하는 경우에만 루프가 있습니다. $Ear(G)$, 또는 $G'$ 이 단일 정점으로 구성됩니다 (그래프에 가장자리가 하나 이상 있다고 가정 했으므로).
따라서 우리는 $G$ 과 $H$루프가 없습니다. 이제 평행 모서리 만 처리하면됩니다. 두 모서리가 평행 한 경우$G$, 그런 다음 구성에 따라 해당 정점을 $Ear(G)$두 개의 평행 한 모서리로 연결됩니다. 보다 일반적으로 두 개 이상의 평행 모서리$G$ 파벌에 해당 $Ear(G)$모든 가장자리가 두 배가됩니다. 모든 정점$Ear(G)$ "이중 파벌"(잠재적으로 크기 1)과 같은 고유 한 최대 값에 포함되며, 이러한 파벌을 축소하고 새로 형성된 평행 모서리를 단일 모서리로 대체하여 기본 그래프의 선 그래프를 얻습니다. $G$. 이것은 거꾸로도 작동하기 때문에 (즉, 간단한 그래프와$Ear(G)$ 우리는 회복 할 수있다 $G$), 우리는 $G$ 과 $H$ 간단합니다.
그래서 우리는 휘트니의 정리로 끝났습니다. 맞죠? 글쎄, 그렇게 빠르지는 않습니다. 루프와 평행 가장자리를 떠난 후$G$ 과 $H$, 우리는 삼각형과 $K_{1,3}$: 결국 모서리가 두 배인 삼각형이 부드럽습니다. 그러나 이것은 Theorem 4에 의해 배제되었습니다.$G$ 과 $H$동일한 수의 정점을 가지며 가장자리를 남겨도 변경되지 않습니다. 그래서$G$ 과 $H$ 실제로 동형입니다.
* 내가 말할 수있는 한,이 기사에서 사용 된 선 그래프의 개념은 여기에 사용 된 것과 다릅니다. 평행 모서리에 해당하는 정점이 여전히 하나의 모서리와 만 연결되어 있다는 점입니다.