완전한 그래프

완전한 그래프
7개의7 정점이 있는 완전 그래프인 K
꼭지점	n
가장자리	$\displaystyle \textstyle \frac {n(n-1)}{2}$
반지름	$\displaystyle \left \{\text{array}{ll}\leq 1\1&{\text{array}\end{array}}\오른쪽.}$
직경	$\displaystyle \left \{\text{array}{ll}\leq 1\1&{\text{array}\end{array}}\오른쪽.}$
둘레	$\displaystyle \left \{\text{array}{ll}\infty &n\leq 2\3&{\text{array}\end{array}\right.}$
자기동형	n! (Sn)
색수	n
색채 지수	n이 홀수일 경우 n이 짝수일 경우 n - 1
스펙트럼	$\displaystyle \left \{\text{ll}\emptyset &\left\{0^{1}\right\}&n=1\left\{(n-1)^{n-1}\right\}&{\text{array}\right}\right}.}$
특성.	(n - 1)-정규 대칭 그래프 정점-이행 엣지-트랜시 매우 규칙적이다 일체형
표기법	Kn.
그래프 및 매개 변수 표

그래프 이론의 수학 분야에서, 완전한 그래프는 모든 뚜렷한 정점 쌍이 고유한 모서리에 의해 연결되는 단순한 무방향 그래프이다.완전 이중 그래프는 각 개별 정점 쌍이 고유한 가장자리 쌍(각 방향으로 하나씩)으로 연결된 방향 그래프입니다.

그래프 이론 자체는 전형적으로 레온하르트 오일러의 1736년 쾨니히스베르크의 7개의 다리에서 시작된 것으로 추정됩니다.그러나, 정다각형 점 위에 꼭짓점을 배치한 완전한 그래프의 그림은 이미 13세기에 라몬 ^[1]룰의 작품에서 나타났다.그런 그림을 신비로운 ^[2]장미라고 부르기도 한다.

특성.

n개의 꼭지점에 대한 완전한 그래프는 K로 표시됩니다_n.일부 출처는 이 표기법의 문자 K가 독일어 단어 콤플렛을 ^[3]의미한다고 주장하지만, 완전한 그래프의 독일어 이름인 Vollstandiger Graph는 문자 K를 포함하지 않으며, 다른 출처는 표기법이 그래프 ^[4]이론에 대한 카지미에츠 쿠라토스키의 공헌을 존중한다고 말한다.

K는_n n(n – 1)/2개의 모서리(삼각형 수)를 가지며, n – 1의 정규 그래프입니다. 모든 완전한 그래프는 자체 최대 클리입니다.그래프 연결을 끊는 유일한 정점 절단은 전체 정점 집합이기 때문에 최대 연결입니다.완전 그래프의 보완 그래프는 빈 그래프입니다.

전체 그래프의 가장자리가 각각 방향을 지정하면 결과적으로 생성되는 방향 그래프를 토너먼트라고 합니다.

K는_n T가 i개의 ^[5]정점을 가지도록_i n개의 나무_i T로 분해할 수 있다.Ringel의 추측은 전체 그래프_2n+1 K를 n개의 ^[6]가장자리를 가진 트리의 복사본으로 분해할 수 있는지 여부를 묻습니다.이것은 충분히 큰 ^[7][8]n에 대해 사실인 것으로 알려져 있습니다.

K의_n+2 특정 꼭지점 쌍 사이의 모든 개별 경로의 수는 다음과 같이 주어진다^[9].

${\displaystyle w_{n+2}=n!e_{n}=\lfloor en!\loor,}$

여기서 e는 오일러의 상수를 나타낸다.

${\displaystyle e_{n}=\sum _{k=0}^{n}{\frac {1}{k!}}.}$

전체 그래프의 일치 수는 전화번호로 표시됩니다.

1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ...(OEIS의 시퀀스 A00000085).

이러한 수치는 n-vertex ^[10]그래프에 대해 호소야 지수의 가능한 최대값을 제공합니다.완전 그래프_n K의 완전 일치 수(짝수 n개)는 이중 요인(n – 1)!^[11]으로 표시됩니다.

K까지의 교차₂₇ 번호는 알려져 있으며, K는₂₈ 7233 또는 7234의 교차로가 필요합니다.추가 값은 직선 교차 번호 프로젝트를 ^[12]통해 수집됩니다.K에 대한_n 직선 교차 숫자는 다음과 같습니다.

0, 0, 0, 1, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ...(OEIS의 시퀀스 A014540).

지오메트리 및 토폴로지

n개의 노드가 있는 완전한 그래프는 (n – 1)-simplex의 가장자리를 나타냅니다.기하학적으로₃ K는 삼각형의 엣지 세트를 형성하고₄, K는 사면체 등을 형성한다.토러스의 위상을 가진 비볼록 다면체인 CsaaSzarr 다면체는 완전한 그래프₇ K를 골격으로 가지고 있다.4차원 이상의 모든 인접 폴리토프도 완전한 골격을 가지고 있습니다.

K부터₁₄ K까지는 모두 평면 그래프입니다.그러나 5개 이상 vertices을 갖춘 그래프의 모든 평면 그림이고, 그 비평면 완전 그래프 K:Kuratowski의 정리에 의해 평면 그래프의 characterizations에서 핵심 역할을 하고 있는 건널목이 포함되야만 한다, 그래프는 평면 만일 그것이 포함되어 있지 K5도 완전한 양분 그래프 K3,3으로 절목, 그리고 Wagner's.월하위 분할 대신 그래프 마이너에 대해 동일한 결과가 유지됩니다.Petersen 패밀리의 일부로서 K는₆ 링크리스 ^[14]임베딩의 금지된 미성년자 중 한 명과 같은 역할을 합니다.즉, Conway와^[15] Gordon이 증명했듯이, K의 모든₆ 3차원 공간 내 매립은 적어도 한 쌍의 연결된 삼각형과 본질적으로 연결되어 있습니다.콘웨이와 고든은 또한 K의₇ 모든 3차원 매립이 중요하지 않은 매듭으로 우주에 내장된 해밀턴 순환을 포함한다는 것을 보여주었다.

예

1 ~ 12 사이의 n$${\$displaystyle$n$}$개의$$$$ 정점에 $대한{\displaystyle }$ $전체{\displaystyle }$ 그래프는 에지 수와 함께 아래에 나와 있습니다.

K1: 0	K2: 1	K3: 3	K4: 6
K5: 10	K6: 15	K7: 21	K8: 28
K9: 36	K10: 45	K11: 55	K12: 66

「 」를 참조해 주세요.

• 완전히 연결된 네트워크, 컴퓨터 네트워킹
• 완전 이분 그래프(또는 바이클라이크)는 이분 그래프 중 한쪽에 있는 모든 정점이 다른 쪽에 있는 모든 정점에 연결되어 있는 특수 이분 그래프입니다.

레퍼런스

외부 링크

• Weisstein, Eric W. "Complete Graph". MathWorld.