구조가있는 랜덤 그래프의 구조
배경
[이것을 건너 뛰고 즉시 정의로 이동할 수 있습니다.]
(랜덤) 그래프 또는 네트워크의 중요한 기능은 다음과 같습니다.
학위 분포 $p(d)$ (지수, 푸 아송 또는 멱 법칙)
평균 정도 $\bar{d}$
평균 군집 계수 $\bar{C}$
평균 거리 $L$ 및 직경 $D$
무작위로 생성 된 그래프는 종종 전시하는 데 필요한 작은 세계의 속성을 , 즉,$L\propto \log N$ 과 $\bar{C}$"작지 않음"입니다. 다음 조건 중 하나 이상을 해결하는 몇 가지 랜덤 그래프 모델이 있습니다.
- 와트 - Strogatz 모델 (정규 기저 링 격자)
- Barabasi - 알버트 모델 (바람직한 첨부)
- 구성 모델 (주어진 시퀀스도, RESP. 분포)
- 뉴먼 모델 (통합 사회 구조 )
Watts-Strogatz와 Barabasi-Albert 모델은 Erdős-Rényi 모델 의 수정이고 Newman 모델은 구성 모델의 특정 일반화이지만,이 모델을 통합하려는 "메타 모델"이 이미 있는지 궁금합니다. 이 모든 모델 중에서 가장 좋습니다. (참조 요청.)
Watts-Strogatz와 Newman의 모델을 모두 일반화하여 "ER 그래프에 가까운 무작위 구조와 [일부 임의의 정규 그래프] " ( Wikipedia 에서 인용 ) 사이를 보간하는 무작위 그래프를 조사하고 싶습니다 .
이를 위해 여러 가지 일반 그래프를 손에 들고 싶습니다.
체계적으로 상징화되고 열거되고,
기호 (즉, 인접 행렬)에서 쉽게 생성되고
작은 세계 특성에 대한 닫힌 형식 표현이있을 수 있습니다. $L$ 과 $\bar{C}$
내가 염두에 둔 정규 그래프는 예를 통해 가장 쉽게 설명 할 수 있습니다.
정의
정점 구성을 정점을 나타내는 그래프로 설정 $\nu$ 많은 이웃과 함께 $\nu_0,\nu_2,\dots,\nu_{d-1}$ 연속 된 각 이웃 쌍 사이의 최단 경로 (임의의 길이) $\nu_i, \nu_{i+1}$. 정점 구성은 기호로 코드화 할 수 있습니다.$(n_1.n_2.\dots.n_k)^m$ 즉, $\nu$ 학위가있다 $d = m \cdot k$ 에 둘러싸여 $m$-주기적 순서 $n_i$-얼굴 resp. 가장 짧은주기. (이것은 그래프 이론의 언어로 기하학에서 정점 구성 의 표준 정의에 불과합니다 .)
예:
정점은 주어진 정점 구성을 가지고 있다고합니다. $\Gamma$ 이웃과 이웃 사이의 최단 경로 하나가 동형 일 때 $\Gamma$. 그래프는 주어진 정점 구성을 가지고 있다고합니다.$\Gamma$ 모든 정점에 정점 구성이있는 경우 $\Gamma$. 정점 구성은 그래프가있을 때 실현 가능하다고합니다.
이제 모든 정점이 동일한 정점 구성을 갖는 유한 그래프를 고려하십시오.
질문
모든 정점 구성 $\Gamma$다소 임의의 크기의 그래프로 실현할 수 있습니까? 이것을 증명하거나 반증하는 방법?
이것은 구 (즉, 정다면체)의 주기적 타일링을 정의하지 않는 모든 정점 구성 (기하학적 의미에서)이 유클리드 또는 쌍곡면의 주기적 타일링을 정의하는지 여부와 관련이 있습니다.실현 불가능한 정점 구성이있는 경우 : 주어진 정점 구성이 실현 가능한지 어떻게 확인합니까?
주어진 정점 구성으로 그래프를 수행합니까? $\Gamma$ 꼭짓점 전이 여야합니까?
동일한 정점 구성을 가진 두 정점 전이 그래프의 (동일한) 수의 정점이 동형임을 보장하지 않기 때문에 두 개의 동일하게 정의 된 그래프가 동형이되도록 "모양"을 정의 할 수있는 일반적인 수단은 무엇입니까? (예 : 아래 참조)
주어진 실현 가능한 정점 구성 및 "모양"에 대해 인접 행렬을 생성하는 체계적인 방법이 있습니까?
"모양"이란 Dolbilin과 Schulte가 논문 The Local Theorem for Monotypic Tilings 에서 "이웃 단지 (코로나)"라고 부르는 것을 의미합니다 .
예
정점 구성 고려 $(4)^4$ 그리고 숫자로 정의 된 "모양" $(4, 6)$
모양의 반대쪽에있는 정점을 연결할 때 모든 정점은 동일한 정점 구성을 갖습니다. $(4)^4$또한 결과 그래프는 정점 전이입니다.
우리는 직경을 찾습니다 $D = 5$, 클러스터링 계수 $\bar{C} = 0$, 평균 거리 $L =\frac{1}{23}(4\times 1 + 7 \times 2 + 7 \times 3 + 4 \times 4 + 1 \times 5) \approx 2.61$ 폐쇄 또는 재귀 명시 적 표현을 찾을 수 있습니다 ( $(n,m)$) 가능한 것 같습니다.
"모양"
동일한 정점 구성과 우리가 찾은 정점 수 $D = 5$ 및 평균 거리 $L =\frac{1}{23}(4\times 1 + 6 \times 2 + 6 \times 3 + 5 \times 4 + 2 \times 5) \approx 2.78$
"모양"
우리가 찾은 거의 같은 수의 정점으로 $D = 4$ 및 평균 거리 $L =\frac{1}{24}(4\times 1 + 8 \times 2 + 8 \times 3 + 4 \times 4 ) \approx 2.5$.
군집 계수를 원하는 경우 $\bar{C} = 1/2$ 정점 구성으로 시작할 수 있습니다. $(3.n)^m$, 예 : $(3.4)^2$:
안타깝게도이 구성은 평면이 아닌 구 ( 육 팔면체를 생성 ) 를 타일링하기 때문에 적합하지 않습니다 . 그래서 당신은 선택해야$(3.4)^3$적어도. 정점 구성을 사용하여 유한 그래프로 만들 수있는 일부 크기의 멋진 "모양"을 그리려면$(3.4)^m$, $m > 2$, 쌍곡선 기하학이 필요 합니다 . 내가 추측했듯이 인접 행렬을 찾는 것은 훨씬 더 어렵습니다 (질문 5 참조). 또한 직경$D$ 및 평균 거리 $L$ (닫힌 표현식으로).
또는 절반에 가장자리를 추가 할 수 있습니다. $n\cdot m$ $4$-사이클 (무작위로 선택) $(4)^4$ 그래프-따라서 직경 감소 $D$ 및 평균 거리 $L$.
답변
다음 정점 구성에는 표기법이 있습니다. $(3.4.4.4)^1$ 질문 1 (임의의 크기의 그래프 존재)과 질문 3 (정점 이동성)에 대한 반례를 제공해야합니다.
이 구성을 실현하는 그래프는 제한적으로 많으며 모두 최대 24 개의 정점으로 유한합니다. 그 중 정확히 2 개는 평면, 마름모 육 팔면체 의 가장자리 그래프 (왼쪽)와 밀접하게 관련된 유사 마름모 육 팔면체 의 가장자리 그래프 (오른쪽)입니다. 첫 번째 만 정점 전이입니다.
다른 모든 그래프는 정점을 식별하여 얻을 수 있습니다. 예를 들어 왼쪽 그래프에서 대척 점을 식별하면 "투영 다면체"가 제공됩니다.
이 그림에서는 명확하지 않기 때문에 오른쪽 이미지에서 정점 구성을 강조 표시했습니다.
이 구성의 모든 그래프라고 생각합니다. 내가 틀렸을 수도 있지만, 꼭짓점이 24 개 이상인 그래프는 확실히 없습니다.
더 일반적으로, 당신은에 관심이있을 수있는 지역 정리 에서
- Dolbilin과 Schulte의 "모노 타입 타일링에 대한 지역 정리"
특정 지역 제한이 글로벌 대칭을 의미하는 경우에 대한 질문입니다. 일반적으로 고유성과 정점 이동성을 제공하지만 토폴로지가 "간단히 연결"된 경우에만 적용됩니다 (따라서 구의 타일링의 경우 유클리드 / 하이퍼 볼릭 평면이지만 토러스에는 적용되지 않습니다. 그래프는 고유하지 않습니다.$(4)^4$).
섹션 3의 시작 부분 (정리 3.1 아래)에서는 구성이 $(3.5.5.5)^1$무한 그래프로 실현할 수 있지만 정점 전이 그래프로는 실현할 수 없습니다. 나는이 주장을 추적하려고 노력했지만 말 그대로 수천 개의 타일링이 포함 된 "Tilings and Patterns"책만을 언급하고 있으며 원하는 타일링을 찾을 수 없었습니다.
마지막으로 다음 구성 $(3.4.5)^1$ 전혀 실현할 수 없어야합니다.
이를 확인하려면 그래프에 "삼각형면"이 포함되어야합니다 (구성에 포함됨). 해당 삼각형의 세 모서리는 각각 사각형 또는 오각형과 공유됩니다. Wlog는 두 개의 가장자리가 쿼드 레인지와 공유된다고 가정합니다. 하지만이 두 모서리는 정점을 공유하므로이 정점은 유형이 될 수 없습니다.$(3.4.5)^1$.
일반적으로 실현 가능한 구성과 실현 불가능한 구성을 구별하는 것은 매우 까다로운 것 같습니다. 경험상 이전 예에서와 마찬가지로 이상한 얼굴이 문제를 일으키는 것으로 보입니다. 예를 들어 구성$(\mathbf 5.8.10)^1$ 두 종류의면을 묶는 오각형면이 있고 정점에서 반복되는면 유형이 없기 때문에 같은 이유로 존재할 수 없습니다.
(댓글에서) 당신이 가장 관심있는 것을 언급했기 때문에 $(3.n)^m$ (가정 $n\ge 3$, $m\ge 2$) :
이 구성은 항상 존재하고 고유하며 정점 전 이적입니다 ( "단순 연결된 토폴로지"를 가정하여 "그래프가 평면형"으로 번역 할 수 있음).
유한하다 $(3.3)^2$( 팔면체 ),$(3.4)^2$( 육 팔면체 ) 및$(3.5)^2$( 이십 십이 면체 ). "평면"이라고 생각할 수 있습니다.$\smash{(3.3)^3}$( 삼각형 타일링 ) 및$\smash{(3.6)^2}$( trihexagonal tiling ), 다른 모든 경우 쌍곡선.
고유성과 대칭성은 본질적으로 앞서 언급 한 지역 정리 (및 관련 확장 정리)의 결과입니다. 그러나 쉬운 용어로 말하자면, 이러한 정점 구성으로 그래프를 작성하려고하고 임의의 정점에서 시작한 다음 다른 정점 주변의 정점 구성을 완료하려고하면 고유 한 방식으로 만 수행 할 수 있습니다. (정말로 종이에 시도해보십시오). (무한히 많은) 단계에서 선택을하지 않기 때문에 결과는 독특합니다.