밀집 그래프

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 그래프 밀도
- 2.1. 무한 그래프의 밀도 (상한 밀도)
3. 희소 그래프와 타이트 그래프
4. 그래프의 희소/밀집 클래스
- 4.1. 빅클리크-프리 그래프
참조

1. 개요

밀집 그래프는 그래프 이론에서 그래프의 밀도와 희소성을 다루는 개념과 관련된 용어이다. 그래프 밀도는 유한 그래프와 무한 그래프에 대해 정의되며, 상한 밀도는 무한 그래프의 밀도를 나타낸다. (k, l)-희소 그래프와 (k, l)-타이트 그래프는 그래프의 간선 수에 따라 정의되며, 트리, 숲, 평면 그래프 등이 이러한 그래프의 예시로 제시된다. 그래프 클래스의 희소성과 밀집성은 어딘가 밀집, 어디에도 밀집하지 않음으로 구분되며, 빅클리크-프리 그래프는 유한 퇴화도를 갖는 그래프와 어디에도 밀집하지 않은 그래프를 포함하는 그래프 패밀리이다.

더 읽어볼만한 페이지

그래프족 - 척도 없는 네트워크
척도 없는 네트워크는 네트워크 과학에서 연결 정도 분포가 멱법칙을 따르는, 즉 일부 허브 노드가 압도적으로 많은 연결을 가지는 불균등한 연결 구조를 가진 네트워크를 의미하며, 바라바시-앨버트 모델로 설명된다.
그래프족 - 정규 그래프
정규 그래프는 그래프 이론에서 모든 꼭짓점의 차수가 동일한 그래프를 의미하며, 각 꼭짓점이 k개의 변에 잇닿아 있는 그래프를 k-정규 그래프라고 하고, 여러 성질 및 다양한 분야에 응용된다.

밀집 그래프
그래프 정보
종류	그래프
정의
간선 수	최댓값에 가까운 그래프
속성
참고 문헌
참고 문헌	Coleman, T. F.; Moré, J. J. (1983)

2. 그래프 밀도

(내용 없음)

2. 1. 무한 그래프의 밀도 (상한 밀도)

상한 밀도는 유한 그래프에서 정의된 그래프 밀도의 개념을 무한 그래프로 확장한 것이다. 직관적으로 설명하면, 무한 그래프는 상한 밀도보다 작은 밀도를 갖는 임의로 큰 유한 부분 그래프를 가지지만, 상한 밀도보다 큰 밀도를 갖는 임의로 큰 유한 부분 그래프는 가지지 않는다. 공식적으로, 그래프 G의 상한 밀도는 밀도 α를 갖는 G의 유한 부분 그래프가 유한한 수의 정점을 갖는 값 α의 하한이다. 에르되시-스톤 정리를 사용하면 상한 밀도는 1 또는 초과분수 형태인 0, 1/2, 2/3, 3/4, 4/5, … , n/(n + 1) 중 하나만 될 수 있음을 보일 수 있다(예: Diestel, 5판, p. 189 참조).

3. 희소 그래프와 타이트 그래프

그래프의 희소성을 정량적으로 나타내는 한 방법으로 스트레이누와 테란 (2009)이 제안한 (''k'', ''l'')-희소 그래프와 (''k'', ''l'')-타이트 그래프 개념이 있다. 이 개념은 그래프 내 부분 그래프들의 간선 수에 특정 제약을 두어 정의되며, 다양한 종류의 그래프를 분류하고 그 특성을 이해하는 데 도움을 준다. 자세한 정의와 예시, 다른 그래프 종류와의 관계 등은 하위 섹션에서 다룬다.

3. 1. (k, l)-희소 그래프와 (k, l)-타이트 그래프

`스트레이누`와 `테란` (2009)은 그래프 ''G'' = (''V'', ''E'')에 대해, 모든 비어 있지 않은 정점 부분 집합 ''W'' ⊆ ''V''에 대해 ''W''에 의해 유도된 부분 그래프가 최대 ''kW'' - ''l''개의 간선을 가지면 (''k'', ''l'')-희소 그래프((k, l)-sparse graph)로 정의한다. 만약 그래프가 (''k'', ''l'')-희소 그래프이면서 정확히 ''kn'' - ''l''개의 간선(여기서 ''n''은 전체 정점 수)을 가지면 (''k'', ''l'')-타이트 그래프((k, l)-tight graph)라고 정의한다.

