근린(그래프 이론)

그래프 이론에서, 그래프에서 정점 v의 인접 정점은 가장자리에 의해 v와 연결되는 정점이다.그래프 G에서 정점 v의 근방은 v에 인접한 모든 정점에 의해 유도되는 G의 하위 그래프이다. 즉, v에 인접한 정점과 v에 인접한 정점을 연결하는 모든 가장자리로 구성된 그래프이다.

인근은 종종 ${\displaystyle N_{}G}$ (${\displaystyle }$v $){displaystyle N_{G}(v)}$ 또는$$ (그래프가 모호하지 않은 경우) $N{\displaystyle }$($)$ {$displaystyle$ N$(v$으로 $표시$됩니다.대응하는 유도 서브그래프가 아닌 인접 정점 세트를 참조하기 위해서도, 같은 인접 표기법을 사용할 수 있다.위에서 설명한 인접관계는 v 자체를 포함하지 않으며, 보다 구체적으로 v의 개방적인 인접관계입니다.또, 폐쇄된 인접관계라고 불리며 ${\displaystyle {NG}_{}[}$v$](\displaystyle N_{G}[v$로 $표시$되는 인접관계도 정의할 수 있습니다.아무 조건 없이 언급되었을 경우, 인접관계는 완전하다.열어야 할 의료.

인접관계 목록 및 인접관계 매트릭스 표현을 통해 컴퓨터 알고리즘에서 그래프를 표현하기 위해 인접을 사용할 수 있습니다.인근은 또한 인근 지역의 평균 밀도를 측정하는 그래프의 클러스터링 계수에도 사용됩니다.또한, 많은 중요한 그래프 클래스는 인접 지역의 특성 또는 인접 지역 간의 관계 대칭으로 정의될 수 있다.

고립된 정점에는 인접한 정점이 없습니다.정점의 정도는 인접한 정점의 수와 같습니다.특별한 경우는 정점을 그 자체에 연결하는 루프입니다.그런 엣지가 존재할 경우 정점은 그 자신의 네이버에 속합니다.

그래프의 로컬 속성

G의 모든 정점이 동일한 그래프 H와 동형인 인접 관계를 갖는 경우 G는 국소적으로 H라고 하며, G의 모든 정점이 어떤 그래프 계열 F에 속하는 인접 관계를 갖는 경우 G는 국소적으로 F라고 한다(Hell 1978, Sedlachek 1983).예를 들어 그림에 나타난 8면체 그래프에서 각 정점은 4개의 정점의 주기와 근방 동형을 가지므로 8면체는 국소적으로₄ C이다.

예를 들어 다음과 같습니다.

• 완전한 그래프_n K는 로컬_n-1 K입니다.국소적으로 완전한 그래프는 완전한 그래프의 분리된 결합뿐입니다.
• Turan 그래프 T(rs,r)는 국소 T(r-1)s,r-1)이다.보다 일반적으로 모든 투란 그래프는 국소 투란이다.
• 모든 평면 그래프는 로컬 외부 평면 그래프입니다.그러나 모든 로컬 외부 평면 그래프가 평면인 것은 아닙니다.
• 그래프는 로컬로 독립적인 경우에만 삼각형이 없습니다.
• 모든 k색 그래프는 국소적으로 (k-1)색이다.모든 국소 k색 그래프에는 $색수{\displaystyle }$ O$)$ {$displaystyle$ O$({\sqrt {kn}}})$가 있습니다(Wigderson 1983).
• 유도 서브그래프를 취득하는 조작으로 그래프 패밀리 F가 닫히면 F 내의 모든 그래프도 로컬 F가 된다.예를 들어, 모든 화음 그래프는 국소적으로 화음이고, 모든 완전한 그래프는 국소적으로 완벽하며, 모든 비교 가능성 그래프는 국소적으로 비교 가능합니다.
• 그래프는 모든 이웃이 주기인 경우 국지적으로 순환합니다.예를 들어, 8면체는 국소적으로₄ 연결된 고유 그래프이고, 20면체는 국소적으로₅ 연결된 고유 그래프이며, 순서 13의 팔레 그래프는 국소적으로₆ C입니다.K를₄ 제외한 국소 순환 그래프는 휘트니 삼각측정의 정확한 기초 그래프이며, 내장면이 그래프의 클리핑이 되도록 표면에 그래프를 내장한다(하르트펠트 & 링겔 1991; 라리온, 노이만-라라 & 피사냐 2002; 말니치 & 모하르 1992).국소 순환 그래프는 ${\displaystyle {n\mathrm{}}^{}}$2 -${\displaystyle o^{}}$ (${\displaystyle 1^{}}$ )$${ $displaystyle$ n$^{2-o(1)}$의 에지를 가질 수 있다(Seress & Szabo 1995).
• 발톱이 없는 그래프는 국소적으로 공삼각 없는 그래프이다. 즉, 모든 정점에 대해 정점 근방의 보완 그래프는 삼각형을 포함하지 않는다.국소적으로 H인 그래프는 H의 독립성이 최대 2인 경우에만 손톱이 없습니다. 예를 들어, 정십이면체의 그래프는 국소적으로₅ C이고₅ C는 독립성이 2이므로 손톱이 없습니다.
• 국소 선형 그래프는 모든 인접 지역이 유도 일치인 그래프이다(Fronchek 1989).

집합의 근린

정점 집합 A의 경우, A의 근방은 정점 근방의 합체이며, 따라서 A의 적어도 1개의 멤버에 인접한 모든 정점의 집합이다.

그래프 내의 정점 집합 A는 A의 모든 정점이 A의 바깥쪽에 동일한 이웃 집합을 갖는 경우 모듈이라고 한다.모든 그래프는 모듈로의 고유 재귀적 분해, 즉 모듈적 분해가 있으며, 모듈적 분해 알고리즘은 선형 시간에 그래프에서 구성될 수 있습니다. 모듈적 분해 알고리즘은 비교 가능성 그래프의 인식을 포함한 다른 그래프 알고리즘에 응용 프로그램을 가집니다.

「 」를 참조해 주세요.

• 마르코프 블랭킷
• 무어인근처
• 폰 노이만 근교
• 두 번째 이웃 문제
• 다면체의 관련 개념인 정점 도형

레퍼런스

• Fronček, Dalibor (1989), "Locally linear graphs", Mathematica Slovaca, 39 (1): 3–6, hdl:10338.dmlcz/136481, MR 1016323
• 를 클릭합니다Hartsfeld, Nora; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica, 11 (2): 145–155, doi:10.1007/BF01206358, S2CID 28144260.
• 를 클릭합니다Hell, Pavol (1978), "Graphs with given neighborhoods I", Problèmes combinatoires et théorie des graphes, Colloques internationaux C.N.R.S., vol. 260, pp. 219–223.
• 를 클릭합니다Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics, 258 (1–3): 123–135, doi:10.1016/S0012-365X(02)00266-2.
• 를 클릭합니다Malnič, Aleksander; Mohar, Bojan (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B, 56 (2): 147–164, doi:10.1016/0095-8956(92)90015-P.
• 를 클릭합니다Sedláček, J. (1983), "On local properties of finite graphs", Graph Theory, Lagów, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 242–247, doi:10.1007/BFb0071634, ISBN 978-3-540-12687-4.
• 를 클릭합니다Seress, Ákos; Szabó, Tibor (1995), "Dense graphs with cycle neighborhoods", Journal of Combinatorial Theory, Series B, 63 (2): 281–293, doi:10.1006/jctb.1995.1020.
• 를 클릭합니다Wigderson, Avi (1983), "Improving the performance guarantee for approximate graph coloring", Journal of the ACM, 30 (4): 729–735, doi:10.1145/2157.2158, S2CID 32214512.