밀도 그래프

수학에서 밀도 그래프는 가장자리 수가 최대 가장자리 수에 근접하는 그래프를 말한다.그 반대, 가장자리가 몇 개뿐인 그래프는 희박한 그래프다.희박한 그래프와 조밀한 그래프의 구분은 다소 모호하며, 맥락에 따라 달라진다.

단순 그래프의 그래프 밀도는 최대 가능 에지에 대한$$ ${\displaystyle 에지}$ E $displaystyle E$}의 수의 비율로 정의된다.

리디렉션되지 않은 단순 그래프의 경우 그래프 밀도는 다음과 같다.

${\displaystyle D={\frac { E}{\binom {}{{2}}={\frac {2E}{V -1}}}}}$

지시된 단순 그래프의 경우 최대 가능한 가장자리는 지시도를 고려하는 비방향 그래프의 두 배이므로 밀도는 다음과 같다.

${\displaystyle D={\frac { E}{2{\binom {}{{2}}:}={\frac {{{{}}{{\frac { E}{V -1}}}}}}}$

여기서 E는 가장자리 수, V는 그래프에서 정점 수입니다.비방향 그래프의 최대 에지 수는${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{V}{}\frac{2}{}}$) = ${\displaystyle \frac{\mathrm{V}}{}}$(${\displaystyle \frac{}{}}$V - ${\displaystyle \frac{\mathrm{}}{}}$ )$$2 {\$displaystyle$ {\$binom {}{{2}}={\frac {$ V (V$-1){2$이므로 최대 밀도는 1(완전한 그래프의 경우)이고 최소 밀도는 0(Coleman & Moré 1983).

상위밀도

상한 밀도는 위에 정의한 그래프 밀도 개념을 유한 그래프에서 무한 그래프까지 확장한 것이다.직관적으로 무한 그래프는 높은 밀도보다 작은 밀도를 가진 임의로 큰 유한 서브그래프를 가지고 있으며, 그 밀도가 높은 임의의 큰 유한 서브그래프를 가지고 있지 않다.형식적으로 그래프 G의 상위 밀도는 농도 α의 G의 유한 서브그래프가 한정된 정점 수를 가지도록 값 α의 최소치다.Erdős-Stone 정리를 사용하여 상위 밀도는 1 또는 1만이 될 수 있다는 것을 알 수 있다.1/2, 2/3, 3/4, 4/5, ...n/n + 1, ...(예: Diestel, 5판, 페이지 189 참조).

희박하고 타이트한 그래프

Lee & Streinu(2008)와 Streinu & Theran(2009)은 정점이 있는 모든 비 빈 서브그래프가 최대 kn - l 에지를 가지고 있고 (k, l)-파스이며 정확히 kn - l 에지를 가지고 있다면 (k, l)-파스라고 정의한다.따라서 나무는 정확하게 (1,1)밀도 그래프, 숲은 정확히 (1,1)-파스 그래프, 그리고 식목성 k가 있는 그래프는 정확히 (k,k)-파스 그래프다.사이비숲은 정확히 (1,0)-파스 그래프이고, 경직성 이론에서 발생하는 라만 그래프는 정확히 (2,3)타이트 그래프다.

괄호로 특징지어지지 않는 다른 그래프 패밀리도 이와 같이 설명할 수 있다.예를 들어, 정점이 없는 평면 그래프의 에지는 최대 3n - 6개(정점 수가 3개 미만인 그래프는 제외)이며 평면 그래프의 하위 그래프는 평면 그래프라는 사실은 평면 그래프가 (3,6)-sparse라는 것을 의미한다.그러나 모든(3,6)-스파스 그래프가 평면적인 것은 아니다.마찬가지로 외부 평면 그래프는 (2,3)-파스, 평면 쌍방향 그래프는 (2,4)-파스다.

스트레이누와 테란은 k와 l가 정수일 때 다항 시간, 0㎛ l < 2k일 때 시험(k, l)-sparsity가 수행될 수 있음을 보여준다.

그래프 계열의 경우, 가족 내 그래프가 모두 (k, l)-파스인 k와 l의 존재는 가족 내 그래프가 퇴행성을 경계했거나 수목성을 경계한 것과 동등하다.좀 더 정확히 말하자면, 최대 a의 수목성 그래프가 정확히 (a,a)-sparse 그래프라는 것은 내시윌리엄스(1964)의 결과에서 비롯된다.마찬가지로, 최대 d에서의 퇴행성의 그래프는 정확히 (d + 1)/2, 1)-분산 그래프다.

그래프의 희박하고 조밀한 클래스

네셰틸&오소나 데 멘데스(2010년)는 첨사성/밀도 이분법으로 인해 단일 그래프 인스턴스 대신 무한 그래프 클래스를 고려할 필요가 있다고 판단했다.그들은 어딘가에 밀집한 그래프 클래스를 임계값 t가 존재하는 그래프의 클래스로 정의하여 모든 전체 그래프가 클래스의 그래프 하위 그래프에 t-분할로 표시되도록 하였다.반대로 그런 문턱이 존재하지 않으면 계급이 어디에도 밀도가 없다.네슈테틸 & 오소나 데 멘데스(2012년)에서는 어디선가 밀도 대 밀도 이분법의 특성이 논의된다.

경계가 있는 퇴행성 그래프와 어딘지 모르게 밀도가 높은 그래프의 클래스는 모두 바이클릭 프리 그래프에 포함되며, 일부 완전한 초당적 그래프를 하위 그래프로 제외하는 그래프 패밀리(Telle & Villanger 2012)이다.

참고 항목

• 경계확장
• 조밀도 하위그래프

참조

• 알고리즘 및 데이터 구조 사전의 Paul E. Black, Sparse 그래프, Paul E.검은색(에드), NIST.2005년 9월 29일에 회수되었다.
• Coleman, Thomas F.; Moré, Jorge J. (1983), "Estimation of sparse Jacobian matrices and graph coloring Problems", SIAM Journal on Numerical Analysis, 20 (1): 187–209, doi:10.1137/0720013.
• Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, ISBN 3-540-26183-4, OCLC 181535575.
• Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs", Discrete Mathematics, 308 (8): 1425–1437, arXiv:math/0702129, doi:10.1016/j.disc.2007.07.104, MR 2392060.
• Nash-Williams, C. St. J. A. (1964), "Decomposition of finite graphs into forests", Journal of the London Mathematical Society, 39 (1): 12, doi:10.1112/jlms/s1-39.1.12, MR 0161333
• Preiss, first (1998), Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, ISBN 0-471-24134-2.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2010), "From Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits", European Congress of Mathematics, European Mathematical Society, pp. 135–165
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, doi:10.1007/978-3-642-27875-4, hdl:10338.dmlcz/143192, ISBN 978-3-642-27874-7, MR 2920058.
• Streinu, I.; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics, 30 (8): 1944–1964, arXiv:math/0703921, doi:10.1016/j.ejc.2008.12.018.
• Telle, 얀 아르네;Villanger, Yngve(2012년),"biclique-free 그래프에 지배를 위해 FPT 알고리즘", 엡스타인은 레아에, Ferragina, 파올로(eds.), 알고리즘 – ESA2012년:20회 유럽 심포지엄, 류블랴나, 슬로베니아, 9월 10–12, 2012년, 회보, 강의 노트 컴퓨터 과학으로, 7501 vol., 스프링거,를 대신하여 서명함. 802–812,. doi:10.1007/978-3-642-33090-2_69.