이 정의에 따르면, 다음과 같은 관계가 성립한다:

트리는 정확히 (1, 1)-타이트 그래프이다.
숲은 정확히 (1, 1)-희소 그래프이다.
아보리티가 ''k''인 그래프는 정확히 (''k'', ''k'')-희소 그래프이다.
의사 숲은 정확히 (1, 0)-희소 그래프이다.
강성 이론에서 나타나는 라만 그래프는 정확히 (2, 3)-타이트 그래프이다.

희소성만으로 특징짓기 어려운 다른 그래프 종류도 이 개념으로 설명할 수 있다. 예를 들어, ''n''개의 정점을 가진 평면 그래프는 (3개 미만의 정점을 가진 경우를 제외하고) 최대 3''n'' – 6개의 간선을 가진다. 또한 평면 그래프의 모든 부분 그래프 역시 평면 그래프이므로, 평면 그래프는 (3, 6)-희소 그래프이다. 그러나 모든 (3, 6)-희소 그래프가 평면 그래프인 것은 아니다. 비슷하게, 외부 평면 그래프는 (2, 3)-희소이며, 평면 이분 그래프는 (2, 4)-희소이다.

스트레이누와 테란은 정수 ''k'', ''l''에 대해 0 ≤ ''l'' < 2''k'' 조건이 만족될 때, 어떤 그래프가 (''k'', ''l'')-희소한지를 다항 시간 안에 판별할 수 있음을 보였다.

어떤 그래프 종류에 속하는 모든 그래프가 (''k'', ''l'')-희소하다는 성질은, 해당 종류의 그래프들이 경계가 있는 퇴화 또는 경계가 있는 아보리티를 갖는다는 것과 동등하다. 더 구체적으로, 다음과 같은 관계가 알려져 있다:

내시-윌리엄스 (1964)의 결과에 따르면, 아보리티가 최대 ''a''인 그래프는 정확히 (''a'', ''a'')-희소 그래프이다.
화이트 (1970)에 따르면, 퇴화가 최대 ''d''인 그래프는 (''d'', ''d''(''d''+1)/2)-희소 그래프이다.

3. 2. 평면 그래프와 희소성

희소 그래프의 정의에 직접 부합하지 않는 그래프 종류 중 일부도 희소성을 이용해 설명할 수 있다. 예를 들어, ''n''개의 정점을 가진 평면 그래프는 (3개 미만의 정점을 가진 그래프는 제외하고) 최대 3''n'' – 6개의 간선을 가진다. 또한, 평면 그래프의 모든 부분 그래프 역시 평면 그래프라는 성질 때문에, 평면 그래프는 (3,6)-희소 그래프라고 할 수 있다. 하지만 모든 (3,6)-희소 그래프가 평면 그래프인 것은 아니다.

비슷하게, 외부 평면 그래프는 (2,3)-희소 그래프이며, 평면 이분 그래프는 (2,4)-희소 그래프이다.

리 스트레이누와 테란은 ''k''와 ''l''이 정수이고 0 ≤ ''l'' < 2''k''라는 조건을 만족할 때, 어떤 그래프가 (''k'',''l'')-희소 그래프인지 판별하는 문제를 다항 시간 안에 해결할 수 있음을 보였다.

3. 3. 퇴화와 희소성

스트레이누와 테란 (2009)은 그래프의 희소성을 정의하는 한 가지 방법을 제시했다. 어떤 그래프에서 ''n''개의 정점을 가진 모든 비어 있지 않은 부분 그래프가 최대

kn - l

개의 간선을 가질 때, 이 그래프를

(k, l)

-희소 그래프라고 한다. 만약

(k, l)

-희소 그래프이면서 정확히

kn - l

개의 간선을 가지면

(k, l)

-타이트 그래프라고 부른다.

이 정의에 따르면 다음과 같은 예시를 들 수 있다.

트리는 정확히 $(1, 1)$ -타이트 그래프이다.
숲은 정확히 $(1, 1)$ -희소 그래프이다.
아보리티가 ''k''인 그래프는 정확히 $(k, k)$ -희소 그래프이다.
의사 숲은 정확히 $(1, 0)$ -희소 그래프이다.
구조적 강성 이론에서 다루는 라만 그래프는 정확히 $(2, 3)$ -타이트 그래프이다.

희소성만으로 완전히 특징지을 수는 없지만, 희소성의 개념으로 설명할 수 있는 다른 그래프 군들도 있다.

''n''개의 정점을 가진 평면 그래프는 (3개 미만의 정점을 가진 경우를 제외하고) 최대 $3n - 6$ 개의 간선을 가진다. 평면 그래프의 모든 부분 그래프 역시 평면 그래프이므로, 평면 그래프는 $(3, 6)$ -희소 그래프이다. 하지만 모든 $(3, 6)$ -희소 그래프가 평면 그래프인 것은 아니다.
외부 평면 그래프는 $(2, 3)$ -희소 그래프이다.
평면 이분 그래프는 $(2, 4)$ -희소 그래프이다.

스트레이누와 테란은 정수 ''k''와 ''l''에 대해

0 \le l < 2k

일 때, 어떤 그래프가

(k, l)

-희소한지를 다항 시간 안에 판별할 수 있음을 보였다.

어떤 그래프 군에 속하는 모든 그래프가

(k, l)

-희소하다는 것은, 그 군에 속하는 그래프들이 유한한 퇴화수를 갖거나 유한한 아보리티를 갖는다는 것과 동등하다. 더 구체적으로 살펴보면 다음과 같다.

내시-윌리엄스 (1964)의 결과에 따르면, 아보리티가 최대 ''a''인 그래프는 정확히 $(a, a)$ -희소 그래프이다.
유사하게, 화이트 (1970)에 따르면, 퇴화수가 최대 ''d''인 그래프는 $\left( d, \binom{d+1}{2} \right)$ -희소 그래프이다.

4. 그래프의 희소/밀집 클래스

네세트릴과 오소나 드 멘데스는 2010년 연구에서 그래프의 희소성/밀집성 이분법을 개별 그래프가 아닌 무한한 그래프 클래스 전체에 적용해야 한다고 주장했다. 그들은 어떤 그래프 클래스에 속한 그래프들의 부분 그래프 중에 모든 완전 그래프가 ''t''-세분으로 나타나게 하는 임계값 ''t''가 존재할 경우, 해당 클래스를 어딘가 밀집(somewhere dense)하다고 정의했다. 반대로, 이러한 임계값 ''t''가 존재하지 않으면 그 클래스는 어디에도 밀집하지 않음(nowhere dense)이라고 정의했다. 이 두 개념 사이의 이분법적 속성에 대한 더 자세한 논의는 네세트릴과 오소나 드 멘데스의 2012년 연구에서 찾아볼 수 있다.

참고로, 유한 퇴화도를 갖는 그래프 클래스와 어디에도 밀집하지 않은 그래프 클래스는 모두 빅클리크-프리 그래프라는 더 큰 범주에 속한다.

4. 1. 빅클리크-프리 그래프

빅클리크-프리 그래프는 어떤 완전 이분 그래프를 부분 그래프로 포함하지 않는 그래프 패밀리를 가리킨다. 이러한 빅클리크-프리 그래프에는 유한 퇴화도를 갖는 그래프 클래스와 어디에도 밀집하지 않은 그래프 클래스가 포함된다.

여기서 '어디에도 밀집하지 않은 그래프' 클래스는 네세트릴과 오소나 드 멘데스가 2010년에 정의한 개념이다. 그들은 그래프 클래스에 속한 그래프의 부분 그래프에 모든 완전 그래프가 ''t''-세분으로 나타나는 임계값 ''t''가 존재하지 않는 경우, 해당 클래스를 '어디에도 밀집하지 않음'이라고 정의했다. 어디에도 밀집하지 않음과 어딘가 밀집함의 이분법적 속성에 대한 자세한 논의는 네세트릴과 오소나 드 멘데스의 2012년 연구에서 다루어진다.

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com